Karatsuba Multiplication

IT 위키

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[편집 | 원본 편집]

  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[편집 | 원본 편집]