When working with 8-bit numbers, multiplying two 8-bit values results in a 16-bit product. However, using the Karatsuba algorithm, calculating the product of two 8-bit numbers, X and Y, involves intermediate results that overflow 8 bits.
Let's denote the 8-bit components of X and Y as follows:
X = x0 + x1<<8 Y = y0 + y1<<8
The resulting product, Z, can be expressed as:
Z = X * Y = z0 + z1<<8 + z2<<16
The partial products, z0, z1, and z2, have the following bit widths:
z2 = x1 * y1 -> 16 bits z1 = x1 * y0 + x0 * y1 -> 17 bits z0 = x0 * y0 -> 16 bits
As you can see, z1 overflows 8 bits, reaching 17 bits due to the maximum value it can hold: 65025 + 65025 = 130050.
To handle this overflow, the algorithm employs a technique called "Carry Propagation." Essentially, the lowest 8 bits of each partial product are retained, and the remaining bits are added to the higher digits.
z1 += z0 >> 8; z0 &= 255; z2 += z1 >> 8; z1 &= 255; z3 = z2 >> 8; Z = z0 + z1<<8 + z2<<16 + z3<<24
Modern hardware implementations of multiplication often handle this overflow automatically, providing the result as two words instead of one. This means that the result of a 16-bit multiplication is a 32-bit value.
When adding the 8-bit sub-products, it's important to use at least 10 bits to accommodate the possibility of adding three numbers simultaneously. Alternatively, you can add them one by one with 9 bits (or 8 bits plus 1 carry).
In the case of signed values, an additional bit is needed to represent the sign. To avoid this, it's common practice to remember the signs of the operands, use their absolute values for the multiplication, and then assign the appropriate sign to the result based on the original signs.
For more in-depth information, refer to the following resources: