Ctrlalt: /* Ссылки */

2021-10-12T00:23:16Z

Ссылки

← Предыдущая версия		Версия от 00:23, 12 октября 2021
Строка 64:		Строка 64:
	== Ссылки ==		== Ссылки ==

			Видео
			* [https://www.youtube.com/watch?v=h7apO7q16V0 Reducible — The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?]
	Теория		Теория
	* [http://e-maxx.ru/algo/fft_multiply e-maxx.ru — Быстрое преобразование Фурье за O (N log N). Применение к умножению двух полиномов или длинных чисел]		* [http://e-maxx.ru/algo/fft_multiply e-maxx.ru — Быстрое преобразование Фурье за O (N log N). Применение к умножению двух полиномов или длинных чисел]

Ctrlalt: Новая страница: « using Complex = complex; void fft(vector &p, Complex x) { size_t n = p.size(); if (n == 1) return; vector...»

2021-10-11T23:15:12Z

Новая страница: « using Complex = complex<double>; void fft(vector<Complex> &p, Complex x) { size_t n = p.size(); if (n == 1) return; vector<Complex>...»

Новая страница

using Complex = complex<double>;

void fft(vector<Complex> &p, Complex x) {
size_t n = p.size();
if (n == 1)
return;

vector<Complex> a(n / 2), b(n / 2);
for (int i = 0; i < n / 2; i++) {
a[i] = p[2 * i];
b[i] = p[2 * i + 1];
}

fft(a, x * x);
fft(b, x * x);

Complex xPow = 1;
for (int i = 0; i < n / 2; i++) {
p[i] = a[i] + xPow * b[i];
p[n / 2 + i] = a[i] - xPow * b[i];
xPow *= x;
}
}

const double PI = acos(-1);

vector<Complex> fixSize(vector<int> &p, int targetSize) {
vector<Complex> res(p.begin(), p.end());
while (res.size() < targetSize || (res.size() & (res.size() - 1)))
res.push_back(0);
return res;
}

vector<Complex> evaluate(vector<int> &p, int targetSize) {
vector<Complex> res = fixSize(p, targetSize);
fft(res, polar(1.0, 2 * PI / res.size()));
return res;
}

vector<int> interpolate(vector<Complex> &p) {
int n = p.size();
fft(p, polar(1.0, -2 * PI / n));

vector<int> res(n);
for (int i = 0; i < n; i++)
res[i] = round(real(p[i]) / n);

while (res.size() > 1 && !res.back())
res.pop_back();
return res;
}

vector<int> multiply(vector<int> &pa, vector<int> &pb) {
int targetSize = pa.size() + pb.size();
vector<Complex> a = evaluate(pa, targetSize);
vector<Complex> b = evaluate(pb, targetSize);

for (int i = 0; i < a.size(); i++)
a[i] *= b[i];

return interpolate(a);
}

== Ссылки ==

Теория
* [http://e-maxx.ru/algo/fft_multiply e-maxx.ru — Быстрое преобразование Фурье за O (N log N). Применение к умножению двух полиномов или длинных чисел]
* [https://cp-algorithms.com/algebra/fft.html cp-algorithms.com — Fast Fourier transform]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 neerc.ifmo.ru/wiki — Быстрое преобразование Фурье]
* algorithmica.org — Быстрое преобразование Фурье [https://ru.algorithmica.org/cs/algebra/fft/ 1], [https://algorithmica.org/ru/fft 2]
* [https://drive.google.com/file/d/1IdjyWinAT3Qo9oSonFj21VASBCJsxltB/view Кульков А. — Быстрое преобразование Фурье и многочлены]
* [https://usaco.guide/adv/fft?lang=cpp usaco.guide — Introduction to Fast Fourier Transform]

Код
* [https://github.com/indy256/codelibrary/blob/master/cpp/numeric/fft.h indy256/codelibrary/cpp/numeric/fft.h]
* [https://github.com/indy256/codelibrary/blob/master/cpp/numeric/fft_slow.cpp indy256/codelibrary/cpp/numeric/fft_slow.cpp]
* [https://github.com/ADJA/algos/blob/master/NumberTheory/FFT.cpp ADJA/algos/NumberTheory/FFT.cpp]
* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/FFT.java kevin-wayne/algs4/FFT.java]

Быстрое преобразование Фурье - История изменений

Ctrlalt: /* Ссылки */

Ctrlalt: Новая страница: « using Complex = complex; void fft(vector &p, Complex x) { size_t n = p.size(); if (n == 1) return; vector...»