Mathematics: Karatsuba Algorithm

[last updated: 2021-08-01]
go to: ...
-----

• The Karatsuba algorithm is used to multiply very large integers. It is generally faster when the operands are larger than 500 digits (very approximate)

• given two large numbers, x & y
  set n = number of digits of the larger one
  set m = (n // 2) + 1
• Then:
  x = x₁ x 10^m + x₀
  y = y₁ x 10^m + y₀
• Calculate interim quantities:
  z₀ = x₀ y₀
  z₁ = x₁ y₀ + x₀ y₁
  z₂ = x₁ y₁
• Then:
  x y = z₂ * 10^2m + z₁ * 10^m + z₀
  -------------------------------------------------------------------------

• For example:
  • x = 12345
    y = 6789
  • n = 5
    m = 3
  • x = 12 x 10³ + 345
    y = 6 x 10³ + 789
    Or:
    x₁ = 12
    x₀ = 345
    y₁ = 6
    y₀ = 789

  • z₀ = x₀ y₀
    z₀ = 345 * 789 = 272205

    
    z₁ = x₁ y₀ + x₀ y₁
    z₁ = (12 * 789) + (345 * 6) = 11538

    
    z₂ = x₁ y₁
    z₂ = 12 * 6 = 72
    

  • x y = z₂ * 10^2m + z₁ * 10^m + z₀
          = 72 * 10⁶ + 11538 * 10³ + 272205
          = 72,000,000 + 11,538,000 + 272,205
          = 83,810,205

• In the python program I wrote to implement this algorithm, it performed 20x slower than standard multiplication for operands up to about 30-digits.

.

.

.

eof