Card 07/ 08
Practice: Costing a Faster Way to Multiply Large Numbers
Multiplying two n-digit numbers takes three half-size multiplications and some linear-time additions.
Costing a divide-and-conquer design means writing its recurrence from a description and solving it, and this exercise practises both on a problem where one call fewer is the whole improvement. It needs the recurrence form T(n) = a·T(n/b) + f(n) and the master theorem's three cases.
Multiplying two n-digit numbers the way taught at school multiplies every digit of one by every digit of the other: n² single-digit multiplications. A divide-and-conquer version splits each number into a high half and a low half of n/2 digits. The product can then be assembled from four products of half-size numbers, high times high, high times low, low times high and low times low, plus some additions and shifts by powers of ten, which take time linear in n. In 1960 Anatoly Karatsuba found a rearrangement that gets the same product from three half-size multiplications, at the cost of a few extra additions and subtractions, still linear.
- Write the recurrence for the four-multiplication version, and solve it with the master theorem.
- Do the same for Karatsuba's three-multiplication version.
- Recurse down to single digits on two 1,024-digit numbers. How many single-digit multiplications does each version make?
Show the answer
Each version calls itself on halves and does linear work outside the calls, so b is 2 and f(n) is O(n) in both; only a differs. With four calls n^(log₂ 4) is n², and with three it is n^(log₂ 3), about n^1.585. Both outgrow the linear work, so both are case 1 and the leaves set the cost.
| Multiplications | Recurrence | n^(log₂ a) | Result |
|---|---|---|---|
| Four | T(n) = 4T(n/2) + O(n) | n² | O(n²) |
| Three | T(n) = 3T(n/2) + O(n) | n^1.585 | O(n^1.585) |
The four-multiplication version is O(n²), no better than the school method: splitting alone bought nothing. Karatsuba's single saved call changes the exponent. For part 3, each level of recursion multiplies the number of products by a while the numbers halve, and 1,024 digits halve ten times to reach one, so the counts are 4¹⁰ and 3¹⁰. The program below counted them by recursing, treating each half-size product as one call as the recurrence does.
import math
def single_digit_products(calls: int, digits: int) -> int:
if digits == 1:
return 1
return sum(single_digit_products(calls, digits // 2) for _ in range(calls))
for digits in (2, 8, 64, 1024):
four = single_digit_products(4, digits)
three = single_digit_products(3, digits)
print(f"{digits} digits: four calls {four}, three calls {three}, ratio {four / three:.1f}")
print(f"log2 3 = {math.log2(3):.3f}")2 digits: four calls 4, three calls 3, ratio 1.3
8 digits: four calls 64, three calls 27, ratio 2.4
64 digits: four calls 4096, three calls 729, ratio 5.6
1024 digits: four calls 1048576, three calls 59049, ratio 17.8
log2 3 = 1.585On 1,024 digits the four-call version makes 1,048,576 single-digit multiplications and Karatsuba's makes 59,049, almost 18 times fewer, and the gap widens as the numbers grow. Real implementations stop recursing well before single digits, because for short numbers the extra additions cost more than the saved multiplication. CPython uses the school method unless both integers are longer than 70 of its internal digits, about 630 decimal digits, and Java's BigInteger switches to Karatsuba once both numbers exceed 80 ints.
Two slips are common. Answering O(n log n) for the three-call version matches it to merge sort by shape and ignores a. Expecting the four-call version to beat the school method forgets that four calls on halves leave n² leaves, exactly the school method's n² digit products.
← → move through sections and cards