1

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

Spektre
  • 49,595
  • 11
  • 110
  • 380
Kolyx akos
  • 13
  • 2

1 Answers1

2

lest consider positive numbers only for starter. lets have 8 bit numbers/digits x0,x1,y0,y1.

When we apply 8bit multiplication:

x0*y0 -> 8bit * 8bit -> 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 8bit. 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 Cant make value propagate through carry

So the result of 16 bit multiplication is 32 bit. Beware that for adding the 8bit 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:

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • Thank u so much..except I still dont understand why z1 is a 17 bit top value..where does the 1 bit come from..thank u ♥ – Kolyx akos Dec 18 '17 at 19:05
  • @Kolyxakos if you add two `1bit` numbers you get up to `2bit` number. now `z1 = 16bit + 16bit = 17bit`. You can see it like when you add two similar values the output is roughly twice as big value so it need one more bit to store. – Spektre Dec 18 '17 at 19:09