0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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})$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.