Karatsuba’s multiplication algorithm
…or how to multiply really biiiig values
Leave alone the algebraic manipulations the multiplication algorithm itself, though intricate and messy at first glance, is not really hard, but first we need to know how to:
- Convert number from system with base n to binary string
- Add two binary strings
- Subtract two binary strings
Convert to binary string
If you’re not in the mood to deal with all these number systems and want to jump straightly to the decimal to binary part — that’s ok. Long story short…
Successively do these steps while the number is greater than 0:
- append the result of n mod 2 to the resulting string
- divide n by 2
Then
3. reverse the resulting string
Yet, how does this work?
Q: What does it mean for a number to be decimal?
A: It means the number is based in ten.
Q: What does it mean for number to be based in ten?
A: It means each of its digits are smaller than ten and it is the result of summation of the product of its digits and powers of ten.
Number (4321)₁₀ = 4 * 10³ + 3 * 10² + 2 * 10¹ + 1 * 10⁰
Q: What does it mean for a number to be base-b?
A: It means the number is expressed using powers of b
Let n be an integer and b be a base in which we will express number n.
Pick some integers (dₖ … dₖ₋₁… d₀) such that 0 ≤ dᵢ ≤ b, then we can define n to be base-b number:
n = dₖ*b^k + dₖ₋₁*b^k-1 + … + d₁ * b + 0
Then, shall we repeatedly divide n by the biggest power of b such that
n ≥ b^k we will get the remainders corresponding to the place value of the quotients. In other words, we will repeatedly get as quotients the values of dₖ … d₀.
For example, if take the base-10 number 4321:
4 * 10³ + 3 * 10² + 2 * 10¹ + 1 * 10⁰
and divide it by 10³ we will get 4 as quotient, then if divide the remainder of this division
3 * 10² + 2 * 10¹ + 1 * 10⁰
by 10² we will get the quotient 3.
Continuing the division:
(2 * 10¹ + 1)/10¹ = (2 * 10) + 1
(1)/10⁰ = (1 * 1) + 0
This process can also be done in reverse order, starting from the “left”, which means dividing repeatedly by b and writing down the remainder of that division.
1.
(4 * 10³ + 3 * 10² + 2 * 10¹ + 1 * 10⁰) % 10 = 1, since 4321 = (432 * 10) + 1
2.
4321 / 10 = 432
Get Roman’s stories in your inbox
Join Medium for free to get updates from this writer.
3.
(4 * 10² + 3 * 10¹ + 2 * 10⁰) % 10 = 2, sinse 432 = (43 * 10) + 2
4.
432 / 10 = 43
5.
43 % 10 = 3
6.
43/ 10 = 4
7.
4 % 10 = 4
Same procedure works for converting between bases. Consider number 43 defined in binary:
(43)₁₀ = (101011)₂ = (1 * 2⁵ + 0 * 2⁴ + 1 * 2³ + 0 * 2² + 1 * 2¹ + 1 * 2⁰)
By repeatedly dividing the base-2 defined sequence by 2 we will get the binary quotients 101011. Same works for converting to any base.
Add and Subtract two binary strings
Rules for adding two bits are:
- 0 + 0 = 1
- 0 + 1 = 1
- 1 + 1 = 0
The logic behind the third case is that 1 + 1 is 2 that has a binary representation of (10)₂, so we carry over the redundant 1 to the left.
In terms of implementation, we keep a carry variable, initially set to 0, and at each step we take the sum of three bits: first bit, second and a carry. At the end we append the carry, if any, to the resulting string.
By associative property:
i. 1 + 1+ 1 = 1 + (1 + 1) = 1 + (0) (with carry = 1) = (11)₂
ii. 1 + 0 + 1= 0 + (1 + 1) = 0 + (0) (with carry = 1) = (10)₂
Rules for subtracting two bits are:
- 1–1=0
- 1–0=1
- 0–1 = 1
Again, let’s go over the third case. Since 0 is smaller than one, we have to borrow from the left, e.g:
(10)₂–(1)₂ = (02)₂-(1)₂ = 1
It’s counterintuitive, but as you can see, 0 after borrowing becomes 2, not 1. This explains why 0–1 = 1.
Divide and Conquer multiplication algorithm
Every number x can be expressed in the form
x = a* k^(n/2) + b, where n is number of digits of x, k is the base, a is the first n/2 digits and b is the second n/2 digits. For example, number (123456)₁₀ and (4789)₁₀ can be expressed as
123456 = 123 * 10³ + 456
4789 = 47 * 10² + 89
What does this give us? We can now algebraically manipulate new expressions to multiply them.
(a*k^(n/2) + b) * (c * k^(n/2) + d) =
ac * k^(2(n/2)) + (ad + bc) * k^(n/2) + bd
Then we calculate the values of ac, (ad + bc), bd recursively, but there is a trick. We don’t need to calculate ad and bc separately.
(ad + bc) = ((a + b) * (c + d))-ac-bd
So, we first recursively compute values of ac and bd to then get the value of (ad + bc).
