Алгоритм бинарного умножения Python?

Question

Я пишу эту программу python, чтобы понять, как реализовать алгоритм умножения. Я собрал «главную» копию всей моей работы и всех моих инструкций и того, что я сделал, чтобы не тратить время на 3-4 файла, чтобы перевернуть между ними. Мой вопрос - спросить, как мне начать работу с функцией shift_left и функциями binary_multiplaction. Я не понимаю, с чего начать.

import unittest 
import sys 


def binary_addition(a, b): 
""" 
Binary addition. 

:param a: the first operand - a tuple of bits 
:param b: the second operand - a tuple of bits 
:type a: tuple 
:type b: tuple 
:return: the sum, as a tuple of bits 
:rtype: tuple 
""" 

# first, ensure that the 2 arrays have the same number of bits, 
# by filling in with 0s on the left of the shortest operand 
diff = len(a)-len(b) 

if diff > 0: 
    # concatenating a tuple of size <diff> with tuple b (all elements are 0s) 
    b = ((0,) * diff) + b 
elif diff < 0: 
    # concatenating a tuple of size <-diff> with tuple a (all elements are 0s) 
    a = ((0,) * (-diff)) + a 

c = 0 
s = [0] * (len(a)+1) 
for j in reversed(range(0, len(a))): 
     d = (a[j] + b[j] + c) // 2 
     s[j+1] = (a[j] + b[j] + c) - 2*d 
     c = d 
s[0] = c 

# removing unneeded 0s on the left 
if s[0] == 0: 
    s.remove(0) 

return tuple(s) 


def shift_left(a,n): 
""" 
Shift an array of bits to the L, by adding n 0s on the right. 

#. construct a tuple of n elements, all 0s 

#. concatenate it to the tuple that has been passed in 

#. return the concatenation 

:param a: a tuple of bits 
:param n: the number of positions over which to shift 
:type a: tuple 
:return: if n > 0, the L-shifted array; otherwise, the original array; *if the first parameter (`a`) is not of the `tuple` type, the function should handle it nicely and return an empty tuple. A test in the test suite below checks that this requirement has been met.* 
:rtype: tuple 
""" 
# 
return a + (0,) * n 


def binary_multiplication(a, b): 
""" 
Multiply arrays of bits. 

#. Initialize the cumulative sum of product (a tuple with 0 as its only element) 

#. Go over the bits in `b` (the second multiplicand), in *reverse order*: if current bit is 1, add to the cumulative sum the operand `a`, L-shifted by 0 for rightmost bit, by 1 for bit k-1, by 2 for bit k-2, ... 

#. return the cumulative sum 

:param a: first multiplicand - an array of bits 
:param b: second multiplicand - an array of bits 
:type a: tuple 
:type b: tuple 
:return: an array of bits 
:rtype: tuple 
""" 

# 



class Multiplication_unittest(unittest.TestCase): 


def test_binary_addition_1(self): 
    self.assertEqual(binary_addition((1,0,1),(1,1,1,1)), (1,0,1,0,0)) 

def test_binary_addition_2(self): 
    self.assertEqual(binary_addition((1,1,1,1),(1,0,1)), (1,0,1,0,0)) 

def test_binary_addition_3(self): 
    self.assertEqual(binary_addition((1,0,1,1),(1,1,1,1)), (1,1,0,1,0)) 

def test_binary_addition_4(self): 
    self.assertEqual(binary_addition((0,),(1,)), (1,)) 

def test_binary_addition_5(self): 
    self.assertEqual(binary_addition((1,),(1,)), (1,0)) 

def test_binary_addition_6(self): 
    self.assertEqual(binary_addition((0,),(0,)), (0,)) 


def test_shift_left_1(self): 
    """ Trying to shift a value that is _not_ a tuple (ex. an integer) returns an empty tuple """ 
    self.assertEqual(shift_left(5, 3),()) 


def test_shift_left_2(self): 
    """ Shifting by 0 places returns the array that has been passed in """ 
    self.assertEqual(shift_left((1,1), 0), (1,1)) 


def test_shift_left_3(self): 
    """ Shifting an empty tuple by 1 place return a tuple with 0 as a single element """ 
    self.assertEqual(shift_left((), 1), (0,)) 


def test_shift_left_4(self): 
    """ Shifting a 1-tuple (with 0 as the only element) by 1 place """ 
    self.assertEqual(shift_left((0,), 1), (0,0)) 


def test_shift_left_5(self): 
    """ Shifting a 1-tuple (with 1 as the only element) by 1 place """ 
    self.assertEqual(shift_left((1,), 1), (1,0)) 


def test_shift_left_6(self): 
    """ Shifting 110 (6) by 3 places returns 110000 (6x8=48) """ 
    self.assertEqual(shift_left((1,1,0), 3), (1,1,0,0,0,0)) 


def test_multiplication_1(self): 
    """ Short operands: 0 x 0 """ 
    self.assertEqual(binary_multiplication((0,),(0,)), (0,)) 

def test_multiplication_2(self): 
    """ Short operands: 0 x 1 """ 
    self.assertEqual(binary_multiplication((0,),(1,)), (0,)) 

def test_multiplication_3(self): 
    """ Short operands: 1 x 0 """ 
    self.assertEqual(binary_multiplication((1,),(0,)), (0,)) 

def test_multiplication_4(self): 
    """ Short operands: 1 x 1 """ 
    self.assertEqual(binary_multiplication((1,),(1,)), (1,)) 

def test_multiplication_5(self): 
    """ Short operands 2 x 1""" 
    self.assertEqual(binary_multiplication((1,0),(1,)), (1,0)) 

def test_multiplication_6(self): 
    """ Long operands """ 
    self.assertEqual(binary_multiplication((1,0,1,1,1,1,0,1),(1,1,1,0,1,1,1,1)), (1,0,1,1,0,0,0,0,0,1,1,1,0,0,1,1)) 

def test_multiplication_5(self): 
    """ Operands of different sizes """ 
    self.assertEqual(binary_multiplication((1,0,0,1,1),(1,1,1,0,1,1,1,1)), (1,0,0,0,1,1,0,1,1,1,1,0,1)) 




def main(): 
    unittest.main() 

if __name__ == '__main__': 
    main() 

Answer 1

Вы были недалеко, и уже сделали сложную часть сложения и смены.

Вы все еще есть ошибки в тесте на shift_left, потому что один из ваших тестов требуют сдвиг нон кортежа возвращает пустой кортеж, когда он в настоящее время вызывает исключение. Здесь вы можете сказать, что исключение является нормальным и изменить тест, или явно проверить, что операнд является кортежем

def shift_left(a,n): 
    ... 
    # 
    if not isinstance(a, tuple): return() 
    return a + (0,) * n 

После этого умножение просто умножить произведение операнд1 каждой цифрой операнда 2 сдвиньте продукт (влево) на позицию цифры и добавьте все эти продукты. Как цифры могут быть только 0 или 1, он просто дает:

def binary_multiplication(a, b): 
    ... 
    # initialize a null tuple of same size as a for the final sum 
    s = (0,) * len(a) 
    # take a copy of a for the intermediary products 
    m = a[:] 
    for i in reversed(range(len(b))): 
     if b[i] != 0:  # when digit is one, add the intermediary product 
      s = binary_addition(s, m) 
     m = shift_left(m, 1) # shift one per digit in b 
    return s 

И ваши тесты проходят хорошо ...