Big-number arithmetic cost

Why this matters

Most of the time a program adds and multiplies numbers that fit in a single machine word, which is a fixed-size slot the processor works on at once. A loop counter, a price in cents or an array index all fit easily. Some programs need numbers that are far larger. A cryptography library works with keys that are commonly 2048 bits long, which is a number with about 617 decimal digits. A program that computes 1000 factorial produces a number with 2,568 digits. For these numbers the cost of one addition or one multiplication is no longer a fixed amount of work.

This lesson shows how to count that work. The count depends on how many digits each number has. Once you can count digits, you can say how an addition or a multiplication grows as the numbers grow, and you can see why a 64-bit number can be treated as a fixed cost.

The lesson on counting steps and Big-O explains the notation. The lesson on estimating from constraints shows how to pick a limit for a problem. Here the question is narrower: how much work does one arithmetic operation take when its inputs are large?

Digits are the unit of work

A decimal digit is one of the symbols 0 to 9. The number 2,568 has four decimal digits. A number with n digits is at least 10 to the power n minus 1 and below 10 to the power n. You can count the digits of a number by writing it out and counting the symbols.

The number of digits is the natural measure of size for big numbers. We will count the work in digit operations. A digit operation is one step that adds or multiplies two single digits, plus any carry. Our counts are exact counts of these steps in the program we write, so they do not change from run to run.

Computers store numbers in binary, which uses only 0 and 1. A binary digit is called a bit. The count of bits and the count of decimal digits differ only by a fixed factor: a decimal digit holds about 3.32 bits, because the logarithm of 10 in base 2 is about 3.32. So a number with n decimal digits has about 3.32 times n bits. Changing the unit from decimal digits to bits changes the count by a constant factor. That factor does not change the growth rate, so the big-number cost is written the same way in both units.

Adding two big numbers

Adding by hand works from the rightmost digit to the leftmost. You add the two digits in one column, plus any carry from the column on the right. You write the last digit of the sum and keep the tens digit as the carry for the next column to the left.

Here is 234 plus 987 worked by hand.

  234
+ 987
-----
 1221

Column by column from the right:

4 plus 7 is 11. Write 1, carry 1.
3 plus 8 plus the carry 1 is 12. Write 2, carry 1.
2 plus 9 plus the carry 1 is 12. Write 2, carry 1.
No digits are left, so the final carry 1 is written as the leading digit.

The result is 1221. There were three columns, so there were three digit operations, plus one final step to write the leftover carry.

A program does the same thing. It stores each number as a list of digits, with the least significant digit first, which is the rightmost digit. The least significant digit is the one with the smallest place value, so it is the one that gets the carry. The function below adds two lists of digits and counts the steps.

Python · editable

digits of 234 + 987: 1221 in 3 steps

The output matches the hand sum. The loop runs once for each column, and the number of columns is the length of the longer number. If both numbers have n digits, the addition takes n steps, plus at most one extra step for the carry. We write the cost as O(n), where n is the number of digits.

How the cost grows

Doubling the number of digits doubles the cost. A 1,000-digit number takes about 1,000 digit operations to add to another 1,000-digit number. A 10,000-digit number takes about 10,000. The cost is a straight line in the number of digits. This is the cheapest kind of big-number work, and it is why addition is rarely the bottleneck in a program that handles big numbers.

Multiplying two big numbers

Multiplying by hand uses a method that most people learn at school. Each digit of the first number is multiplied by each digit of the second number, and the partial results are added with shifts to the left. The method is called schoolbook multiplication.

Here is 12 times 34 worked by hand, using the same idea.

    12
x   34
-----
    8     (2 x 4)
   4      (1 x 4, shifted one place)
   6      (2 x 3, shifted one place)
  3       (1 x 3, shifted two places)
-----
  408

The number 12 has 2 digits and 34 has 2 digits, so there are 2 times 2 equals 4 digit products. Each product is one digit operation. Then the partial results are added, which costs a little more work. The total is 408.

