##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Faster integer multiplication.
Problem: Multiply two -digit numbers.
Grade school: digit operations.
Karatsuba's insight: Split each number into two halves. , .
This needs multiplications. Karatsuba reduces it to :
Recurrence:
By Master Theorem:
This beats for large . Modern libraries use even faster algorithms (Toom-Cook, FFT).
