Karatsuba Multiplication

Karatsuba Multiplication is a divide-and-conquer algorithm used for fast multiplication of large numbers. It reduces the number of necessary multiplications compared to traditional long multiplication, making it more efficient for large inputs.

Algorithm Overview

Karatsuba multiplication breaks two n-digit numbers into smaller parts and recursively computes their product using fewer multiplications.

Steps

1. Divide: Split two n-digit numbers into two halves.
   • Let X and Y be two numbers of length n.
   • Represent them as:
     • X = 10^m * A + B
     • Y = 10^m * C + D
   • where A, B, C, and D are approximately n/2-digit numbers.
2. Recursive Multiplication:
   • Compute three products instead of four:
     • AC = A × C
     • BD = B × D
     • AD + BC = (A + B) × (C + D) - AC - BD
3. Combine:
   • Result = AC × 10^(2m) + (AD + BC) × 10^m + BD

Example

Consider multiplying 1234 × 5678 using Karatsuba’s method:

1. Divide:
   • X = 1234 → A = 12, B = 34
   • Y = 5678 → C = 56, D = 78
2. Recursive Multiplication:
   • AC = 12 × 56 = 672
   • BD = 34 × 78 = 2652
   • (A + B) × (C + D) - AC - BD = (12+34) × (56+78) - 672 - 2652
   • = 46 × 134 - 672 - 2652 = 6164 - 672 - 2652 = 2840
3. Combine:
   • Result = 672 × 10^4 + 2840 × 10^2 + 2652 = 7006652

Time Complexity

• Traditional multiplication: O(n²)
• Karatsuba multiplication: O(n^(log₂3)) ≈ O(n^1.585)

Advantages

• More efficient than traditional multiplication for large numbers.
• Reduces the number of recursive multiplications from 4 to 3.

Limitations

• Overhead for small numbers due to recursion.
• Memory usage increases as recursion depth grows.

Applications

• Cryptography: Used for large integer multiplication in encryption algorithms.
• Big Number Arithmetic: Essential in high-precision computations.
• Polynomial Multiplication: Applied in symbolic computation and computer algebra.
• Fast Fourier Transform (FFT)-based Computations: Used in efficient multiplication techniques.

See Also

• Divide-and-Conquer Algorithm
• Fast Multiplication
• Strassen Algorithm
• FFT Multiplication
• Computational Complexity