можно покопать GMP, afaik - там есть реализация этого метода, так же в гугл легко выдает способы модификации этого метода.
UbIvItS Преобразованием Фурье вроде намного быстрей. Правда, я пока с этим не разбирался, руки не дойдут.
Преобразование Фурье бывает не только над действительными/комплексными числами, но и над кольцами. Для умножения чисел можно использовать оба преобразования Фурье. Что из них будет быстрее - не знаю.
Этот метод основан на "Китайской теореме об остатках". Мне вообще надо реализовать этот метод в Delphi. Я застрял на востановлении по алгоритму Ньютона! помогите люди добрые!!
для чисел больших 512 бит(570-571) бит какой будет наиболее быстрый алгоритм умножения и нахождения остатка? надо максимально быстро сделать операцию: а*б\с а,б,с - числа где то по 571 биту.
dead_body http://lists.boost.org/Archives/boost/2005/04/85368.php http://www.cs.nyu.edu/exact/doc/qmul.ps Хотя вот: http://www.cse.psu.edu/~furer/Papers/mult.pdf В общем, видимо, лучше всего Шенхаге-Штрассена.
Не бог весть какой источник, но... http://en.wikipedia.org/wiki/Sch%C3%B6nhage-Strassen_algorithm In practice the Schönhage-Strassen algorithm starts to outperform older methods such as Karatsuba and Toom-Cook multiplication for numbers beyond 2^(2^15) to 2^(2^17) (10,000 to 40,000 decimal digits). Надоб на практике проверить как оно на самом деле
