Major 0 18 апреля, 2016 Опубликовано 18 апреля, 2016 · Жалоба Наткнулся на работу 1983 Галкин, Желуковский "Машинный алгоритм преобразования фурье без ошибок округления". Используется поле GF для чисел Мерсенна. Развернуто нашел у Ричарда Блейхута (жаль у него нет новы изданий с учетом современных реалий). Но практических работ использующих отображение в поле целых чисел не нашел. Это игра ума, или современные реализации на double или double double плюс FMA убивают смысл затеи? Есть корефеии, заставшие эту тему? P.S. Про Блейхута ошибся, в 2010 вышла новая версия "Fast Algorithms for Signal Processing" Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Pavia 0 19 апреля, 2016 Опубликовано 19 апреля, 2016 · Жалоба Тут эксперты получше меня. Объясняю как я понимаю. Это обычные длинные числа. Проблемо в том что на каждом умножении они удваеваются. Откуда имеем скорость работы 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/ Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Major 0 20 апреля, 2016 Опубликовано 20 апреля, 2016 · Жалоба Про умножение и памяь не очень понял. Попробую сам, возможно ошибаюсь. Нам требуется выбрать число 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, ручная работа. и вычеты по модулю или сдвиги не дешевле умножения или сложения на ПК. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться