Karatsuba Algorithm - DAA Visualizer

Input Numbers

Number 1

Number 2

Recursive Decomposition

Level 0

Level 1

Level 2+

Click "Play" or "Step" to begin visualization

Speed:

Set your numbers and click "Play" to begin.

Statistics

Steps

Max Depth

Time Complexity

O(n^log₂3) ≈ O(n^1.585)

Calculation Steps

No calculations yet

Pseudocode

function karatsuba(x, y):
  if x < 10 or y < 10:
    return x × y
  n = max(size(x), size(y))
  m = n / 2
  high1 = x / 10^m
  low1 = x mod 10^m
  high2 = y / 10^m
  low2 = y mod 10^m
  z0 = karatsuba(low1, low2)
  z1 = karatsuba(high1+low1, high2+low2)
  z2 = karatsuba(high1, high2)
  return z2×10^(2m) + (z1-z2-z0)×10^m + z0

Algorithm Visualization

Input Numbers

Recursive Decomposition