A01.ipynb

Kernel: SageMath 10.0

Description

You must complete the following two functions. Your inputs are the digits of left/right hand side of the operators. We have discussed the solution during practice. You can assume that the inputs are correct, i.e. you should not check for errors. The digits are in little endian order, i.e. 123 in base 10 is [3, 2, 1]. You can only work with the digits and must not calculate the numbers from the digits.

You solution (Part 1):

def add(lhs_digits, rhs_digits, base):
    result = []
    carry = 0
    for i in range(max(len(lhs_digits), len(rhs_digits))):
       
        lhs_digit = lhs_digits[i] if i < len(lhs_digits) else 0
        rhs_digit = rhs_digits[i] if i < len(rhs_digits) else 0
        
        total = lhs_digit + rhs_digit + carry
        carry = total // base
        result.append(total % base)

    if carry > 0:
        result.append(carry)
    
    return result

All test cases passed!

Check your solution

The add function is defined to take three arguments: lhs_digits, rhs_digits, and base. It is intended to add two numbers represented by their digits in little-endian order.

Inside the function, we initialize an empty list called result to store the digits of the result of the addition.

We also initialize a carry variable to 0. This variable will be used to keep track of any carry that occurs during addition.

We use a for loop to iterate through both lists of digits, ensuring that all digits are processed. We determine the loop's range based on the maximum length between lhs_digits and rhs_digits.

Inside the loop, we get the digits from both lists, lhs_digit and rhs_digit. If one list is shorter than the other, we use 0 as the digit for the shorter list.

We calculate the total sum of the digits, including any carry from the previous iteration.

We calculate the new carry for the next iteration by performing integer division of total by base. The quotient becomes the new carry.

We append the remainder of the division of total by base to the result list. This represents the digit at the current position in the result.

After the loop, we check if there is any remaining carry. If there is, we append it to the result list to handle cases where the addition results in an extra digit with a carry.

Finally, the function returns the result list, which contains the digits of the sum of the two input numbers.

assert add([0], [1], 10) == [1]
assert add([0], [1, 1], 10) == [1, 1]
assert add([0, 1], [1], 10) == [1, 1]
assert add([2, 2], [3, 9], 10) == [5, 1, 1]

Your solution (Part 2):

def mul(lhs_digits, rhs_digits, base):
    len_lhs = len(lhs_digits)
    len_rhs = len(rhs_digits)
    
    result = [0] * (len_lhs + len_rhs)
    for i in range(len_lhs):
        carry = 0
        for j in range(len_rhs):
            product = lhs_digits[i] * rhs_digits[j] + result[i + j] + carry
            carry = product // base
            result[i + j] = product % base

        if carry > 0:
            result[i + len_rhs] += carry

    while len(result) > 1 and result[-1] == 0:
        result.pop()
    
    return result

Check your solution

The mul function is defined to take three arguments: lhs_digits, rhs_digits, and base. It is intended to multiply two numbers represented by their digits in little-endian order.

We calculate the lengths of the input digit lists and store them in len_lhs and len_rhs.

We initialize a result list filled with zeros. This list will store the digits of the product.

We use a nested for loop to iterate through the digits of the first number (lhs_digits) and the digits of the second number (rhs_digits).

Inside the inner loop, we multiply the current digits (lhs_digits[i] and rhs_digits[j]), add the result to the current position in the result list, and consider any carry from previous iterations.

We calculate the carry for the next iteration by performing integer division of product by base. The quotient becomes the new carry.

We set the current digit in the result list to the remainder of the division of product by base. This represents the digit at the current position in the result.

After the inner loop finishes processing all digits of the second number, we check if there is any remaining carry. If there is, we add it to the appropriate position in the result list.

We then remove any leading zeros from the result list using a while loop.

Finally, the function returns the result list, which contains the digits of the product of the two input numbers.

assert mul([0], [1], 10) == [0]
assert mul([1], [0], 10) == [0]
assert mul([0, 1], [1], 10) == [0, 1]
assert mul([1], [0, 1], 10) == [0, 1]
assert mul([5], [6], 10) == [0, 3]
assert mul([9, 9], [9, 9], 10) == [1, 0, 8, 9]