An arithmetic circuit illustrating Karatsuba's algorithm for n=4. The shaded boxes are Karatsuba circuits for n=2. A subtraction node computes the difference of its left input minus its right input.
Cost (= black area) of Karatsuba's algorithm for increasing recursion depths. The image approaches a fractal of dimension log 3=1.59.
An arithmetic circuit computing the FFT for n=8.
Cost of the FFT for increasing recursion depths. The black area is proportional to the total work.
