С учетом вектора коэффициента и значения, какой самый быстрый способ оценки полинома?

Question

Я помню, как где-то читал (может быть, кто-то может помочь вспомнить, где), что существует метод, который является самым быстрым для оценки полинома. Что-то напоминает мне, что это как-то связано с формулой Виетты, или с тем фактом, что коэффициент 0-степени является произведением коэффициентов 0-степени любых факторов многочлена.

Я знаю, что в википедии написано, что это схема Хорнера для быстрой оценки. Но я вспоминаю, что вам вообще не нужно было так оценивать - у него было что-то с корнями?

Все, что я точно знаю, это то, что был метод оценки полинома, который дает вам ощущение "о, что умно", когда вы видите это, но это не слишком сложно и вроде как очевидно.

Кто-нибудь добрый или достаточно умный, чтобы помочь мне?

Это что-то вроде «вы можете вычислить P в точке x с помощью…», а затем есть действительно простая небольшая вещь, которая на самом деле не требует каких-либо реальных сложений и умножений порядка степени полинома.

Answer 1

Вы оцениваете многочлен более одного раза?Является ли полином особенно простым?Рассмотрим следующий многочлен:

f(a) = a^(14)

Если мы хотим уменьшить количество умножений, необходимое для оценки f(a), мы можем вычислить минимальную цепочку сложений из возведение в цепочку сложений :

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

Что показывает, что мы можем вычислить f(a), используя только 5 умножений.Для фиксированного многочлена с малыми коэффициентами это может быть значительной экономией.Wikipeida отмечает:

На практике ... кратчайшее возведение в степень по цепочке сложений в основном используется для небольших фиксированных показателей, для которых кратчайшая цепочка может быть предварительно вычислена и не слишком велика.

Для многих реальных случаев, когда f(a) может варьироваться, может подойти другой метод, но стоит отметить альтернативные решения!

Answer 2

Я думаю, что вы ищете Быстрое преобразование Фурье это тоже хорошо, посмотрите это PowerPoint на БПФ .Фактически, БПФ полезно, когда вы хотите вычислить полиномиальное значение в n другой точке, которая является O (n log n) и очень быстрее, чем алгоритм Хорнера.

БПФ работает на мощности n-го корня единицы, ииспользует соотношение между ними и поэтому очень быстро, когда вы хотите вычислить значение n различных точек.