In Karatsuba algorithm for multiplying two numbers, we divide each number into two. For example:
x= 1234
y= 2456
Then a = 12, b = 34, c = 24 , d = 56
What if the digits in each number are not even, or the same? What is the rule in dividing it into two parts?
Example:
x = 12345
y = 2478
or
x = 12456778
y = 241
Please help.
The most common approach is to take the longest number, and divide it in half (rounding an odd number of digits arbitrarily). So for
x = 12345
y = 2478
you would get a=12, b=345, c=2, d=478. Since the number of digits in x is not even, we are free to choose whether to split into a=12 and b=345 or a=123 and b=45; it makes no difference to the running time. For your second example
x = 12456778
y = 241
you would get a=1245, b=6778, c=0, d=241.
I think in this case we should pad with zeros up to an even degree of the largest of the two numbers. Suppose that $x \ge y$ and $2^n \le x < 2^{n+1}$. Then one should represent $x, y$ as $$x = x_1\cdot 2^{\lceil \frac{n}{2} \rceil} + x_2, y = y_1\cdot 2^{\lceil \frac{n}{2} \rceil} + y_2$$ and then apply Karatsuba Rule. The total complexity is still $O(n^{\log_23})$
