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

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')

[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")

The issue here might be that while taking the time you are starting the timer before taking input() and it is adding the time taken by you type the same, otherwise it is working as per your constraint.

Benchmark answer, comparing the different solutions with two numbers at the limit (using strings for input/output):

28.246 seconds  sum_with_int
 0.035 seconds  sum_with_Decimal
 3.574 seconds  sum_by_hand
 0.479 seconds  sum_by_hand_8

Code (Try it online!):

Old link (Try it online!):

def sum_with_int(a, b):
    return str(int(a) + int(b))

def sum_with_Decimal(a, b):
    return str(Decimal(a) + Decimal(b))

def sum_by_hand(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]])

def sum_by_hand_8(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")

funcs = sum_with_int, sum_with_Decimal, sum_by_hand, sum_by_hand_8

from time import time
from decimal import *

setcontext(Context(prec=MAX_PREC, Emax=MAX_EMAX, Emin=MIN_EMIN))

a = b = '9' * 30
for f in funcs:
    print(f(a, b))

a = b = '9' * 999999
for _ in range(1):
    for f in funcs:
        t = time()
        f(a, b)
        print('%6.3f seconds ' % (time() - t), f.__name__)
    print()