Fastest way to add two big numbers (a million digits)

Question

Constraint:

1 ≤ 𝐴 ≤ 𝐵 ≤ 10^1000000

Input:

1000211 1000299

Output:

2000510

The runtime must be <4 s.

I've already tried but it's still too slow:

x, y = input().split()
print(int(x) + int(y))

Answer 1

You're converting from decimal to binary and back. At least in CPython, that takes quadratic time (or causes an error). Instead of int, use Decimal, after configuring for "bignum arithmetic" as shown near the end of that page. Then it takes linear time.

Timings of the steps with both numbers at the limit:

int() 14.1069 seconds
add    0.0005 seconds
str() 15.9351 seconds
print  0.0019 seconds

And with using Decimal as int:

int()  0.0366 seconds
add    0.0001 seconds
str()  0.0043 seconds
print  0.0009 seconds

Code (Try it online!):

from time import time
from contextlib import redirect_stdout
import io

# Set to True for using Decimal as int (a hack to overwrite it like that, but meh, who cares here)
if False:
    from decimal import *
    setcontext(Context(prec=MAX_PREC, Emax=MAX_EMAX, Emin=MIN_EMIN))
    int = Decimal

def report(label):
    global t
    print(label, f'{time() - t:7.4f} seconds')
    t = time()

x = y = '9'*999999
t = time()
x, y = int(x), int(y)
report('int()')
s = x + y
report('add  ')
s = str(s)
report('str()')
with open('/dev/null', 'w') as devnull:
    with redirect_stdout(devnull) as f:
        print(s)
report('print')

Answer 2

[Edit: Including feedback from Kelly]

Here's the old-school way of doing big integer addition.

• You start at the back of the string, i.e. units, then move up, i.e. tens, etc
• You do 1 digit addition and you keep a running carry bit

Representing this in Python it would be easy to reverse the string with [::-1] so that you can start at index 0 of the string for the units, index 1 of the string for tens, and so forth. We do all digits until we run out and the carry has diminished to 0.

As per Kelly's advice, we stage the result in a string array and, when we're done, we turn it back into a string with a join.

Also, as pointed out by Kelly this may not be the fastest way since the algorithm is not in native code. When I ran this on tio.run I hit the 4s threshold close to 10^1000000. So the algorithm just scrapes in, satisfying the criteria.

import re

def sum(a, b):
    a = [int(e) for e in re.findall('.', a)][::-1]
    b = [int(e) for e in re.findall('.', b)][::-1]
    carry = 0
    i = 0
    result = [ ]
    while (i < len(a) or i < len(b) or carry > 0):
        sum = (a[i] if i < len(a) else 0) + (b[i] if i < len(b) else 0) + carry
        result.append(sum % 10)
        carry = sum // 10
        i = i + 1
    return "".join([str(e) for e in result[::-1]])

while True:
    print("Input:")
    a, b = input().split()
    print("Output:", sum(a, b))

To improve performance, rather than add 1 digit at a time, we can consider adding 8 digits at a time. The new algorithm:

• Pads the number to an exact multiple of 8 characters
• Then uses regular expressions to split this into an array of 8 characters
• Convert the array of 8 characters into an array of 8-digit numbers
• Then the while loop does 8-digit number addition with carry
• When we have our result, we convert it back into an array of 8 characters and clean it up

import re

def sum(a, b):
    if (len(a) % 8) > 0: a = a.zfill(len(a) + 8 - (len(a) % 8))
    if (len(b) % 8) > 0: b = b.zfill(len(b) + 8 - (len(b) % 8))
    a = re.findall('........', a)
    b = re.findall('........', b)
    a = [int(e) for e in a][::-1]
    b = [int(e) for e in b][::-1]
    carry = 0
    i = 0
    result = [ ]
    while (i < len(a) or i < len(b) or carry > 0):
        sum = (a[i] if i < len(a) else 0) + (b[i] if i < len(b) else 0) + carry
        result.append(sum % 100000000)
        carry = sum // 100000000
        i = i + 1
    return "".join([str(e).zfill(8) for e in result[::-1]]).lstrip("0")