Re: преобразование фурье

From

Evgenij Masherov (2:5020/175.2)

To

Alexey Wolchansky

Date

2002-07-18T20:19:14Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Thu Jul 18 2002 16:20, Alexey Wolchansky wrote to Tolik Pozdeev:

 >> Хотелось бы  почитать про сабж(и подобные методы для быстрого перемножения

 AW> длинных чисел). Заранее сенкс.

 AW> Фурье бы от такого письма в гробу перевернулся :) Наверное-таки длинных
 AW> рядов чисел?
 AW> В рунете лежит книга в форматеЛ.Рабинер Б.Гоулд "Теория и применение
 AW> цифровой обработки сигналов" МИР 1978г. Поищи по поисковикам.

 Нет. Здесь спрашивается именно про умножение длинных чисел. Основная проблема
- если число представлено массивом "разрядов", скажем, по основанию 32768, то
время умножения пропорционально квадрату количества разрядов. Основная
операция - свертка, т.е. SUM a(i)*b(K-i), дающая в данном случае К-тый разряд
произведения. Однако Фурье свертки есть произведение Фурье от компонент
свертки. Т.е. делаем Фурье от "разрядов" сомножителей, затем перемножаем и
обратное Фурье. Сложность падает до сложности БПФ. При этои возможна потеря
точности, поэтому или Фурье с огромным запасом по точности - или аналоги Фурье
над конечными полями.
Кнут, т.2, гл. 4, параграф можно найти самому.

Евгений Машеров АКА СанитарЖеня

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