Tag Archives: complexity theory

Polynomial Multiplication, Karatsuba and Fast Fourier Transform

Let’s say you want to write a short program to multiply two linear functions f(x) = ax+b and g(x) = cx+d and compute the coefficients of the resulting product: You might think it’ll take 4 multiplications (for ac, ad, bc and bd) and 1 addition (for ad+bc), but there’s … Continue reading

Posted in Notes | Tagged , , , , , | Leave a comment