Karatsuba's Algorithm for multiplying two large numbers

 

An implementation of Karatsuba's Algorithm for multiplying two large numbers. This method is more efficient than the traditional multiplication approach, particularly for very large numbers, as it reduces the number of multiplication operations.

How Karatsuba's Algorithm Works:

1. Split the numbers:

Ø  The two numbers x and y are split into two parts: a higher-order part (a and c) and a lower-order part (b and d).

Ø  x = a * 10^n/2 + b

Ø  y = c * 10^n/2 + d

2. Recursive Multiplication:

Ø  Karatsuba's algorithm computes three products:

• ac = karatsuba(a, c)
• bd = karatsuba(b, d)
• (a + b)(c + d) - ac - bd to calculate the cross terms, which is equivalent to ad + bc.
2. Recombine the results:

Ø  The result is computed as: \(x×y=ac×10^{2n}+(ad+bc)×10^{n}+bd\)

This step puts the computed pieces back together to get the final result.

Detailed Code Walkthrough:

1. Base Case:

Ø  If either x or y is less than 10, the algorithm simply multiplies them directly. This is the base case for the recursion.

2. Splitting the Numbers:

Ø  The numbers x and y are split at the midpoint, where n is the length of the largest number. This allows the number to be divided into a (higher-order digits) and b (lower-order digits).

3. Recursive Calls:

Ø  The algorithm makes three recursive calls to compute ac, bd, and ad + bc.

4. Recombination:

Ø  The three results (ac, bd, and ad + bc) are combined using the formula: $$x×y=ac×10^{2n}+(ad+bc)×10^{n}+bd$$

 

Explanation with math example:

Let's go through a mathematical example to understand Karatsuba's Algorithm in detail.

Suppose we want to multiply:

x=1234 and y=5678

Step 1: Split the numbers

Split x and y into two parts, each with half the number of digits:

\(x=a×10^{n}+b=12×10^{2}+34\)  (where a=12,b=34)

\(y=c×10^{n}+d=56×10^{2}+78\)  (where c=56,d=78)

 

Step 2: Apply Karatsuba's Formula

Karatsuba's algorithm computes the following three products:

1. Compute ac:

ac=a×c=12×56=672

2. Compute bd:

bd=b×d=34×78=2652

3. Compute (a + b)(c + d) - ac - bd: First, calculate the sums:

a+b=12+34=46

c+d=56+78=134

Now, multiply these sums:

(a+b)(c+d)=46×134=6164

Finally, subtract ac and bd from this result to get the middle term:

(a+b)(c+d)−ac−bd=6164−672−2652=2840

Step 3: Combine the Results

Now, we combine the results using the formula:

\(x×y=ac×10^{2n}+(ad+bc)×10^{n}+bd\)

In this case, n=2, so:

\( x×y=672×10^{4}+2840×10^{2}+2652\)

Simplify:

x×y=6720000+284000+2652=7006652

Thus, the product of 1234×5678 using Karatsuba’s algorithm is:

7006652​

Verification:

If we use traditional multiplication:

1234×5678=7006652

So the result matches!

 

Similar Example Usage:

In the main method:

java

long x = 12345678;

long y = 87654321;

long result = karatsuba(x, y);

System.out.println("Karatsuba Multiplication Result: " + result);

This will multiply 12345678 and 87654321 using Karatsuba's algorithm and print the result.

 

Summary of Karatsuba's Algorithm:

ü  Step 1: Split the numbers into two halves.

ü  Step 2: Compute three smaller multiplications: ac, bd, and (a+b)(c+d)−ac−bd.

ü  Step 3: Recombine the results using the formula \(x×y=ac×10^{2n}+(ad+bc)×10^{n}+bd\).

Java Code Example:

public class KaratsubaMultiplication {       public static long karatsuba(long x, long y) {         if (x < 10 || y < 10) {             return x * y;         }           int n = Math.max(Long.toString(x).length(), Long.toString(y).length());         int halfN = n / 2;           long a = x / (long) Math.pow(10, halfN);         long b = x % (long) Math.pow(10, halfN);         long c = y / (long) Math.pow(10, halfN);         long d = y % (long) Math.pow(10, halfN);           long ac = karatsuba(a, c);         long bd = karatsuba(b, d);         long adbc = karatsuba(a + b, c + d) - ac - bd;           return ac * (long) Math.pow(10, 2 * halfN) + adbc * (long) Math.pow(10, halfN) + bd;     }       public static void main(String[] args) {         long result = karatsuba(12345678, 87654321);         System.out.println("Karatsuba Multiplication Result: " + result);     } }

 

Complexity:

ü  Traditional multiplication: O(n^2).

ü  Karatsuba multiplication:  \(O(n^{1.585})\)≈O(n1.585), making it faster for large numbers.

Advantages of Karatsuba's Algorithm:

Ø  Faster for large numbers: Karatsuba reduces the time complexity from O(n^2) (for traditional multiplication) to O(n^1.585) by reducing the number of recursive multiplications.

Potential Improvements:

Ø  Precision Handling: For large numbers, floating-point arithmetic (Math.pow) could introduce precision issues. You may want to use integer arithmetic for splitting the numbers to avoid potential floating-point rounding errors.

Conclusion:

Karatsuba's algorithm is particularly useful when working with very large numbers, as it reduces the number of recursive multiplication operations compared to the traditional approach. However, for small numbers, regular multiplication might be faster due to the overhead introduced by recursion.