アルゴリズムをよく理解して実行できることを想像してみてください - 手で - 頭のてっぺんから - そして、不自然なトリックを覚えることなく ZK Bookは再び拡張され、今回は高速フーリエ変換、特に数論変換(NTT)を教えています。 NTTアルゴリズムは、O(n log n)時間でn点の多項式を評価します。通常、このような評価にはO(n²)時間がかかります。 高速フーリエ変換にはすでに多数の学習リソースがありますが、満足のいくものではないことがわかりました。 たとえば、非常に一般的な説明は、「多項式を偶数項と奇数項に分割する」ことに依存しており、「いじる因数」と「蝶」を使用します。ただし、これらの方法は、アルゴリズムを説明するのではなく、アルゴリズムを説明する偶然のランダムな発見として現れます。 上記のような特徴は、より深い、そしてはるかに理解しやすい基礎となる概念に付随するものであると考えています。複素数との類推を避けることさえあります。 私たちは、学習の旅のすべてのステップがやる気を起こさせ、すべてのステップが前のステップの些細な延長となるように細心の注意を払いました。したがって、概念的な飛躍や驚きの発見はありません。 章名に怖がらないでください。根底にある原理は基本的な代数にすぎません。 13章を終える頃には、数論変換を手作業で計算できるようになります。 次へリンクします。