2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Алгоритм Фюрера
Сообщение26.04.2013, 20:11 
Хочу разобраться в алгоритме быстрого умножения, но что-то пока не очень получается :-( :-( :-(
Вот ссылка на статью, по которой разбираюсь: http://www.mpi-inf.mpg.de/~csaha/intMult.pdf
Итак, алгоритм состоит из 5-ти частей:
  • выбор параметров $M, m, k, c, p$. Тут почти всё понятно, кроме $c$. У них написано, что его можно взять равным $42$, хотя у меня получилось, что $c=O(\log N)$. Это я что-то не так посчитал или они имели ввиду, что для реальных чисел $42$ хватит с головой?
  • кодирование чисел многочленами -- тут тоже всё просто
  • вычисление корня $\rho (\alpha )$ -- просто подставить в формулу.
  • преобразование Фурье -- об этом позже
  • восстановление числа -- тоже по формуле
Теперь про преобразование Фурье. Вводится понятие групповой алгебры и характера:

(Оффтоп)

$E$ - аддитивная абелева группа, $\mathbb C$ - кольцо комплексных чисел. Тогда групповой алгеброй называется множество всевозможных сумм $\sum\limits _{g\in E}\alpha _gg, \alpha _g\in \mathbb C$ с операциями покоординатного сложения и "свёрточного" умножения.
Гомоморфизм $\chi :E\to\mathbb C^*$ называется характером. Образом характера является корень из 1. Множество всех характеров образуют мультипликативную группу $\hat E$, изоморфную $E$.

Далее вводятся непонятные для меня обозначения $|\chi \rangle =\sum\limits _{x\in E}\chi (x)|x\rangle$ и $\langle \chi |f\rangle ,f\in \mathbb C[E], \chi\in\hat E$. И ещё не понятно, как в явном виде найти все характеры (группу $\hat E$)?
Заранее спасибо за помощь!

 
 
 
 Re: Алгоритм Фюрера
Сообщение26.04.2013, 21:09 
Аватара пользователя
vlad_light в сообщении #715980 писал(а):
И ещё не понятно, как в явном виде найти все характеры (группу $\hat E$)?


Например, разложить группу в прямое произведение циклических. Любой характер однозначно задается своими значениями на образующих этих циклических компонент. Отсюда же видно, что группа характеров изоморфна исходной группе.

-- 26.04.2013, 22:12 --

vlad_light в сообщении #715980 писал(а):
Далее вводятся непонятные для меня обозначения $|\chi \rangle =\sum\limits _{x\in E}\chi (x)|x\rangle$


Это элемент групповой алгебры, у которого $\alpha_g=\chi(g)$.

 
 
 
 Re: Алгоритм Фюрера
Сообщение26.04.2013, 21:39 
Аватара пользователя
vlad_light в сообщении #715980 писал(а):
Это я что-то не так посчитал или они имели ввиду, что для реальных чисел хватит с головой?
Ограниченность $c$ следует из того, что $p$ достаточно большое ($p$ равно $1$ по модулю $2M$, значит $p\geqslant 2M+1$)

Теоретико-групповое описание БПФ можно пропустить, авторы его приводят как альтернативное обоснование, видимо, для знакомых с теорией представлений.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group