# Karatsuba Multiplication Rule in dividing a Number in two parts

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.

## 2 Answers

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