Skip to content

Instantly share code, notes, and snippets.

@joelonsql
Created April 16, 2024 17:34
Show Gist options
  • Save joelonsql/a331f0c0d4a97972e3e16bc3c46280dc to your computer and use it in GitHub Desktop.
Save joelonsql/a331f0c0d4a97972e3e16bc3c46280dc to your computer and use it in GitHub Desktop.
The Half-Karatsuba Multiplication Algorithm

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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment