|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 18 Jul 2002 20:19:14
To : Alexey Wolchansky
Subject : Re: преобразование фурье
--------------------------------------------------------------------------------
Thu Jul 18 2002 16:20, Alexey Wolchansky wrote to Tolik Pozdeev:
>> Хотелось бы почитать про сабж(и подобные методы для быстрого перемножения
AW> длинных чисел). Заранее сенкс.
AW> Фурье бы от такого письма в гробу перевернулся :) Hаверное-таки длинных
AW> рядов чисел?
AW> В рунете лежит книга в форматеЛ.Рабинер Б.Гоулд "Теория и применение
AW> цифровой обработки сигналов" МИР 1978г. Поищи по поисковикам.
Hет. Здесь спрашивается именно про умножение длинных чисел. Основная проблема
- если число представлено массивом "разрядов", скажем, по основанию 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
