"Homemade" infinite precision sum function

Question

How would you go about this:

Write your own infinite precision "sum", "product", and "to the power of" functions, that represent numbers as lists of digits between 0 and 9 with least significant digit first. Thus: 0 is represented as the empty list [], and 10 is represented as [0,1]. You may assume that numbers are non-negative (no need for negative numbers, or for subtraction).

I have functions to convert to and from.

eg: iint(5387) == [7, 8, 3, 5] and pint([7, 8, 3, 5]) == 5387

def iint(n):
    # list of all digits in the int
    digits = [int(x) for x in str(n)]
    # reverse the list
    digits.reverse()
    return digits

def pint(I):
    # new int c
    c = 0
    # iterates through list
    for i in range(len(I)):
        # add to c digit in the list multiplied by 10^of its position in the list. 1, 10, 100, 1000 ect.
        c = c + I[i] * (10 ** i)
    return c

# add two infinite integers
def iadd(I, J):
    pass

First though would be just convert back to int do the calculation and then back again but that would "gut the question".

Not looking for a complete solution just some pointers on where to start for iadd()because I am completely stumped. I assume after you get iadd() the rest should be simple enough.

How would you add 2 long numbers on paper, by hand? It's the same process here. Start by writing out, in plain english, the steps you would take to do the manual addition. From there, you can start translating them into code, one bit at a time. — Alexander, Oct 26 '21 at 12:51
Remember there are a few cases you need to keep track of: if you had numbers (lists of digits) `a` and `b`, they might 1) have the same number of digits, or 2) `a` has fewer digits, or 3) `b` has fewer digits. Also, when adding digits together, the individual digit sum might 1) be `<= 9` or 2) be `>= 10` -- remember when it's `>=10` you'll need to "carry the 1" — Joshua Voskamp, Oct 26 '21 at 12:57
https://stackoverflow.com/questions/13905936/converting-integer-to-digit-list?rq=1 shows a fast(er?) way to accomplish your `iint` function: `return reversed(list(map(int,str(n))))` — Joshua Voskamp, Oct 26 '21 at 15:13

Joshua Voskamp · Accepted Answer · 2021-10-26T13:56:47.613

For writing your iadd function, one way is to use test-driven development; write your test inputs, and your expected outputs. assert that they're equal, then rewrite your function so it passes the testcase.

In the particular case of needing to add two lists of numbers together, "how would you do that by hand?" (as noted by a comment) is an excellent place to start. You might

starting from the least-significant digit
add individual digits together (including a carry from the previous digit, if any)
carry the "high" digit if the result is > 9
record the result of that addition
loop from step 2 until you exhaust the shorter number
if you have a carry digit "left over," handle that properly
if one of the input numbers has more digits than the other, properly handle the "left over" digits

Here's a code snippet that should help give some ideas:

    for d in range(min(len(I),len(J))):
        added = I[d] + J[d]
        digit = added%10 + carry
        carry = added//10

And some testcases to try:

assert iadd([1],     [1]) == [2]   # 1 + 1 == 2
assert iadd([0,1],   [1]) == [1,1] # 10 + 1 == 11
assert iadd([9,1],   [1]) == [0,2] # 19 + 1 == 20
assert iadd([9,9,9,9,9], [2])         == [1,0,0,0,0,1] # 99,999 + 2   == 100,001
assert iadd([4,0,2],     [9,2,3,4,1]) == [3,3,5,4,1]   # 201 + 14,329 == 14,533

You may need to take the rest of the division per 10 after adding the carry :) if added = 9 and carry =1 you will end up with an error Itk — JuR, Oct 26 '21 at 13:48
@JuR not shown is the rest of my (working) code, with the operations in that order ;) **edit: i see what you mean ;) — Joshua Voskamp, Oct 26 '21 at 13:51
Yes, sorry should have made it clean in the question that you can assume the numbers are non-negative. Your explanation is very helpful thank you. — chas108, Oct 26 '21 at 13:56

Alain T. · Answer 2 · 2021-10-27T15:54:36.400

Itertools's zip_longest should be very useful to implement the addition operation.

For example:

def iint(N): return [int(d) for d in reversed(str(N))] 
def pint(N): return int("".join(map(str,reversed(N))))

from itertools import zip_longest
def iadd(A,B):
    result = [0]
    for a,b in zip_longest(A,B,fillvalue=0):
        result[-1:] = reversed(divmod(a+b+result[-1],10))
    while result and not result[-1]: result.pop(-1) # remove leading zeros
    return result


a = iint(1234)
b = iint(8910)
print(iadd(a,b)) # [4, 4, 1, 0, 1]  (10144)

For the multiplication, you should make sure to keep the intermediate results below 100

def iprod(A,B):
    result = []
    for iA,a in enumerate(A):
        if not a: continue
        result = iadd(result,[0]*iA+[a*d for d in B]) # a*d+9 <= 90
    return result

print(iprod(a,b)) # [0, 4, 9, 4, 9, 9, 0, 1] 10994940

For the power operation, you'll want to break down the process into a reasonable number of multiplications. This can be achieved by decomposing the exponent into powers of 2 and multiplying the result by the compounded squares of the base (for 1 bits). But you'll need to make a division by 2 function to implement that.

This strategy is based on the fact that multiplying a base raised to various powers, adds these powers:

A^7 * A^6 = A^13

and that any number can be expressed as the sum of powers of two:

13 = 1 + 4 + 8,

so

A^13 = A^1 * A^4 * A^8.

This reduces the number of multiplications for A^B down to 2log(B) which is much less than multiplying A by itself B-1 times (although we'll be dealing with larger numbers).

def idiv2(N):
    result = N.copy() or [0]
    carry  = 0
    for i,d in enumerate(reversed(N),1):
        result[-i],carry = divmod(result[-i]+carry*10,2)
    return result if result[-1] else result[:-1]
        
def ipow(A,B):
    result, a2n = [1], [] # a2n is compounded squares A, A^2, A^4, A^8, ...
    while B:
        a2n = iprod(a2n,a2n) if a2n else A
        if B[0]%2 : result = iprod(result,a2n)
        B = idiv2(B)
    return result

print(ipow(iint(12),iint(13))) 
# [2, 7, 0, 9, 7, 3, 5, 0, 2, 3, 9, 9, 6, 0, 1] 106993205379072

print(len(ipow(a,b))) # 27544 digits (takes a long time)

Further optimization could be achieved by creating a specialized square function and using it instead of iprod(a2n,a2n)

"Homemade" infinite precision sum function

2 Answers2