The Half-Karatsuba Multiplication Algorithm

half_karatsuba.md

Karatsuba Multiplication for factors with significant length disparity.

The Half-Karatsuba Multiplication Algorithm is a specialized case of the normal Karatsuba multiplication algorithm, designed for the scenario where var2 has at least twice as many base digits as var1.

In this case var2 (the longer input) is split into high2 and low1, at m2 (half the length of var2) and var1 (the shorter input), is used directly without splitting.

The algorithm then proceeds as follows:

1. Compute the product z0 = var1 * low2.
2. Compute the product temp2 = var1 * high2.
3. Adjust the weight of temp2 by adding m2 (* NBASE ^ m2)
4. Add temp2 and z0 to obtain the final result.

Proof

The algorithm can be derived from the original Karatsuba algorithm by simplifying the formula when the shorter factor var1 is not split into high and low parts, as shown below.

Original Karatsuba formula:

result = (z2 * NBASE ^ (m2 × 2)) + ((z1 - z2 - z0) * NBASE ^ m2) + z0

Substitutions:

low1 = var1
high1 = 0

Applying substitutions:

z0 = (low1 * low2)
   = (var1 * low2)

z1 = ((low1 + high1) * (low2 + high2))
   = ((var1 + 0) * (low2 + high2))
   = (var1 * low2) + (var1 * high2)

z2 = (high1 * high2)
   = (0 * high2)
   = 0

Simplified using the above substitutions:

result = (z2 * NBASE ^ (m2 × 2)) + ((z1 - z2 - z0) * NBASE ^ m2) + z0
       = (0 * NBASE ^ (m2 × 2)) + ((z1 - 0 - z0) * NBASE ^ m2) + z0
       = ((z1 - z0) * NBASE ^ m2) + z0
       = ((z1 - z0) * NBASE ^ m2) + z0
       = (var1 * high2) * NBASE ^ m2 + z0