Най-бързият алгоритъм за изчисляване на големи полиноми

Доста общ въпрос, кой е най-бързият (от гледна точка на времева сложност) алгоритъм за оценка на полиноми от Степен 400 до 500.

Благодаря предварително.


multiplication polynomial-math
person Noor    schedule 09.12.2009    source източник
comment
Това е дяволски полином.   -  person ChaosPandion    schedule 10.12.2009
comment
Може да се наложи да разширите въпроса. Какъв вид принос очаквате? Какъв език? и т.н...   -  person ChaosPandion    schedule 10.12.2009
comment
Бих попитал и на mathoverflow.com.   -  person Georg Schölly    schedule 10.12.2009
comment
Какъв тип данни? Ако имате работа със стойности с плаваща запетая, трябва да имате предвид и числената стабилност.   -  person Josef Grahn    schedule 10.12.2009
comment
Заглавието на вашия въпрос предполага умножение на повече от един полином, а не оценка на един. Проблемът с умножението се решава ефективно чрез трансформации на Фурие и навивки.   -  person Phil Miller    schedule 10.12.2009

Отговори (2)


arrow_upward
9
arrow_downward

Ако говорите за оценка на полиноми, вероятно не можете да бъдете по-бързи от линейното време схемата на Хорнър - освен ако имате някакви специални обстоятелства.

Ако говорите за умножение на полиноми, алгоритъмът на Карацуба е доста лесен за изпълнение и доста бързо за този размер. Вярвам, че алгоритмите, базирани на бързо преобразуване на Фурие, си струва да се използват само ако имате по-големи полиноми.

person Hans-Peter Störr    schedule 09.12.2009
comment
+1 за Horner...много по-добре от първия ми поглед (както винаги). - person Jason Punyon; 10.12.2009
comment
Horner е не само бърз, но и устойчив на някои случаи на грешки при загуба на прецизност, които могат да засегнат наистина наивни подходи. - person dmckee --- ex-moderator kitten; 10.12.2009

arrow_upward
3
arrow_downward

Модифицираните версии на бързи трансформации на Фурие (FFT) обикновено осигуряват много добри резултати за този вид проблеми. Разгледайте този документ, който предлага като се използва хибриден FFT подход. Бих започнал вашето изследване, като потърся термини от рода на "бързо едномерно FFT". Може също да ви помогне да отбележите, че умножаването на два полинома е по същество същата операция като умножаването на две цели числа.

person John Feminella    schedule 09.12.2009