все то же pi

From

Evgeny Sharandin (2:5020/755.12)

To

Ilia Kantor

Date

2002-12-09T00:33Z

Area

RU.ALGORITHMS

Reply-To: shar@nep.cplire.ru

Привет Ilia!

02 декабря 2002 года (а было тогда 14:27)
Ilia Kantor в своем письме к Evgeny Sharandin писал:

 IK>>> что умножения идут на полразмера), хреново реализованное БПФ
 IK>>> (еще бы - такая ошибка точности!)

 ES>> Одно из лучших из доступных в исходниках как по скорости, так и
 ES>> по точности.

 IK> По скорости - да, но вот по точности - очень далеко от совершенства.
 IK> Впрочем, я неверно выразился - неточность заключается в используемом
 IK> алгоритме умножения, в котором отсутствует балансировка
 IK> данных.

А! Ну так эта программа предлагается не сама по себе, а в качестве демонстрашки
возможностей Oour-овского FFT. Но тем не менее она близка к лидерам по
скорости. А среди тех, кто пользуется формулой Гаусса-Лежандра, похоже и вообще
самая шустрая. Частенько и Чудновского обставляет.

 IK> Кстати, что интересно, простейшее БПХ этот код обставляет как
 IK> пить дать ;) По точности, имеется в виду..

Блин. Да кого волнует точность промежуточных вычислений! Важно достижение
конечного результата за возможно меньшее время. Или нет? А что до сравнения
БПХ/БПФ, то фифти-фифти. Возьми PI AGM  (Dara Hazeghi) и убедись в том. Никакой
особой разницы.

 IK>>> и метод деления Ньютона-Рафсона(не знаю, с какими улучшениями,
 IK>>> но Карп там явно покопался) - последнее очевидно по времени
 IK>>> вычисления.

 ES>> Ньютон без ухищрений. А вот Гаусс серьезно можифицирован автором
 ES>> (Ооура)

 IK> Никаких авторских изменений не заметил.

Странно. Они в исходниках явно помечены со ссылками на первоисточники. Но
авторского там и прям мало (зато заметно;) - просто порядок вычислений
несколько поменялся с целью более эффективного использования кеша и регистров
процессора.

 IK> Относительно Ньютона - сравни стандартный метод с тем, что
 IK> есть в исходниках. Во-первых, убраны деления, во-вторых, операции
 IK> проводятся с частями чисел длины 2^k, для чего в формуле выносится
 IK> единичка...

А вот это уже давно стало нормой, годов так с 60-70-х.

С уважением, Evgeny                           09 декабря 2002 года

---
 * Origin: LID (2:5020/755.12)