Search code examples
algorithmkaratsubaprogrammers-notepad

Karatsuba Algorithm Overflow

I've been studying Karatsuba's algorithm on Wikipedia and I stopped at this section that confused me ..Why is there an overflow in this algorithm , I don't understand the steps he made to resolve this issue .here is a screenshot of my problem

screenshot

Solution

  • Let's consider positive numbers only for starter. Let's have 8 bit numbers/digits x0,x1,y0,y1.

    When we apply 8 bit multiplication:

    x0*y0 -> 8 bit * 8 bit -> 16 bit

    It will produce up to 16 bit result. The top value is:

    FFh*FFh = FE01h
255*255 = 65025

    Now if we return to Karatsuba let

    X = x0 + x1<<8
Y = y0 + y1<<8
Z = X*Y = z0 + z1<<8 + z2<<16

    Now lets look at the bit width of zi

    z2 = x1*y1         -> 16 bit
z1 = x1*y0 + x0*y1 -> 17 bit
z0 = x0*y0         -> 16 bit

    Note that z1 is 17 bit as top value is

    65025+65025 = 130050

    So each of the zi overflows the 8 bit. To handle that you simply take only the lowest 8 bits and the rest add to higher digit (like propagation of Carry). So:

    z1 += z0>>8;   z0 &= 255;
z2 += z1>>8;   z1 &= 255;
z3  = z2>>8;
Z = z0 + z1<<8 + z2<<16 + z3<<24

    But usually HW implementation of the multiplication handles this on its own and give you result as two words instead of one. See Can't make value propagate through carry

    So the result of 16 bit multiplication is 32 bit. Beware that for adding the 8 bit sub results you need at least 10 bits as we are adding 3 numbers together or add and propagate them one by one with 9 bits (or 8 bits + 1 carry).

    If you add signed values to this you need another one bit for sign. To avoid it remember signs of operands and use abs values ... and set the sign of result depending on the original signs.

    For more details see these: