I am trying to figure out a question about Karatsuba's algorithm when multiplying two binary values. I am trying to multiply:
10110110 * 11001000
I need to figure out which subproblems are completed when using Karatsuba's algorithm. I know that the algorithm is
x * y = ((2^n)(xHyH))+(2^(n/2))(xHyL + xLyH) + xLyL
But what does each value represent? How do I go from binary values to xH,yH,xL, and yL? Thanks.
The point is to split your numbers into low and high parts:
x = 10110110b
xh= 1011b
xl= 0110b
x = xh<<4 + xl
The base of number is not important (but all must have the same base) as you handle digits in Karatsuba so you can use any base. You just need to have the operations needed defined on the used base you use. So for example if your number is decadic string you do not need to convert it to binary.
So the point is to zero pad x,y from right either to common power of 2 bit-width in the first run (if not done already) or just to common size in each run to avoid/handle rounding problems while splitting. As the numbers are usually in some kind of register or programming language variable type then they usually already are zero padded. In case of bignums or strings this is not guaranteed.
Then in each step you split your x,y into 2 halves and compute the equation.
The equations involves multiplication so it recursively call the same karatsuba multiplication but now on with half bit-width numbers.
Once you hit computable bit-width of x,y you compute the multiplication directly instead of using Karatsuba (this is usually the highest word bit-width your ALU supports for multiplication).
As you input x,y numbers are already 8 bit which most CPUs can handle directly Karatsuba is not needed. If you do not have multiplication or want just to try the stuff you can subdivide until bit-width 1 and use truth table:
0*0=0
0*1=0
1*0=0
1*1=1
Now the problem is that you need to add chunks of numbers together (after the partial multiplications) which might exceed their bit-width. (if you add two 4 bit numbers the result might be 9 bits) And in the Karatsuba equation you add a lot off stuff so you need to take in mind you need more than just single carry bit (I think two should cut it, I use double increment instead (check overflow twice) which works for me).
Also if you use the limiting ALU bit-width and higher level language (like C/C++) you might not have access to carry at all and need to workaround it for example like this:
Here small example (and some other approaches too):
In case you want to measure speed up take in mind that Karatsuba has bigger overhead than naive O(n^2) multiplication start to be faster only for big enough numbers ...
Now back to your splitting question. All depends how are your numbers stored. So in case of strings you split them with string functions. In case of numbers you have them in some variable which is represented in binary already (on the silicon level) so you can use bit shifts and masks. In case of 8 -> 4 + 4 bits in C++ it is done like this:
x = your number;
xl = x&15; // bitwise AND
xh = x>>4; // shift right arithmetic SRA by 4 bits
where 15 = (1<<4)-1 and 4 is the bit-width you want to split to. So if you want n bit-width you can rewrite to:
x = your number;
n = new bit width (half of x bitwidth)
xl = x&((1<<n)-1); // bitwise AND
xh = x>>n; // shift right arithmetic SRA by 4 bits
You can pass the n in the recursion as operand too and just halve it by n>>=1 and stop on n=0 meaning you already on 1 bit-width and have no reason to split...
