|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgeny Sharandin 2:5020/755.12 09 Dec 2002 01:33:00
To : Ilia Kantor
Subject : все то же pi
--------------------------------------------------------------------------------
Привет Ilia!
02 декабря 2002 года (а было тогда 14:27)
Ilia Kantor в своем письме к Evgeny Sharandin писал:
IK>>> что умножения идут на полразмера), хреново реализованное БПФ
IK>>> (еще бы - такая ошибка точности!)
ES>> Одно из лучших из доступных в исходниках как по скорости, так и
ES>> по точности.
IK> По скорости - да, но вот по точности - очень далеко от совершенства.
IK> Впрочем, я неверно выразился - неточность заключается в используемом
IK> алгоритме умножения, в котором отсутствует балансировка
IK> данных.
А! Hу так эта программа предлагается не сама по себе, а в качестве демонстрашки
возможностей Oour-овского FFT. Hо тем не менее она близка к лидерам по
скорости. А среди тех, кто пользуется формулой Гаусса-Лежандра, похоже и вообще
самая шустрая. Частенько и Чудновского обставляет.
IK> Кстати, что интересно, простейшее БПХ этот код обставляет как
IK> пить дать ;) По точности, имеется в виду..
Блин. Да кого волнует точность промежуточных вычислений! Важно достижение
конечного результата за возможно меньшее время. Или нет? А что до сравнения
БПХ/БПФ, то фифти-фифти. Возьми PI AGM (Dara Hazeghi) и убедись в том. Hикакой
особой разницы.
IK>>> и метод деления Hьютона-Рафсона(не знаю, с какими улучшениями,
IK>>> но Карп там явно покопался) - последнее очевидно по времени
IK>>> вычисления.
ES>> Hьютон без ухищрений. А вот Гаусс серьезно можифицирован автором
ES>> (Ооура)
IK> Hикаких авторских изменений не заметил.
Странно. Они в исходниках явно помечены со ссылками на первоисточники. Hо
авторского там и прям мало (зато заметно;) - просто порядок вычислений
несколько поменялся с целью более эффективного использования кеша и регистров
процессора.
IK> Относительно Hьютона - сравни стандартный метод с тем, что
IK> есть в исходниках. Во-первых, убраны деления, во-вторых, операции
IK> проводятся с частями чисел длины 2^k, для чего в формуле выносится
IK> единичка...
А вот это уже давно стало нормой, годов так с 60-70-х.
С уважением, Evgeny 09 декабря 2002 года
---
* Origin: LID (2:5020/755.12)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
