Integer Multiplication (Karatsuba)

Multiply large integers efficiently - O(n^1.585) complexity

Select Input

Choose a predefined test file or upload your own

Select a test file and click "Run Algorithm" to see the results

Algorithm Information

Karatsuba Algorithm:

For two n-digit numbers x and y:

  1. Split x = a·10^m + b and y = c·10^m + d
  2. Compute z₂ = a × c
  3. Compute z₀ = b × d
  4. Compute z₁ = (a + b) × (c + d) - z₂ - z₀
  5. Result = z₂·10^(2m) + z₁·10^m + z₀

Time Complexity:

O(n^log₂3) ≈ O(n^1.585) - better than traditional O(n²)

Key Insight:

Reduces 4 multiplications to 3, improving asymptotic complexity