Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 01.01.2011, 23:55
Новичок

Отправить личное сообщение для alien308 Посмотреть профиль Найти все сообщения от alien308
 
Регистрация: 01.01.2011
Сообщений: 4

Библиотека или исходники с алгоритмом для двумерного быстрого преобразования фурье.
Нужны библиотека или исходники с алгоритмом двумерного быстрого преобразования фурье для цельночисленных данных. Для быстроты естественно
  #2  
Старый 02.01.2011, 09:40
гщсть

 
Сообщений: n/a

FFTW

не важно что на входе целые числа - промежуточные же числа и ответ будут вещественными
  #3  
Старый 02.01.2011, 11:32
Новичок

Отправить личное сообщение для alien308 Посмотреть профиль Найти все сообщения от alien308
 
Регистрация: 01.01.2011
Сообщений: 4

Так целые числа для скорости, операции с целыми намного быстрее, чем с числами с плавающей точкой.
  #4  
Старый 02.01.2011, 12:36
гocть

 
Сообщений: n/a

забудь о целых числах при вычислении fft. там синусы косинусы считаются и перемножаются с первого же шага алгоритма.

да, есть целочисленный аналог fft - number theoretic transform, где мы работаем под модулем, но там постоянно делят, делят, делят, поэтому он медленнее чем вещественный fft.
  #5  
Старый 02.01.2011, 18:05
Новичок

Отправить личное сообщение для alien308 Посмотреть профиль Найти все сообщения от alien308
 
Регистрация: 01.01.2011
Сообщений: 4

Правильно отмаштабировать и умножай сколько хочешь в пределах разумного. А значение синусов, косинусов в табличке (массиве) хранить, немного их.
  #6  
Старый 02.01.2011, 20:17
гocть

 
Сообщений: n/a

процессоры нынче по 4-8 чисел с плавающей точкой за раз умножают (SSE2 инструкции). не парься, возьми хорошую реализацию вещественного fft - я уже назвал тебе fftw, это будет быстрее всего что ты щас собираешься понапридумывать с целыми числами.
  #7  
Старый 03.01.2011, 11:35
Новичок

Отправить личное сообщение для alien308 Посмотреть профиль Найти все сообщения от alien308
 
Регистрация: 01.01.2011
Сообщений: 4

Попробовал, да скорость с 64 разрядными целыми сравнима с double. Так что fftw, быстрей будет чем самописноное.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Исходники c++ Heroini Криптография 1 14.05.2010 00:59
Сортировка выбором двумерного массива в C# Amel Сортировка и поиск 0 15.03.2010 20:19
кто знает где есть исходники алгоритмов много шаблонного поиска? vv40in Сортировка и поиск 0 13.04.2009 15:04
Трехмерные преобразования Jeyzi Решение задач с acm.sgu.ru 2 17.06.2008 12:20
алгоритм преобразования числа в string незарегистрированный Обработка изображений, звук, графика 1 08.12.2006 12:59