Re: Деление длинных чисел методом Ньютона

From

Илья Кантор (2:5020/175.2)

To

Nick Kovaliov

Date

2002-10-30T13:19:16Z

Area

RU.ALGORITHMS

From: "Илья Кантор" <ilia@manual.ru>

Wed Oct 30 2002 11:25, Nick Kovaliov wrote to Илья Кантор:

ИК>> Как организовать вычисление A/B ?

NK> один столбиком, другой методом Ньютона.
Да, именно это и пишу ;) Умножение уже есть через БПФ.
По 8 миллионов цифр перемножает ;)

ИК>> Сначала, вроде, нужно найти обратное к B методом Ньютона.
ИК>> С какой точностью это нужно делать, если длина 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 ??



ИК>> Сам метод Ньютона делает итерации R <- R+(1-BR)*R.
ИК>> С какой точностью выполнять каждую операцию ?

NK> А вот с этим сложнее ...
Эти шаги я понял, как делать..  ;)

NK> А в Кнуте ещё описана не квадратическая, а кубическая итерация ...
Давить. Ньютон лучше ;)

NK> Имхо слишком много накладных расходов,
NK> которыя я лично не знаю, как избежать,
NK> и поэтому проще просто столбиком :)
Сложение и 2 умножения.. Вроде, все ;)
Ну и чуть всякой байды вроде копирования и округления, но это не считается.

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)