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

From

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

To

Nick Kovaliov

Date

2002-10-30T17:53:31Z

Area

RU.ALGORITHMS

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

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

 ИК>> Неправда. Будет медленнее. Модулярная арифметика, однако..
 ИК>> И реализовывать забодаешься 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, которая там ;)

 ИК>> Нормальный столбик выигрывает у
 ИК>> простого Real FFT до 1024 цифр :(
 ИК>> А ежели все оптимизировать - код уродский получается.

 NK> Я имел ввиду асм-оптимизацию :)
 NK> У меня получалось 5.25 тактов на итерацию ...
 NK> то есть приблизительно n*m*5.25 тактов,
 NK> где n и m - размеры в 32-бит словах.
Нет уж, давай С++ против С++.. Портабельность, все же ;)

 NK> А что такое wide NNT ? ...
 Это когда несколько простых чисел берется и китайская теорема об остатках..
Одного простого слишком мало для сотен миллионов цифр.

 NK>         ИК> NK> Кого давить-то ? :)

    ИК>> Итерацию давить ;)
    ИК>> Она кубическая, но в ней вычислений больше.
    ИК>> Невыгодно, однако..

 NK> дЫк и сходится быстрее ...
 NK> Кнут, насколько я помню, её (кубическую) всё же рекомендовал.
Может быть.. Ньютона можно вычислять с сильно ограниченной точностью
умножения, поэтому везде его делают, насколько мне известно.

 NK>         КИ>NK> Ну ты ещё скажи, что тебя ТОЛЬКО
 NK>         КИ>NK> асимптотическая сложность интересует ... ;-)

    КИ>> Дык хочу 10000 цифр перемножать и выше.
    КИ>> По всему выходит, что с 10000 Ньютон
    КИ>> должен зарулить обычное деление.

 NK> Ну для таких размеров-то конечно ...
 NK> А зачем тебе такие большие числа ? ;-)
Мало ли что ;) Наверное, забью на это, все же..

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