How to count carries in multiplication?

Question

I'm having trouble counting the number of carries in any multiplication problem using Python 2. I attempted to tweak a program I already made that counts carries in any addition problem, but I still cannot seem to make it work. I'm currently learning the basics of Python, so I'm using pretty simple stuff. Any pointers on how to convert this program to apply to multiplication would be appreciated!

Here is my counting carries for addition program:

if len(str(x)) != len(str(y)):
    if len(x) > len(y):
        while len(x) > len(y):
            y = '0' + y
    else:
        while len(y) > len(x):
            x = '0' + x
z = int(x) + int(y)
counter = 0
carries = 0
i = len(str(x))

while i > 1:
    i -= 1
    added = int((x[i])) + int((y[i])) + counter

    if added > 9:
        carries +=1
        counter = 1
    else:
        counter = 0

print str(x), '+', str(y), '=', z
print 'Number of carries: ', str(carries)

Answer 1

I made the assumption that by the number of carries you wanted to know how many times a carry occurred, not the total sum of carries. For example 34 x 48 would have have one multiplication carry for the first step (carry the 3 when multiplying 4 and 8), even though the total carried value was equal to 3.

Additionally, I assumed that you wanted to also know the number of addition carries that occurred when doing the multiplication. Continuing our example, when we multiply 34 * 40 we have one multiplication carry (4 * 4). We now have to add the two results (272 and 1360). This would result in one addition carry, with a total number of carry operations equal to 3.

Basically, I calculate the total number of carries, excluding carries past the largest number. This means that 90 * 9 would not have any carries. Similarly, 90 + 99 would also not have any carries. I decided on that behavior, based off how your addition carries worked. If you didn't mean for that to occur and would like to include the carry off the last bit, simply follow the code changes noted in the **** ... **** comments.

The code is below. I included my own implementation of computing addition carries. It should be functionally equivalent to the code you posted.

def num_add_carries(x, y):
    """
    Return a count of the number of addition carries.

    @param x: A number to add, as an integer.

    @param y: A number to add, as an integer.

    @return: The total number of carry operations.
    """

    # Determine which number is the larger one
    if y <= x:
        min_num = y; max_num = x
    else:
        min_num = x; max_num = y

    # Initialize some parameters
    num_carries = 0
    smin = str(min_num); smin_length = len(smin)
    smax = str(max_num); smax_length = len(smax)

    # Determine the end looping parameter
    #   **** Set to '-1' to include the end carry ****
    end_ix = -1 if smin_length != smax_length else 0

    # Iteratively perform the multiplication, counting the mult carries
    for i, ix in enumerate(xrange(smin_length - 1, end_ix, -1), 1):
        if int(smax[-i]) + int(smin[ix]) > 9:
            num_carries += 1

    return num_carries

def num_mult_carries(x, y):
    """
    Return a count of the total number of multiplication carries, including
    all necessary addition carries.

    @param x: A number to add, as an integer.

    @param y: A number to add, as an integer.

    @return: The total number of carry operations.
    """

    # Determine which number is the larger one
    if y <= x:
        min_num = y ; max_num = x
    else:
        min_num = x; max_num = y

    # Initialize some parameters
    num_carries = 0; adds = [] # List of numbers to add
    smin = str(min_num); smin_length = len(smin)
    smax = str(max_num); smax_length = len(smax)

    # Iteratively perform the multiplication, counting the mult carries
    for i, ix in enumerate(xrange(smin_length - 1, -1, -1)):
        # Perform Multiplication (used for summing, later)
        adds.append(max_num * int(smin[ix]) * (10 ** i))

        # Determine number of multiplication carries
        #   **** Change the '0' to '-1' to include the end carry **** 
        for ix2 in xrange(smax_length - 1, 0, -1):
            if int(smax[ix2]) * int(smin[ix]) > 9:
                num_carries += 1

    # Iteratively perform the addition, counting the addition carries
    s = 0
    while len(adds) > 1:
        s += adds.pop(0)
        num_carries += num_add_carries(s, adds[0])

    return num_carries

