多項式を評価するための最速の方法があることをどこかで読んだことを覚えています（おそらく誰かがどこを覚えているのを手伝ってくれるでしょうか）。ビエッタの公式、または 0 乗係数が多項式の任意の要素の 0 乗係数の積であるという事実と関係があることを思い出します。
ウィキペディアによると、最速で評価するためのホーナーのスキームだと書かれています。しかし、実際にはそのように評価する必要はまったくなかったと思います-それには何かルーツがありましたか?
私が確かに知っているのは、多項式を評価する方法があり、それを見たときに「ああ、それは賢い」ような感覚を与えるということだけですが、それはそれほど難しくなく、一種の明白です。
私を助けてくれる親切で賢い人はいますか？
これは、「x で P を ... で評価できます」という行に沿ったものであり、多項式の次数で実際の加算と乗算を実際に行う必要を実際に回避する、非常に単純な小さなものがあります。
多項式を複数回評価していますか？多項式は特に単純ですか？次の多項式を考えてみましょう。
f(a) = a^(14)
評価に必要な乗算の数を減らしたい場合は、加算チェーンのべき乗f(a)から最小の加算チェーンを計算できます。
((a × a→b) × b→d) × d × d × b
f(a)これは、 5回の乗算のみを使用して計算できることを示しています。係数が小さい固定多項式の場合、これは大幅な節約になります。ウィキペイダノート：
実際には...最短の加算チェーンのべき乗は、主に、最短のチェーンを事前に計算でき、大きすぎない小さな固定指数に使用されます。
別の方法を変えることができる多くの実際のケースでf(a)は適切かもしれませんが、別の解決策に注意する価値があります！
高速フーリエ変換を探していると思いますが、このPowerPoint on FFTも参照してください。実際、FFT は、O(n log n) であり、Horner アルゴリズムよりも非常に高速な n 個の異なる点で多項式の値を計算する場合に役立ちます。
FFT は単位の n 乗根の累乗で動作し、それらの間の関係を使用します。このため、n 個の異なるポイント値を計算する場合は非常に高速です。