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

From

Nick Kovaliov ()

To

Илья Кантор

Date

2002-10-30T14:09:55Z

Area

RU.ALGORITHMS

From: "Nick Kovaliov" <Nick@urm.ru>

        ИК> NK> один столбиком, другой методом Ньютона.
    ИК> Да, именно это и пишу ;)
    ИК> Умножение уже есть через БПФ.
    ИК> По 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> квадратическая, а кубическая итерация ...
    ИК> Давить. Ньютон лучше ;)
Кого давить-то ? :)
Эээ ... нуу ... неужто я уже ничего не помню !? ... ;-\

Там как раз Ньютон, только добавляется
ещё одно кубическое слагаемое,
и сходится такая ерундень быстрее ...

Жалко, Кнута нет под рукой вспомнить.

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

Я не понимаю, почему с такой маленькой точностью вычисляют,
но всё получается правильно ... есть где-нить описание почитать ?
(только ссылки, а не книжки пока что ... ;-|    )

До встречи, всего наилучшего !


--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)