print num_add_carries(99, 99)
print num_mult_carries(657, 34)

The output to the above code is:

1
6

Answer 2

I made the same assumptions as @TehTechGuy, though I approached the problem differently. I chose to use a recursive method rather than an iterative one, since it is more natural for those sorts of problems.

If we are counting the carries that occur during the addition phase, then we need to encapsulate the logic for counting addition carries in a method, as follows:

def count_addition_carries_rec(nums, answer=0, carries=0):

    dig_count = max(len(str(nums[0])), len(str(answer)))
    carries_list = [0]
    new_answer = ''
    # convert to string, apply left-padding, and reverse
    rnums = [str(x).zfill(dig_count)[::-1] for x in [nums[0], answer]]

    for i in range(dig_count):
        dig_sum = str(sum([int(num[i]) for num in rnums]) + carries_list[i])
        if i < dig_count - 1:
            new_answer = dig_sum[-1] + new_answer
            carries_list.append(int(dig_sum[:-1].zfill(1)))
        else:
            new_answer = dig_sum + new_answer

    carries_list = [car for car in carries_list if car != 0]

    if len(nums) == 1:
        # If this is the last number in the list, 
        # return the answer and the number of carries that 
        # occurred in the current as well as previous operations.
        return int(new_answer), carries + len(carries_list)
    else:
        # if there are more numbers in the list,
        # repeat the operation with a sublist, consisting of the next
        # number onwards, passing the current sum (new_answer) and 
        # the current count of carries 
        return count_addition_carries_rec(nums[1:],
                                          new_answer,
                                          carries + len(carries_list))

The count_addition_carries_rec method is generic in that it can take more than 2 integers. The nums argument is a list, which the method expects to be of length 2 or more.

And the method for counting multiplication carries looks as follows:

def count_multiplication_carries_rec(num1, num2, answer=0, carries=0):

    num1, num2 = str(num1), str(num2)

    # if num2 is smaller than num1, 
    # then reverse their assignments, and apply left-padding
    # to the smaller number. 

    if int(num2) < int(num1):
        num1, num2 = num2.zfill(len(num1)), num1
    else:
        num1, num2 = num1.zfill(len(num2)), num2

    carries_list = [0]
    new_answer = ''

    for i in range(len(num2)):
        dig_mul = str(int(num1[-1])*int(num2[len(num2) - i - 1]) + carries_list[i])
        if i < len(num2) - 1:
            new_answer = dig_mul[-1] + new_answer
            carries_list.append(int(dig_mul[:-1].zfill(1)))
        else:
            new_answer = dig_mul + new_answer

    new_answer += '0'*(len(num2)-len(str(int(num1))))
    carries_list = [car for car in carries_list if car != 0]

    if len(str(int(num1))) == 1:
        # If this is the last digit in num1,
        # then return the sum of the answer of the previous operation
        # and the answer of the current operation, counting
        # the addition carries in the process. 
        # Return the final answer as well as the count 
        # of multiplication and addition carries.
        return count_addition_carries_rec([int(answer), int(new_answer)],
                                          answer=0,
                                          carries=carries+len(carries_list))
    else:
        # If there are more digits in num1, repeat the operation
        # with num1 stripped of its last digit.
        return count_multiplication_carries_rec(num1[:-1],
                                                num2,
                                                *count_addition_carries_rec([int(answer), int(new_answer)],
                                                                            answer=0,
                                                                            carries=carries+len(carries_list)))

The count_multiplication_carries_rec is not as generic as the addition method, but that can be easily fixed. You can either create an auxiliary method that calls count_multiplication_carries_rec with 2 numbers at a time, or you can modify the current implementation to work with any number of integers.

Examples using the 2 methods:

>>> count_addition_carries_rec([99,99])
(198, 1)

>>> count_addition_carries_rec([17, 17, 17])
(51, 2)

>>> count_multiplication_carries_rec(15,15)
(225, 2)

>>> count_multiplication_carries_rec(657,34)
(223380, 6)

As you can see, the methods return the result of the addition/multiplication operation as well as the number of carries that occurred while performing that operation.