Перейти к содержанию
    

Фурье в суррогтаных полях

Наткнулся на работу 1983 Галкин, Желуковский "Машинный алгоритм преобразования фурье без ошибок округления".

Используется поле GF для чисел Мерсенна.

Развернуто нашел у Ричарда Блейхута (жаль у него нет новы изданий с учетом современных реалий).

 

Но практических работ использующих отображение в поле целых чисел не нашел.

Это игра ума, или современные реализации на double или double double плюс FMA убивают смысл затеи?

Есть корефеии, заставшие эту тему?

 

P.S. Про Блейхута ошибся, в 2010 вышла новая версия "Fast Algorithms for Signal Processing"

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Тут эксперты получше меня. Объясняю как я понимаю.

 

Это обычные длинные числа. Проблемо в том что на каждом умножении они удваеваются. Откуда имеем скорость работы O((N^2)Log^2(N)) и потребление памяти O(N*2^(N*Log(N)))

Для N=8 вам потребуется 1 Гб при 9 около 4 Гб. Поэтому и неприменяют.

 

Далее вы начинаете использовать дроби и их сокращение.

Это вам позволит сократить память и продержаться до N=100.

В книге есть приписька по этому поводу сокрощения. Но никто нетестировал.

 

Затем вы решаете перейти на поле вычетов. Это экономит память.

Но вконце надо делать обратное преобразование. А это умножение

серии длинных чисел. Сильно ничего не выигрываете.

 

В любом случае ответ усекать. Числа. Откуда приходим к реальным числам. С фикированной или плавающей.

Для float есть теория о точности вычисления.

 

Вот тут можно посмотреть про оценку точности свёртки для double

http://www.daemonology.net/tricl/

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Про умножение и памяь не очень понял.

Попробую сам, возможно ошибаюсь.

Нам требуется выбрать число p такое, чтобы результат свертки был меньше этого p.

Если есть две последовательности длиной N, состоящие из чисел M, то макс коэф. будет равен N*M^2.

Если для M надо q разрядов, то слово памяти должно быть равно 2*q+log2(N).

M=65535, N=1024 => 32+10=42 бита.

Для вычисления (через фурье) надо памяти порядка O(N).

Если заранее знать одну из последовательностей, то оценка на максимальное число бит в результате может быть лучше.

Промежуточные значения у нас по модулю p в поле GF(p), и их переполнение не влияет на результат.

 

Из минусов вижу сложность комбинирования алгоритмов под желаемое N, ручная работа. и вычеты по модулю или сдвиги не дешевле умножения или сложения на ПК.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...