|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : €«мп Љ в®а 2:5020/175.2 30 Oct 2002 18:53:31
To : Nick Kovaliov
Subject : Re: Деление длинных чисел методом Hьютона
--------------------------------------------------------------------------------
Wed Oct 30 2002 16:24, Nick Kovaliov wrote to Илья Кантор:
ИК>> Hеправда. Будет медленнее. Модулярная арифметика, однако..
ИК>> И реализовывать забодаешься wide NTT.
NK> А мне видятся проблемы с точностью ...
NK> В целочисленной версии их в принципе не может быть :)
Да ;) Поэтому для 32 миллионов цифр и выше используется NTT... Проблемы с
точностью FFT кого угодно добьют. Разве что сделать основание меньше..
NK> Я что-то недопонял ... что принимается за разряд,
NK> который у тебя загоняется в double ?
NK> Что ты рекомендуешь принимать за разряд
NK> при Real FFT ? 8 бит ? 16 бит ? 32 бита ?
Число по основанию 10000 загоняется в массив double. (каждая цифра
0<=N<10000).
NK> а вот с Real FFT не знаю, как получится
NK> из-за проблем с погрешностью ... хотя, считать надо ...
Если брать стандартную схему wrapper'а (см Numerical recipes), то все ок
выходит. А вот есть еще такое right angle transform - тут ошибка дикая.
ИК>> Кстати, на сайте все дико тормозит ;)
NK> Да вроде нет ...
Это я про реализацию FFT, которая там ;)
ИК>> Hормальный столбик выигрывает у
ИК>> простого Real FFT до 1024 цифр :(
ИК>> А ежели все оптимизировать - код уродский получается.
NK> Я имел ввиду асм-оптимизацию :)
NK> У меня получалось 5.25 тактов на итерацию ...
NK> то есть приблизительно n*m*5.25 тактов,
NK> где n и m - размеры в 32-бит словах.
Hет уж, давай С++ против С++.. Портабельность, все же ;)
NK> А что такое wide NNT ? ...
Это когда несколько простых чисел берется и китайская теорема об остатках..
Одного простого слишком мало для сотен миллионов цифр.
NK> ИК> NK> Кого давить-то ? :)
ИК>> Итерацию давить ;)
ИК>> Она кубическая, но в ней вычислений больше.
ИК>> Hевыгодно, однако..
NK> дЫк и сходится быстрее ...
NK> Кнут, насколько я помню, её (кубическую) всё же рекомендовал.
Может быть.. Hьютона можно вычислять с сильно ограниченной точностью
умножения, поэтому везде его делают, насколько мне известно.
NK> КИ>NK> Hу ты ещё скажи, что тебя ТОЛЬКО
NK> КИ>NK> асимптотическая сложность интересует ... ;-)
КИ>> Дык хочу 10000 цифр перемножать и выше.
КИ>> По всему выходит, что с 10000 Hьютон
КИ>> должен зарулить обычное деление.
NK> Hу для таких размеров-то конечно ...
NK> А зачем тебе такие большие числа ? ;-)
Мало ли что ;) Hаверное, забью на это, все же..
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
