Re: Деление длинных чисел методом Ньютона
- From
- Nick Kovaliov ()
- To
- Илья Кантор
- Date
- 2002-10-30T16:24:46Z
- Area
- RU.ALGORITHMS
From: "Nick Kovaliov" <Nick@urm.ru>
ИК> Неправда. Будет медленнее.
ИК> Модулярная арифметика, однако..
ИК> И реализовывать забодаешься wide NTT.
А мне видятся проблемы с точностью ...
В целочисленной версии их в принципе не может быть :)
Я что-то недопонял ... что принимается за разряд,
который у тебя загоняется в double ?
Что ты рекомендуешь принимать за разряд
при Real FFT ? 8 бит ? 16 бит ? 32 бита ?
При целочисленном в пнях имхо
проще всего брать байт за разряд.
Не очень много за раз ;-) , но
зато можно запросто извращаться со
всякими схемами Винограда, Рейдера-Гуда,
а вот с Real FFT не знаю, как получится
из-за проблем с погрешностью ... хотя, считать надо ...
ИК> Кстати, на сайте все дико тормозит ;)
Да вроде нет ...
ИК> Нормальный столбик выигрывает у
ИК> простого 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> Кого давить-то ? :)
ИК> Итерацию давить ;)
ИК> Она кубическая, но в ней вычислений больше.
ИК> Невыгодно, однако..
дЫк и сходится быстрее ...
Кнут, насколько я помню, её (кубическую) всё же рекомендовал.
КИ>NK> Ну ты ещё скажи, что тебя ТОЛЬКО
КИ>NK> асимптотическая сложность интересует ... ;-)
КИ> Дык хочу 10000 цифр перемножать и выше.
КИ> По всему выходит, что с 10000 Ньютон
КИ> должен зарулить обычное деление.
Ну для таких размеров-то конечно ...
А зачем тебе такие большие числа ? ;-)
До встречи, всего наилучшего !
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)