A program can follow the same rule. For each digit of the first number, it multiplies that digit by each digit of the second number, adds the product into the right place of the result, and moves the carry to the left. The function below does this and counts each digit product.

Python · editable

digits of 12 * 34: 408 in 4 digit products

The output shows 4 digit products, which matches the hand count. The inner loop runs once for each pair of digits, so the count is the number of digits in the first number times the number of digits in the second number. If both numbers have n digits, the count is n times n, which is n squared. We write the cost as O(n²).

The carry handling after the inner loop adds a little more work, but it is at most about one step per digit of the result, so it does not change the growth. The growth is set by the pairs of digits.

How the cost grows

The table below uses the same program on two random numbers with n digits each. Each number was made from a fixed seed, so the counts are the same each time the lesson is run. The program checks each result against Python's own integer arithmetic, and every row passed.

Python · editable

import random

def to_digits(s):
    return [int(ch) for ch in reversed(s)]

def from_digits(d):
    return int("".join(str(x) for x in reversed(d)))

def add_digits(a, b):
    result = []
    carry = 0
    steps = 0
    for i in range(max(len(a), len(b))):
        steps += 1
        x = a[i] if i < len(a) else 0
        y = b[i] if i < len(b) else 0
        total = x + y + carry
        result.append(total % 10)
        carry = total // 10
    if carry:
        result.append(carry)
    return result, steps

def mul_digits(a, b):
    result = [0] * (len(a) + len(b))
    steps = 0
    for i, x in enumerate(a):
        carry = 0
        for j, y in enumerate(b):
            steps += 1
            total = result[i + j] + x * y + carry
            result[i + j] = total % 10
            carry = total // 10
        k = i + len(b)
        while carry:
            total = result[k] + carry
            result[k] = total % 10
            carry = total // 10
            k += 1
    while len(result) > 1 and result[-1] == 0:
        result.pop()
    return result, steps

random.seed(7)
print("digits n, add steps, mul steps (n by n), checks passed")
for n in [10, 100, 1000]:
    s1 = str(random.randrange(10**(n-1), 10**n))
    s2 = str(random.randrange(10**(n-1), 10**n))
    a, b = to_digits(s1), to_digits(s2)
    sum_d, add_steps = add_digits(a, b)
    prod_d, mul_steps = mul_digits(a, b)
    ok = from_digits(sum_d) == int(s1) + int(s2) and from_digits(prod_d) == int(s1) * int(s2)
    print(n, add_steps, mul_steps, ok)

print()
print("doubling the length")
for n in [500, 1000]:
    s1 = "9" * n
    a = to_digits(s1)
    _, add_steps = add_digits(a, a)
    _, mul_steps = mul_digits(a, a)
    print(n, add_steps, mul_steps)

digits n, add steps, mul steps (n by n), checks passed
10 10 100 True
100 100 10000 True
1000 1000 1000000 True
 
doubling the length
500 500 250000
1000 1000 1000000

Read the first table by column. The add steps equal n. The mul steps equal n times n: 100 for 10 digits, 10,000 for 100 digits and 1,000,000 for 1,000 digits. Every row returned True, which means the digit-by-digit answers matched Python's built-in integer results.

The second table shows the same pattern at 500 and 1,000 digits. Doubling the length from 500 to 1,000 doubled the addition steps and multiplied the multiplication steps by 4, because 1,000 squared is 4 times 500 squared. This is the main fact to remember: addition grows in step with the digits, and schoolbook multiplication grows with the square of the digits.

Why a 64-bit number is a fixed cost

A 64-bit number is a number stored in 64 bits, which is the size of one machine word on a common 64-bit processor. The largest unsigned 64-bit number is 2 to the power 64 minus 1. In decimal that is 18446744073709551615, which has 20 digits. Every 64-bit number has at most 64 bits and at most 20 decimal digits. The input size is capped.

When the size of the input has a fixed upper limit, any cost measured in digits or bits also has a fixed upper limit. The cost does not keep growing as the program runs more, because there is no bigger number to reach. This is what we mean when we say the cost is constant. It means the cost is bounded by a fixed number, not that it is zero.

