Участник:Victoria Stepanischeva/Быстрое преобразование Фурье (FFT) - История изменений

Igor Munkin: /* Схема реализации последовательного алгоритма */

2017-02-23T21:21:03Z

Схема реализации последовательного алгоритма

← Предыдущая версия		Версия от 21:21, 23 февраля 2017
Строка 221:		Строка 221:
	my $theta = 2 * pi * $_ / @{ $input };		my $theta = 2 * pi * $_ / @{ $input };
	Math::Complex->make(cos($theta), sin($theta));		Math::Complex->make(cos($theta), sin($theta));
	} (0 .. $#input);		} (0 .. $#{ $input });
	my $odd = fft([ map { $input->[2 * $_ + 1] }, (0 .. @{ $input } / 2 - 1) ]);		my $odd = fft([ map { $input->[2 * $_ + 1] } (0 .. @{ $input } / 2 - 1) ]);
	my $even = fft([ map { $input->[2 * $_] }, (0 .. @{ $input } / 2 - 1) ]);		my $even = fft([ map { $input->[2 * $_] } (0 .. @{ $input } / 2 - 1) ]);

	return [ map {		return [ map {
	$even->[$_ % @{ $even }] + $w[$_] * $odd->[$_ % @{ $odd }];		$even->[$_ % @{ $even }] + $w[$_] * $odd->[$_ % @{ $odd }]
	} (0 .. $#input) ];		} (0 .. $#{ $input }) ];
	};		}

	</source>		</source>

2016-12-05T08:15:52Z

2016-11-29T14:19:44Z

2016-11-22T21:02:34Z

2016-11-22T20:55:58Z

Масштабируемость алгоритма и его реализации

@@ Строка 276: / Строка 276: @@
 * число процессоров [ 5 : 45 ] с шагом 5
 * размер вектора [ 256 : 16384 ] с шагом равным степени двойки
 На следующем рисунке приведен график производительности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.

2016-11-21T09:31:12Z

2016-11-18T23:24:59Z

← Предыдущая версия		Версия от 23:24, 18 ноября 2016
Строка 258:		Строка 258:
	Обработку подмножеств, получаемых после разбиения, можно выполнять независимо,		Обработку подмножеств, получаемых после разбиения, можно выполнять независимо,
	этот факт можно использовать при распараллеливании алгоритма.		этот факт можно использовать при распараллеливании алгоритма.
			В случае рекурсивной реализации глубина рекурсии составит <math>log\, N</math>.
	Соотношение последовательной и параллельной сложности в случае неограниченных		Соотношение последовательной и параллельной сложности в случае неограниченных
	ресурсов является линейным.		ресурсов является линейным.

2016-11-18T23:18:53Z

2016-11-18T23:10:50Z

← Предыдущая версия		Версия от 23:10, 18 ноября 2016
Строка 279:		Строка 279:
	[[File:Stepmoon_performance.png\|center\|800px]]		[[File:Stepmoon_performance.png\|center\|800px]]

	Текст исследуемой программы		[https://github.com/FFTW/fftw3 Текст исследуемой программы]

	===Динамические характеристики и эффективность реализации алгоритма===		===Динамические характеристики и эффективность реализации алгоритма===

2016-11-18T23:09:32Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 23:09, 18 ноября 2016
Строка 272:		Строка 272:

	===Масштабируемость алгоритма и его реализации===		===Масштабируемость алгоритма и его реализации===
			Набор и границы значений изменяемых параметров запуска реализации алгоритма:
			* число процессоров [ 5 : 45 ] с шагом 5
			* размер вектора [ 256 : 16384 ] с шагом равным степени двойки

			На следующем рисунке приведен график производительности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.
	[[File:Stepmoon_performance.png\|center\|800px]]		[[File:Stepmoon_performance.png\|center\|800px]]

			Текст исследуемой программы

	===Динамические характеристики и эффективность реализации алгоритма===		===Динамические характеристики и эффективность реализации алгоритма===