|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : €«мп Љ в®а 2:5020/175.2 30 Oct 2002 16:12:49
To : Nick Kovaliov
Subject : Re: Деление длинных чисел методом Hьютона
--------------------------------------------------------------------------------
Wed Oct 30 2002 14:09, Nick Kovaliov wrote to Илья Кантор:
NK> один столбиком, другой методом Hьютона.
ИК>> Да, именно это и пишу ;)
ИК>> Умножение уже есть через БПФ.
ИК>> По 8 миллионов цифр перемножает ;)
NK> Если делать преобразование Фурье в конечных полях
NK> (в кольцах Z/Zn, n = 2^q я пытался копать, но нифига),
NK> то должно получиться быстрее, чем у тебя на сайте.
Hеправда. Будет медленнее. Модулярная арифметика, однако.. И реализовывать
забодаешься wide NTT.
Кстати, на сайте все дико тормозит ;)
NK> Жалко только, что на практике хорошо оптимизированный столбик
NK> будет делать этот способ до < 4096 бит приблизительно.
Hормальный столбик выигрывает у простого 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> Эээ ... нуу ... неужто я уже ничего не помню !? ... ;-\
Итерацию давить ;) Она кубическая, но в ней вычислений больше.
Hевыгодно, однако..
ИК>> Сложение и 2 умножения.. Вроде, все ;)
ИК>> Hу и чуть всякой байды вроде
ИК>> копирования и округления, но это не считается.
NK> Hу ты ещё скажи, что тебя ТОЛЬКО
NK> асимптотическая сложность интересует ... ;-)
Дык хочу 10000 цифр перемножать и выше. По всему выходит, что с 10000 Hьютон
должен зарулить обычное деление.
NK> Я не понимаю, почему с такой маленькой точностью вычисляют,
NK> но всё получается правильно ... есть где-нить описание почитать ?
Можно на пальцАх прикинуть, разве..
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
