|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nick Kovaliov 2:5020/400 30 Oct 2002 15:09:55
To : €«мп Љ в®а
Subject : Re: Деление длинных чисел методом Hьютона
--------------------------------------------------------------------------------
ИК> NK> один столбиком, другой методом Hьютона.
ИК> Да, именно это и пишу ;)
ИК> Умножение уже есть через БПФ.
ИК> По 8 миллионов цифр перемножает ;)
Если делать преобразование Фурье в конечных полях
(в кольцах Z/Zn, n = 2^q я пытался копать, но нифига),
то должно получиться быстрее, чем у тебя на сайте.
Жалко только, что на практике хорошо оптимизированный столбик
будет делать этот способ до < 4096 бит приблизительно.
Ежели найдёшь, как быстро вычислять по модулю
2^n - 1, или 2^n + 1 (ну или по модулю какого-нить простого числа),
тогда можно сделать и Фурье над конечными полями очень быстро.
ИК> Читаю Numerical Recipes..
ИК> Там используется какая-то странная добавка к длинам:
ИК> #define MACC 6.
ИК> Интересно, что это такое ?
Тупо в гугле (искал Numerical Recipes MACC)
наткнулся на фортрановский исходник, вот частичка -
MACC = 4 ;Number of interpolation points per 1/4 cycle
ИК> А делают они для деления q=u/v следующее:
ИК> mpinv(s,v,n-m+MACC,m); // s=1/v
ИК> mpmul(rr,s,u,n-m+MACC,n); // rr = su = u/v
ИК> mpsad(s, rr, n+n+MACC/2,1); // s = rr + 1 - что за маразм это ?
ИК> mpmov(q,&rr[1],n-m+1); // rr в q, готово.
ИК> Знать бы еще, что такое эта MACC ??
Больше ничего не нашёл ...
Да и исходник был про какую-то интерполяцию ...
ИК> NK> А в Кнуте ещё описана не
ИК> NK> квадратическая, а кубическая итерация ...
ИК> Давить. Hьютон лучше ;)
Кого давить-то ? :)
Эээ ... нуу ... неужто я уже ничего не помню !? ... ;-\
Там как раз Hьютон, только добавляется
ещё одно кубическое слагаемое,
и сходится такая ерундень быстрее ...
Жалко, Кнута нет под рукой вспомнить.
ИК> NK> Имхо слишком много накладных расходов,
ИК> NK> которыя я лично не знаю, как избежать,
ИК> NK> и поэтому проще просто столбиком :)
ИК> Сложение и 2 умножения.. Вроде, все ;)
ИК> Hу и чуть всякой байды вроде
ИК> копирования и округления, но это не считается.
Hу ты ещё скажи, что тебя ТОЛЬКО
асимптотическая сложность интересует ... ;-)
Я не понимаю, почему с такой маленькой точностью вычисляют,
но всё получается правильно ... есть где-нить описание почитать ?
(только ссылки, а не книжки пока что ... ;-| )
До встречи, всего наилучшего !
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
