Karatsuba Algorithm Overflow Handling
Consider positive 8-bit numbers x0, x1, y0, y1. When applying 8-bit multiplication, the result can be up to 16 bits. The top value is FFh * FFh = FE01h.
Using Karatsuba's algorithm, let X = x0 + x1<<8, Y = y0 + y1<<8, and Z = X * Y = z0 + z1<<8 + z2<<16.
The bit widths of zi are as follows:
z2 = x1 * y1 -> 16 bit z1 = x1 * y0 + x0 * y1 -> 17 bit z0 = x0 * y0 -> 16 bit
Note that z1 is 17 bits, with a top value of 65025 + 65025 = 130050.
To handle overflow, take only the lowest 8 bits of each zi and add the rest to the higher digit. This is like propagating the carry.
z1 += z0 >> 8; z0 &= 255; z2 += z1 >> 8; z1 &= 255; z3 = z2 >> 8; Z = z0 + z1<<8 + z2<<16 + z3<<24
Usually, hardware multiplication handles this automatically, resulting in two words instead of one.
For signed values, remember the signs of operands and use absolute values, setting the result's sign based on the original signs.
For more details, refer to these resources: