Skip to main content
MathOverflow

Return to Question

Became Hot Network Question
Made the question even more concise
Source Link
WiccanKarnak
WiccanKarnak
  • 153
  • 5

Can there exist an algorithm Process quicker than Fast Fourier Transform to square a polynomial?for squares of polynomials

FFT is a quick algorithm for multiplying two polynomials, but given it's a square (i.e. multiplying the polynomial with itself) can we find something better? (I reached a paper by Jaewook Chung and M. Anwar Hussain, and then to something known as Toom-Cook algorithm, but can't find anymore claims)

Can there exist an algorithm quicker than Fast Fourier Transform to square a polynomial?

FFT is a quick algorithm for multiplying two polynomials, but given it's a square (i.e. multiplying the polynomial with itself) can we find something better? (I reached a paper by Jaewook Chung and M. Anwar Hussain, and then to something known as Toom-Cook algorithm, but can't find anymore claims)

Process quicker than Fourier for squares of polynomials

FFT is a quick algorithm for multiplying two polynomials, but given it's a square (i.e. multiplying the polynomial with itself) can we find something better?

Source Link
WiccanKarnak
WiccanKarnak
  • 153
  • 5

Can there exist an algorithm quicker than Fast Fourier Transform to square a polynomial?

FFT is a quick algorithm for multiplying two polynomials, but given it's a square (i.e. multiplying the polynomial with itself) can we find something better? (I reached a paper by Jaewook Chung and M. Anwar Hussain, and then to something known as Toom-Cook algorithm, but can't find anymore claims)