DAA Divide & Conquer Karatsuba

Karatsuba Integer Multiplication — Interactive D&C Tutor

Multiply large integers faster by reducing 4 half-size multiplications to 3. Use Step / Auto to see split → Z0/Z1/Z2 → combine.

← Back

Inputs

Tip: Try 1234 × 5678. We auto-pad digits to a power of 2 (assumption in pseudocode).

X (decimal integer)

Y (decimal integer)

Base B

Auto pad to power-of-2 digits Show combine math (Z1 − Z2 − Z0)

Message

Enter X and Y, then click Start.

Visualization

Step: 0 / 0

Active Call — n = —

pad: — depth: 0

X —

X_H

—

X_L

—

Y —

Y_H

—

Y_L

—

Z0 = Karatsuba(X_L, Y_L)

low × low

—

Z2 = Karatsuba(X_H, Y_H)

high × high

—

Z1 = Karatsuba(X_H+X_L, Y_H+Y_L)

cross via trick

—

Combine

P = Z2·B^(2m) + (Z1 − Z2 − Z0)·B^m + Z0

Result: —

Call Stack (Top = Latest) Depth: 0

Recursion Tree (click to collapse)

Start the simulation to build the tree.

Each node is a Karatsuba(…) call. You should see 3 children: Z0, Z2, Z1.

Watch how the algorithm replaces 4 multiplications with 3 each level.

Live Pseudocode

Highlighted line matches the current step.

Karatsuba(X, Y):
  n = number of digits (assume power of 2)
  if n == 1: return X * Y
  m = n / 2
  (XH, XL) = split X into m high/low digits
  (YH, YL) = split Y into m high/low digits
  Z0 = Karatsuba(XL, YL)
  Z2 = Karatsuba(XH, YH)
  Z1 = Karatsuba(XH+XL, YH+YL)
 cross = Z1 - Z2 - Z0
 P = Z2*B^(2m) + cross*B^m + Z0
 return P

Key idea: compute (XH+XL)(YH+YL) once, then subtract to get the cross term.

Complexity (Quick Visual)

Digits n

n = 16

Compare rough work: Naive ≈ n² multiplications, Karatsuba ≈ n^log2(3).

Naive ~ — Karatsuba ~ — Speedup ~ —

Note

Karatsuba helps most when n is large. For small n, recursion overhead can be slower than schoolbook multiplication.

Karatsuba’s recurrence: T(n)=3T(n/2)+O(n) ⇒ O(n^log₂3) ≈ O(n^1.585).