The program below runs the same digit counting on the largest 64-bit number, and it checks the result against Python's arithmetic.

Python · editable

max64 = 2**64 - 1
print("largest unsigned 64-bit value:", max64)
print("decimal digits in it:", len(str(max64)))
print("bits in it:", max64.bit_length())

def to_digits(s):
    return [int(ch) for ch in reversed(s)]

def from_digits(d):
    return int("".join(str(x) for x in reversed(d)))

def add_digits(a, b):
    result, carry, steps = [], 0, 0
    for i in range(max(len(a), len(b))):
        steps += 1
        x = a[i] if i < len(a) else 0
        y = b[i] if i < len(b) else 0
        total = x + y + carry
        result.append(total % 10)
        carry = total // 10
    if carry:
        result.append(carry)
    return result, steps

d = to_digits(str(max64))
s, add_steps = add_digits(d, d)
p, mul_steps = mul_digits(d, d)
print("add steps for two 20-digit numbers:", add_steps)
print("mul steps for two 20-digit numbers:", mul_steps)
print("sum check:", from_digits(s) == 2 * max64)
print("product check:", from_digits(p) == max64 * max64)
print("product of max64 with itself:", max64 * max64)
print("digits in that product:", len(str(max64 * max64)))

largest unsigned 64-bit value: 18446744073709551615
decimal digits in it: 20
bits in it: 64
add steps for two 20-digit numbers: 20
mul steps for two 20-digit numbers: 400
sum check: True
product check: True
product of max64 with itself: 340282366920938463426481119284349108225
digits in that product: 39

The digit model counts 20 steps for the addition and 400 steps for the multiplication. Both numbers are fixed, so both counts are fixed. These counts are not the cost on the real processor, which is a separate question. A 64-bit processor does a 64-bit add or multiply with one instruction, or a small fixed number of instructions. The instruction count does not depend on the value of the number. That is the reason a text that counts operations on machine words treats add and multiply of 64-bit values as O(1), which means a constant amount of work.

Here is a rule of thumb for using this. If every number in your problem fits in 64 bits, count each arithmetic operation as one unit of work and move on. If a number can grow with the input, such as the value of n factorial or a sum over n terms, count its digits and use the digit-based cost from the earlier sections.

Growth in practice: factorials

A factorial multiplies all whole numbers from 1 up to n. The value grows very fast. The table below uses the digit model on a simple loop that multiplies a running product by a small number k, for k from 1 to n. The model counts the digits of the running product for each multiply, because a multiply by a small number takes one step for each digit.

Python · editable

digits of 100!: 158
digits of 1000!: 2568
n = 100 digit steps to build n! by multiplying by k each time: 6834
n = 1000 digit steps to build n! by multiplying by k each time: 1175176

The running product grows to 158 digits at n equals 100 and to 2,568 digits at n equals 1,000. The cost in digit steps is the sum of those digit counts over the loop, so it reaches 6,834 steps for n equals 100 and 1,175,176 steps for n equals 1,000. The number of loop iterations grew 10 times, but the cost grew about 172 times. The extra growth comes from the numbers getting longer, so each multiply takes longer too. A program that treats each multiply as one unit would miss this, and it would report a cost that is too low.

Common mistakes

Treating every multiply as one step

The most common mistake is to write that a loop does n operations, each costing O(1), when the numbers inside the loop grow. The factorial example shows the result: the count of loop steps is n, but the digit cost is much higher. Before you call an arithmetic step constant, check whether its inputs have a bounded size. If they do not, count the digits.

Forgetting the final carry

When you add two lists of digits, the final carry can still be 1 after the last column. If the code drops that carry, the answer is wrong. The check below shows the result of a version that forgets the final carry on the sum 99 plus 1.

Python · editable

99 + 1 without final carry: [0, 0]

The correct answer is 100, which needs three digits. The version above returns [0, 0], which reads as 00, so the carry was lost. The fix is the two lines at the end of add_digits in this lesson: if carry: followed by an append of the carry.

