joelonsql · April 16, 2024 17:34 · Apr 16, 2024 · Apr 16, 2024 · Apr 16, 2024
diff --git a/half_karatsuba.md b/half_karatsuba.md
@@ -1,4 +1,4 @@
-# Karatsuba Multiplication for factors with significant length disparity
+# 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
@@ -15,22 +15,22 @@ The algorithm then proceeds as follows:
 3. Adjust the weight of temp2 by adding m2 (* NBASE ^ m2)
 4. Add temp2 and z0 to obtain the final result.
 
-*Proof:*
+## 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:*
+**Original Karatsuba formula:**
 
     result = (z2 * NBASE ^ (m2 × 2)) + ((z1 - z2 - z0) * NBASE ^ m2) + z0
 
-*Substitutions:*
+**Substitutions:**
 
     low1 = var1
     high1 = 0
 
-*Applying substitutions:*
+**Applying substitutions:**
 
     z0 = (low1 * low2)
        = (var1 * low2)
@@ -43,7 +43,7 @@ high and low parts, as shown below.
        = (0 * high2)
        = 0
 
-*Simplified using the above substitutions:*
+**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

diff --git a/half_karatsuba.md b/half_karatsuba.md
@@ -1,4 +1,4 @@
-# Karatsuba Multiplication for factors with significant length disparity.
+# 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

diff --git a/half_karatsuba.md b/half_karatsuba.md
@@ -0,0 +1,52 @@
+# 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