DevJourney · code I wrote while learning

README.md

Karatsuba Integer Multiplication (Divide & Conquer)

Problem

  • Multiply two large integers faster than the naive O(n^2) schoolbook algorithm.

Key idea (intuition)

  • Split each n-digit number into high and low halves. Instead of four multiplications of halves, compute only three recursive multiplications using the identity:
    • z2 = high1 * high2
    • z0 = low1 * low2
    • z1 = (high1 + low1) * (high2 + low2) - z2 - z0 Combine with appropriate digit shifts to form the full product. This reduces multiplicative work.

Complexity

  • Time: O(n^{log2(3)}) ≈ O(n^{1.585})
  • Space: O(n) (depending on representation and recursion depth)

Worked example

1234 * 5678 = 7006652

The implementation uses string-based splitting and recursive multiplication; it is primarily educational to show divide-and-conquer speedup.

Notes

  • For very large numbers and production code, use FFT-based multiplication (Schönhage–Strassen) or big-integer libraries.

Code: main.cpp — recursive Karatsuba implementation.