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.
History[편집 | 원본 편집]
Karatsuba multiplication was discovered by the Russian mathematician Anatolii Alexeevitch Karatsuba in 1960. The algorithm was first presented at a seminar by Andrey Kolmogorov, who initially believed that the standard multiplication method of O(n²) was the best possible. However, Karatsuba demonstrated a faster method, reducing the number of multiplications required. This discovery laid the foundation for modern fast multiplication algorithms.
Steps[편집 | 원본 편집]
- 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.
- Recursive Multiplication:
- Compute three products instead of four:
- AC = A × C
- BD = B × D
- AD + BC = (A + B) × (C + D) - AC - BD
- Compute three products instead of four:
- Combine:
- Result = AC × 10^(2m) + (AD + BC) × 10^m + BD
Example[편집 | 원본 편집]
Consider multiplying 1234 × 5678 using Karatsuba’s method:
- Divide:
- X = 1234 → A = 12, B = 34
- Y = 5678 → C = 56, D = 78
- 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
- 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.