1樓：
一種想法是假如你想算f*g,那麼實際上你需要算的是Tf*g,其中Tf是以f的係數為symbol的toeplitz matrix。之後就可以用ifft(fft(f).*fft(g))算了。
另一種簡單的理解是convolution的算符在傅利葉變換以後就是按位相乘的運算。
週末有時間再仔細寫寫。
果然wiki還是很好用的。
傳送門：
英文版：
Cooley
講的細到我都不想搬運到知乎來了……本質上就是變換的時候奇偶分離，奇數做奇數的fft，偶數做偶數的fft，然後奇偶的部分自己又可以根據奇偶分成兩部分。類似quicksort。
2樓：
點值表達就是多項式可以用某些點的座標來唯一的確定，例如三個點確定一條二次曲線。所以，給定一些點的座標，如果它們能唯一確定乙個多項式，就可以看成是這個多項式的一種表示形式。一般地，n+1個點可以確定一條n次曲線。
當然，更多的點也可以，比如你可以取2n個點（然而這並沒有什麼卵用）。
兩個多項式f和g如果都是n-1次的，那麼可以在兩條曲線的相同位置取2n個點，比如都取0, 1, 2, ..., 2n-1這些點的函式值。然後你就可以算出來f*g在這些點處的值，比如f*g(0) = f(0) * g(0)等，只需要2n次乘法即可確定f*g在這些點處的值，就得到了f*g的乙個點值表達。
而f*g最多是乙個2n-2次多項式，2n個點完全可以唯一確定f*g，只不過結果需要轉換成常用的係數表示而已。
要快速在點值表示和係數表示之間轉化，就需要選一些特殊的點（就是復平面上的單位根、有限域上的原根等等），這樣很多冪運算的結果都相同，就能重複利用了。至於怎麼利用這種重複性減小運算量，你還是好好看書吧，一兩句話說不清楚。先看遞迴的寫法，解遞迴式弄明白複雜度；然後再看蝶形運算，利用位運算構建蝶形網路非遞迴地寫出來效率更高的FFT程式。
請懂茶葉的大神給深入淺出的講講茶葉都有哪些類別和功效？
蔓草 那我就主動地拋磚引玉啦！茶葉的分類，根據茶葉特有功能性物質 茶多酚 的氧化發酵程度而分為六大茶類。綠茶，屬不發酵茶，即鮮葉採回後高溫殺青處理，殺死了鮮葉中的氧化酶 酶是蛋白質，遇高溫而失去活性 茶多酚不曾經過氧化。白茶，屬輕發酵茶，即鮮葉採回後，擺在那裡不動讓鮮葉緩慢失去水分，該過程中，多酚類...
有哪些深入淺出講專案管理的好書？
我愛專案管理 其實專案管理的書很多，但多是翻譯外國的書籍，其專案管理的理念和中國國內是不一樣的，國外的邏輯性強，但缺少軟性，看完覺得很有道理，但很難用於實戰。推薦以下幾本，接地氣的實戰書，夠了 V先生的日常 1.專案管理知識體系指南 PMBOK指南 第六版中文版 2.商業分析實踐指南中文版 3.敏捷...
土木工程有什麼深入淺出的專業書推薦？
就看註冊考試相關參考資料，其他的都沒意思。先過基礎 二註，再過一注。過了註冊規範熟悉了，錢也有了，轉行或者繼續熬，隨便。 這方面我建議不僅看國內一些經典書籍，同時關注國外書籍，國外有很多深入淺出的經典教材，只需要google加書籍名稱，會有意想不到的收穫，本人主要隧道火災領域，tunnel fire...