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

From

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

To

Nick Kovaliov

Date

2002-10-30T15:12:49Z

Area

RU.ALGORITHMS

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

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

NK> один столбиком, другой методом Ньютона.

ИК>> Да, именно это и пишу ;)
ИК>> Умножение уже есть через БПФ.
ИК>> По 8 миллионов цифр перемножает ;)

 NK> Если делать преобразование Фурье в конечных полях
 NK> (в кольцах Z/Zn, n = 2^q я пытался копать, но нифига),
 NK> то должно получиться быстрее, чем у тебя на сайте.
Неправда. Будет медленнее. Модулярная арифметика, однако.. И реализовывать
забодаешься wide NTT.

Кстати, на сайте все дико тормозит ;)

NK> Жалко только, что на практике хорошо оптимизированный столбик
NK> будет делать этот способ до < 4096 бит приблизительно.
Нормальный столбик выигрывает у простого Real FFT до 1024 цифр :(
А ежели все оптимизировать - код уродский получается.

NK> Ежели найдёшь, как быстро вычислять по модулю
NK> 2^n - 1, или 2^n + 1 (ну или по модулю какого-нить простого числа),
NK> тогда можно сделать и Фурье над конечными полями очень быстро.
Копай NTT, Shonhage-Shtrassen. Конкретнее, wide NTT.. Там, увы, все не так
просто ;(

ИК>> Читаю Numerical Recipes..
ИК>> Там используется какая-то странная добавка к длинам:
ИК>> #define MACC 6.
ИК>> Интересно, что это такое ?

NK> Тупо в гугле (искал Numerical Recipes MACC)
NK> наткнулся на фортрановский исходник, вот частичка -

NK> Больше ничего не нашёл ...
NK> Да и исходник был про какую-то интерполяцию ...
Да, не очень-то понятная книженция .. ;(


 NK>         ИК> NK> А в Кнуте ещё описана не
 NK>         ИК> NK> квадратическая, а кубическая итерация ...
 NK> Кого давить-то ? :)
 NK> Эээ ... нуу ... неужто я уже ничего не помню !? ... ;-\
Итерацию давить ;) Она кубическая, но в ней вычислений больше.
Невыгодно, однако..

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

 NK> Ну ты ещё скажи, что тебя ТОЛЬКО
 NK> асимптотическая сложность интересует ... ;-)
Дык хочу 10000 цифр перемножать и выше. По всему выходит, что с 10000 Ньютон
должен зарулить обычное деление.

 NK> Я не понимаю, почему с такой маленькой точностью вычисляют,
 NK> но всё получается правильно ... есть где-нить описание почитать ?
Можно на пальцАх прикинуть, разве..

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