patternMinor
Karatsuba multiplication on numbers with odd length
Viewed 0 times
karatsubamultiplicationwithlengthnumbersodd
Problem
I am learning about Karatsuba-Ofman multiplication. I don't quite understand how to multiply two numbers with odd length.
Let's take two 3-digit numbers $a = 234; b = 857$ with base $B = 10$ and length $n=3$.
The first step is to split split $a$ and $b$ at position $n/2$. However, since $n=3$ where do I split it? Does it even matter?
Later in the algorithm I have to multiply $((a_1 + a_0) \cdot (b_1 + b_0) - (a_1 \cdot b_1) - (a_0 \cdot b_0)) \cdot B^{n/2}$. Would that mean, with $n=3$, I have to multiply by $B^{1.5}$?
Let's take two 3-digit numbers $a = 234; b = 857$ with base $B = 10$ and length $n=3$.
The first step is to split split $a$ and $b$ at position $n/2$. However, since $n=3$ where do I split it? Does it even matter?
Later in the algorithm I have to multiply $((a_1 + a_0) \cdot (b_1 + b_0) - (a_1 \cdot b_1) - (a_0 \cdot b_0)) \cdot B^{n/2}$. Would that mean, with $n=3$, I have to multiply by $B^{1.5}$?
Solution
Here, $B = 10$ and $n = 3$. The Karatsuba method works for any $m < n$. With $m = 2$ :
$a = 2 * 10^2 + 34$
and
$b = 8 * 10^2 + 57$
; thus, $a_1 = 2$, $a_0 = 34$, $b_1 = 8$ and $b_0 = 57$.
It follows that $ab = z_2 B^{2m} + z_1 B^m + z_0$ where $z_2 = a_1 b_1 = 16$, $z_1 = a_1 b_0 + a_0 b_1 = 386$ and $z_0 = a_0 b_0 = 1938$.
Thus, $ab = 16 \cdot 10^{2*2} + 386 \cdot 10^2 + 1938 = 200538$.
I'm not sure about the step you mentioned, as it doesn't seem to give the correct result with the current decomposition ($m = 2$).
$a = 2 * 10^2 + 34$
and
$b = 8 * 10^2 + 57$
; thus, $a_1 = 2$, $a_0 = 34$, $b_1 = 8$ and $b_0 = 57$.
It follows that $ab = z_2 B^{2m} + z_1 B^m + z_0$ where $z_2 = a_1 b_1 = 16$, $z_1 = a_1 b_0 + a_0 b_1 = 386$ and $z_0 = a_0 b_0 = 1938$.
Thus, $ab = 16 \cdot 10^{2*2} + 386 \cdot 10^2 + 1938 = 200538$.
I'm not sure about the step you mentioned, as it doesn't seem to give the correct result with the current decomposition ($m = 2$).
Context
StackExchange Computer Science Q#75099, answer score: 5
Revisions (0)
No revisions yet.