Multiplication and Division: From Grade School to Karatsuba

Egyptians, Karatsuba, and One Disproved Kolmogorov

Ancient Egyptians had no multiplication table. Instead: only **doubling and addition**. To compute 13 x 17, repeatedly double 17, select the right rows, add. This is exactly how modern CPUs work - through bit shifts and additions. The Egyptian method is binary multiplication, discovered 5000 years before the binary number system.

The Karatsuba algorithm runs inside Python's bigint (numbers larger than ~70 digits), OpenSSL's RSA implementation, and GNU GMP. Every time Python computes 10**1000, Karatsuba runs.

1960. Moscow. Kolmogorov declares that n^2 is the theoretical minimum for multiplying n-digit numbers - a mathematical wall. One week later, graduate student Karatsuba walks in with O(n^1.585). Kolmogorov cancels his seminar and publishes the student's result. Behind every torch.mm, every CUDA core, and every RSA key is that moment.

• **GPU matrix multiply**: CUDA cores execute 10,000+ parallel multiplications. Every transformer forward pass is thousands of GEMM operations. Optimizing multiplication optimizes all of deep learning
• **RSA-4096**: multiplying two 1000-digit numbers naively costs 10^6 operations. Karatsuba costs ~10^4.75. For a 4096-bit key the difference is billions of operations per encryption
• **Python bigint**: `(10**500) * (10**500)` uses Karatsuba automatically - CPython switches at numbers larger than ~70 digits
• **NumPy broadcasting**: `np.dot(A, B)` for 1000x1000 matrices calls BLAS, which uses blocked algorithms and SIMD - not naive O(n^3)

The Naive Algorithm: Grade-School n-Squared

**1960. Moscow. Kolmogorov - one of the greatest mathematicians of the 20th century - publicly declares**: multiplying two n-digit numbers requires at least n^2 operations. The grade-school algorithm makes this intuitive: every digit of the first number against every digit of the second. Two k-digit numbers: k x k = k^2 multiplications. Kolmogorov called it optimal. He was wrong.

**Multiplication** is shorthand for repeated addition: a x n = a + a + ... + a (n times) where a is the multiplicand, n is the multiplier, and the result is the **product**. **Grade-school algorithm**: multiply each digit of the first number by each digit of the second. Two n-digit numbers = O(n^2) elementary multiplications.

**Why does minus times minus give plus?** Formally: (-1) x (-1) = 1 is the only value that preserves distributivity across the ring of integers. This is not a convention - it is a consequence of the axioms. Distributivity, it turns out, is also the key that Karatsuba used to break the n^2 barrier.

**NumPy under the hood**: `np.dot(a, b)` for two 1000x1000 matrices is 10^9 multiplications. NumPy calls BLAS, which uses vectorized CPU instructions and cache-optimized blocking - not naive O(n^3). The grade-school algorithm stops being viable at matrices larger than 10x10.

Division: The Inverse Operation and Newton-Raphson

**Division** answers: how many times does one number fit into another? It is the inverse of multiplication - just as subtraction inverts addition. Knowing the multiplication table automatically gives the division table. But on CPUs, division is implemented separately and runs 10-30x slower than multiplication.

**Division** is the inverse of multiplication: a / b = c means c x b = a where a is the dividend, b is the divisor, c is the quotient. **Important:** division by zero is undefined! **On CPUs**: division is 10-30x slower than multiplication. Compilers replace constant-divisor division with multiplication by a magic constant at compile time.

Modern CPUs implement division via **Newton-Raphson iteration**: iteratively refine the reciprocal 1/b, then multiply by a. This converts slow division into fast multiplications. GCC and Clang do exactly this for constants - they replace `x / 7` with `x * 0x24924925 >> 33` at compile time.

Properties and Distributivity: The Foundation of Algorithms

Multiplication has convenient properties. Division, like subtraction, loses them. But the key property - **distributivity** - is not just a mental-math shortcut. It is the foundation of Karatsuba's algorithm, matrix multiplication, and FFT.

**Distributivity** is the key property for mental calculation: 7 x 12 = 7 x (10 + 2) = 70 + 14 = 84 99 x 5 = (100 - 1) x 5 = 500 - 5 = 495 **Karatsuba 1960**: distributivity lets two large numbers be multiplied with 3 sub-multiplications instead of 4. That is the step from O(n^2) to O(n^1.585).

**Karatsuba in one paragraph**: split A and B in half: A = a1*10^m + a0, B = b1*10^m + b0. Naive: 4 multiplications (a1b1, a0b0, a1b0, a0b1). Karatsuba: compute a1b1, a0b0, and (a1+a0)(b1+b0) - recover all four products from three via addition. Recursion yields O(n^1.585). One week after Kolmogorov's public announcement - Karatsuba delivered the proof.

Division with Remainder and Modular Arithmetic

17 candies split among 5 children - each gets 3, with 2 left over. That is **division with remainder**. Elementary on the surface. But the remainder operation `%` is the foundation of hash tables, cryptography, and error-correction codes. RSA lives entirely in modular arithmetic.

**Division with remainder:** a = b x q + r where a is the dividend, b is the divisor, q is the quotient, r is the remainder. **Condition:** 0 <= r < b (the remainder is always less than the divisor)

Division with remainder is the foundation of **modular arithmetic**. RSA encryption: encrypting message m with key e means computing m^e mod n. For 4096-bit numbers this requires thousands of modular multiplications. The speed of public-key cryptography depends directly on the speed of multiplication.

Key Ideas

• Multiplication is shorthand for repeated addition; grade-school algorithm is O(n^2)
• Karatsuba 1960: distributivity gives O(n^1.585) - Python uses it automatically for bigint
• Division is the inverse; on CPUs it is 10-30x slower than multiplication - compilers replace constant divisors
• Division with remainder: a = b x q + r, 0 <= r < b - foundation of hashes, RSA, and error correction

Related Topics

Multiplication and division open the door to new concepts:

• Order of Operations — Multiplication is performed before addition
• Divisibility — When the remainder equals zero - GCD and LCM
• Fractions — Division that does not produce a whole number
• Modular Arithmetic — Remainders as a self-contained number system; foundation of RSA

Вопросы для размышления

• Why is multiplication commutative (3 x 7 = 7 x 3) even though '3 groups of 7' and '7 groups of 3' look different visually?
• Karatsuba reduces 4 sub-multiplications to 3 using distributivity. Could it be reduced to 2? Why or why not?
• Compilers replace `x / 7` with multiplication by a magic constant. How does this trick work, and what are its limits?

Связанные уроки

• ar-05-order — Order of operations: multiplication before addition
• ar-13-divisibility — Divisibility - remainders and factorization
• ar-28-modular — Modular arithmetic: the foundation of cryptography
• ar-26-binary — Binary multiplication - the same Egyptian method
• ar-44-crypto-intro — RSA-4096: multiplication is the bottleneck
• ar-45-computer-arithmetic — BLAS, GPU GEMM - industrial-scale multiplication
• prob-01-intro