Converting a long string to a Python integer

Python limits how many digits a string may have when it converts the string to an integer. If the string is too long, the conversion stops with an error. This is a real error message from Python 3.14:

Python · editable

ValueError: Exceeds the limit (4300 digits) for integer string conversion: value has 5000 digits; use sys.set_int_max_str_digits() to increase the limit

The limit is a safety check against very slow conversions. For a program that reads huge numbers, the correct fix depends on the task. You can raise the limit with sys.set_int_max_str_digits, or you can keep the number as a list of digits and work on the list, as this lesson does. Raising the limit makes the conversion slower for very large inputs, so choose the limit on purpose.

Assuming a bounded input means a small one

A 64-bit number is bounded, but the bound is a fixed size, not zero. A loop that does 400 digit steps on a 64-bit product is still a fixed cost. The cost becomes a problem only when the number of such operations grows with the input. Check the loop count and the number size separately.

Practice

Exercise 1

Add 589 and 46 by hand, column by column. How many column operations do you use? Write the carry you pass to each column.

Show the answer

Column 1 is 9 plus 6, which is 15. Write 5, carry 1. Column 2 is 8 plus 4 plus the carry 1, which is 13. Write 3, carry 1. Column 3 is 5 plus 0 plus the carry 1, which is 6. Write 6, no carry. The sum is 635. There were 3 column operations, the length of the longer number.

Exercise 2

How many digit products does schoolbook multiplication need for a 3-digit number times a 4-digit number? Explain the count in one sentence.

Show the answer

It needs 12 digit products. Each of the 3 digits of the first number is multiplied by each of the 4 digits of the second number, and 3 times 4 is 12.

Exercise 3

A program adds two numbers with 5,000 digits each. Using the digit model in this lesson, how many steps does the addition take? How many digit products would multiplying the same two numbers take?

Show the answer

The addition takes about 5,000 steps, because it takes one step for each column. Schoolbook multiplication takes 5,000 times 5,000, which is 25,000,000 digit products. The multiplication is 5,000 times more work than the addition for numbers of this size.

Exercise 4

Write a short function that returns the number of decimal digits in a non-negative integer, without using len(str(n)). Check it on 0, 9, 10 and 99999. Show the code and the output you get.

Show the answer

One way is to repeatedly divide by 10 and count the divisions. The number 0 is counted as one digit, because the loop always runs at least once.

Python · editable

Exercise 5

A program computes the sum of the numbers 1 to n, using one addition for each number. Is the cost O(n) or O(n squared) if every number involved fits in 64 bits? What changes if the sum must be exact for n equal to one billion?

Show the answer

If every number involved fits in 64 bits, each addition is a fixed cost, so the total is O(n). The sum of 1 to one billion is about 5 times 10 to the power 17, which still fits in 64 bits, so the cost stays O(n). For a larger n the sum may need more bits, and then each addition costs more than a fixed amount, so the count must include the digits of the running sum.

Summary

A number with n decimal digits takes about n digit operations to add, so addition costs O(n).
Schoolbook multiplication takes one digit product for each pair of digits, so it costs O(n squared).
Doubling the number of digits doubles the addition cost and quadruples the multiplication cost.
A 64-bit number has at most 20 decimal digits, so arithmetic on it has a fixed upper cost and is treated as O(1).
Count digits when the numbers grow with the input, such as in a factorial, because a loop with a fixed count can still have a growing cost.
Check the final carry and the Python digit limit when you convert or add long numbers.

Big-number arithmetic cost

Why this matters

Digits are the unit of work

Adding two big numbers

How the cost grows

Multiplying two big numbers

How the cost grows

Why a 64-bit number is a fixed cost

Growth in practice: factorials

Common mistakes

Treating every multiply as one step

Forgetting the final carry

Converting a long string to a Python integer

Assuming a bounded input means a small one

Practice

Exercise 1

Exercise 2

Exercise 3

Exercise 4

Exercise 5

Summary

Stuck? Ask the tutor