Karatsuba Multiplication for unequal size, non-power-of-2 operands

Question

What's the most efficient way to implement Karatsuba large number multiplication with input operands of unequal size and whose size is not a power of 2 and perhaps not even an even number? Padding the operands means additional memory, and I want to try and make it memory-efficient.

One of the things I notice in non-even-number size Karatsuba is that if we try to divide the number into "halves" as close to even as possible, one half will have m+1 elements and the other m, where m = floor(n/2), n being the number of elements in the split number. If both numbers are of the same odd size, then we need to compute products of two numbers of size m+1, requiring n+1 storage, as opposed to n in the case when n is even. So am I right in guessing that Karatsuba for odd sizes may require slightly more memory than for even sizes?

Nudicaul

This prior SO question provides some implementation details that might help – Gracchus

Answer 1

Most of the time, length of operands will not be a power of 2. I think this is rare case. Most of the time there will be different lengths of operands. But this will not be a problem for a Karatsuba algo.

Actually, I don't see any problem here. This overhead (odd length) is so light and definitely not a big deal. Problem about different lengths - let's assume, that X = 1234 and Y = 45

So, a = 12, b = 34, c = 0, d = 45 So, after that X * Y = 10 ^ 4 * ac + 10 ^ 2 (ad + bc) + bd

ac = 0;
bd = 34 * 45;
ad + bc = (a + b) * (c + d) - ac - bd = 540;

And, if we assume, that we could multiply 2 digit numbers easily - you could get the answer = 55530. Same, as just multiply 1234 * 45 in any calculator :) So, I can't see any memory issue with different lengths of numbers.

Lubalubba

if x = 123 then how you can divide the number into two portion ? – Plafond

a = 1, b = 23, i guess. – Lubalubba

Nop,,I think this algorithm won't work if n bit number is odd digits number – Plafond

@Plafond can you check my solution – Mining

Answer 2

You can multiply the numbers by powers of 10 so that each of them have even numbers of digits. Apply karatsuba algorithm and them divide the answer by the the factor of powers of 10 that you multiplied the original 2 numbers to make them even.

Eg: 123*12

Compute 1230*1200 and divide the answer with 1000.

Mining

Answer 3

To answer your doubt in comments above. Trick is to follow the formula to calculate powers of 10 in case of decimal calculation.

10^2m(A.C) + 10^m((A+B).(C+D)-A.C-B.D) + B.D

m = n/2 + n%2

n is length of number

Refer to wiki it explains in details.

Ehf

n is length of number - of which of 2 multiplied numbers? – Cap