|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : €«мп Љ в®а 2:5020/175.2 30 Oct 2002 14:19:16
To : Nick Kovaliov
Subject : Re: Деление длинных чисел методом Hьютона
--------------------------------------------------------------------------------
Wed Oct 30 2002 11:25, Nick Kovaliov wrote to Илья Кантор:
ИК>> Как организовать вычисление A/B ?
NK> один столбиком, другой методом Hьютона.
Да, именно это и пишу ;) Умножение уже есть через БПФ.
По 8 миллионов цифр перемножает ;)
ИК>> Сначала, вроде, нужно найти обратное к B методом Hьютона.
ИК>> С какой точностью это нужно делать, если длина A=n, Длина B=m ?
Читаю Numerical Recipes.. Там используется какая-то странная добавка к длинам:
#define MACC 6.
Интересно, что это такое ?
А делают они для деления 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 ??
ИК>> Сам метод Hьютона делает итерации R <- R+(1-BR)*R.
ИК>> С какой точностью выполнять каждую операцию ?
NK> А вот с этим сложнее ...
Эти шаги я понял, как делать.. ;)
NK> А в Кнуте ещё описана не квадратическая, а кубическая итерация ...
Давить. Hьютон лучше ;)
NK> Имхо слишком много накладных расходов,
NK> которыя я лично не знаю, как избежать,
NK> и поэтому проще просто столбиком :)
Сложение и 2 умножения.. Вроде, все ;)
Hу и чуть всякой байды вроде копирования и округления, но это не считается.
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
