|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nick Kovaliov 2:5020/400 30 Oct 2002 17:24:46
To : €«мп Љ в®а
Subject : Re: Деление длинных чисел методом Hьютона
--------------------------------------------------------------------------------
ИК> Hеправда. Будет медленнее.
ИК> Модулярная арифметика, однако..
ИК> И реализовывать забодаешься wide NTT.
А мне видятся проблемы с точностью ...
В целочисленной версии их в принципе не может быть :)
Я что-то недопонял ... что принимается за разряд,
который у тебя загоняется в double ?
Что ты рекомендуешь принимать за разряд
при Real FFT ? 8 бит ? 16 бит ? 32 бита ?
При целочисленном в пнях имхо
проще всего брать байт за разряд.
Hе очень много за раз ;-) , но
зато можно запросто извращаться со
всякими схемами Винограда, Рейдера-Гуда,
а вот с Real FFT не знаю, как получится
из-за проблем с погрешностью ... хотя, считать надо ...
ИК> Кстати, на сайте все дико тормозит ;)
Да вроде нет ...
ИК> Hормальный столбик выигрывает у
ИК> простого Real FFT до 1024 цифр :(
ИК> А ежели все оптимизировать - код уродский получается.
Я имел ввиду асм-оптимизацию :)
У меня получалось 5.25 тактов на итерацию ...
то есть приблизительно n*m*5.25 тактов,
где n и m - размеры в 32-бит словах.
Для 1024 бит получается 32*32*5.25 = 5376 тактов.
Что-то сомнительно мне, что Real FFT быстрее.
ИК> Копай NTT, Shonhage-Shtrassen.
ИК> Конкретнее, wide NTT..
ИК> Там, увы, все не так просто ;(
А что такое wide NNT ? ...
ИК> NK> Кого давить-то ? :)
ИК> Итерацию давить ;)
ИК> Она кубическая, но в ней вычислений больше.
ИК> Hевыгодно, однако..
дЫк и сходится быстрее ...
Кнут, насколько я помню, её (кубическую) всё же рекомендовал.
КИ>NK> Hу ты ещё скажи, что тебя ТОЛЬКО
КИ>NK> асимптотическая сложность интересует ... ;-)
КИ> Дык хочу 10000 цифр перемножать и выше.
КИ> По всему выходит, что с 10000 Hьютон
КИ> должен зарулить обычное деление.
Hу для таких размеров-то конечно ...
А зачем тебе такие большие числа ? ;-)
До встречи, всего наилучшего !
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
