給定一個係數向量和一個值，評估一個多項式的最快方法是什麼？

我記得在某個地方讀書（也許有人可以幫助記住它在哪裏），有一種方法是評估多項式最快的方法。有些事情提醒我，它與Vietta的公式有關，或者0-係數是多項式的任何因子的0-冪係數的乘積這一事實。給定一個係數向量和一個值，評估一個多項式的最快方法是什麼？

我知道維基百科說它是Horner評估速度最快的方案。但我記得你實際上並不需要那樣評價 - 它有什麼根源？

我所知道的一切都是有一種評估多項式的方法，當你看到它時，會給你一個「哦，那是聰明的」類型的感覺，但它並不難，而且是顯而易見的。

任何一種或智能足以幫助我？

這是沿着「你可以通過...評估P在x上」的東西，然後有一個非常簡單的小東西，實際上可以避免在多項式階數上進行任何實際的加法和乘法運算。

來源

2011-11-19 Cris Stringfellow

也許更適合在http://math.stackexchange.com/？ –

謝謝。無論如何，關閉這個問題並自動移植它？或者......實際上我只是看着那裏，我會在這裏抓住機會。編輯以使其更加適合。...... –

您是否多次評估多項式？多項式特別簡單嗎？考慮以下多項式：

f(a) = a^(14)

如果我們要減少我們可以計算從addition-chain exponentiation最小加法鏈評估f(a)所需的乘法的數量：

((a × a→b) × b→d) × d × d × b

這都說明，我們可以使用計算f(a)只有5次乘法。對於具有小系數的固定多項式，這可以節省顯着的成本。 Wikipeida說明：

實踐中...最短加法鏈指數主要用於小型固定指數，其中最短的鏈可以預先計算，並且不是太大。

對於f(a)可以改變的許多現實世界的情況可能適用另一種方法，但值得注意的替代解決方案！

來源

2012-05-10 20:58:48 Hooked

有趣。→（箭頭）符號表示什麼？哦，我看到這是一個可變的保存。這真是令人着迷！非常感謝你讓我接觸到這一點。從現在開始我想知道：尋找任意指數的最短加法鏈的快速方法是什麼？我認爲二進制方法總是最快的。這是真正具有開創性的，因爲它涉及到我正在考慮的其他事情......向您展示了多麼危險的假設！我甚至不知道是否有比二進制更快的方法。燦爛的@掛鉤！ –

@CrisStringfellow就我所知，沒有找到_shortest_ addition鏈的多項式時間解，儘管我知道你可以很快找到近似解。提出的問題超出了我的專業領域，儘管我認爲你會在math.stackexchange.com得到一個很好的答案。如果你問，請交叉連接問題，以便我們可以跟蹤答案。 – Hooked

我想你在找Fast Fourier Transform這很好，看到這個PowerPoint on FFT。實際上，當你想計算n個不同點的O（n log n）並且比Horner算法快得多時，FFT很有用。

FFT在單位的第n個根的冪上運行，並且使用它們之間的關係，因此當你想計算n個不同點的值時，速度非常快。

來源

2011-11-19 19:45:28

顯然，這不是我看到的原始方法，但它非常有趣，我認爲這可能是我現在可以獲得的最好方法。 –

對不起，但我更喜歡其他答案。社區請告知，如果改變答案被認爲是非常糟糕的做法！ –

@CrisStringfellow，放鬆一下，可以接受更適合您需求的答案。 –

給定一個係數向量和一個值，評估一個多項式的最快方法是什麼？

回答

相關問題