89 lines
1.6 KiB
Plaintext
89 lines
1.6 KiB
Plaintext
program Fast_Fourier_transform;
|
|
|
|
{$APPTYPE CONSOLE}
|
|
|
|
uses
|
|
System.SysUtils,
|
|
System.VarCmplx,
|
|
System.Math;
|
|
|
|
function BitReverse(n: UInt64; bits: Integer): UInt64;
|
|
var
|
|
count, reversedN: UInt64;
|
|
begin
|
|
reversedN := n;
|
|
count := bits - 1;
|
|
|
|
n := n shr 1;
|
|
|
|
while n > 0 do
|
|
begin
|
|
reversedN := (reversedN shl 1) or (n and 1);
|
|
dec(count);
|
|
n := n shr 1;
|
|
end;
|
|
|
|
Result := ((reversedN shl count) and ((1 shl bits) - 1));
|
|
end;
|
|
|
|
procedure FFT(var buffer: TArray<Variant>);
|
|
var
|
|
j, bits: Integer;
|
|
tmp: Variant;
|
|
begin
|
|
bits := Trunc(Log2(length(buffer)));
|
|
|
|
for j := 1 to High(buffer) do
|
|
begin
|
|
var swapPos := BitReverse(j, bits);
|
|
if swapPos <= j then
|
|
Continue;
|
|
|
|
tmp := buffer[j];
|
|
buffer[j] := buffer[swapPos];
|
|
buffer[swapPos] := tmp;
|
|
end;
|
|
|
|
var N := 2;
|
|
while N <= Length(buffer) do
|
|
begin
|
|
var i := 0;
|
|
while i < Length(buffer) do
|
|
begin
|
|
for var k := 0 to N div 2 - 1 do
|
|
begin
|
|
var evenIndex := i + k;
|
|
var oddIndex := i + k + (N div 2);
|
|
var _even := buffer[evenIndex];
|
|
var _odd := buffer[oddIndex];
|
|
var term := -2 * PI * k / N;
|
|
var _exp := VarComplexCreate(Cos(term), Sin(term)) * _odd;
|
|
|
|
buffer[evenIndex] := _even + _exp;
|
|
buffer[oddIndex] := _even - _exp;
|
|
end;
|
|
i := i + N;
|
|
end;
|
|
N := N shl 1;
|
|
end;
|
|
|
|
end;
|
|
|
|
const
|
|
input: array of Double = [1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0];
|
|
|
|
var
|
|
inputc: TArray<Variant>;
|
|
|
|
begin
|
|
SetLength(inputc, length(input));
|
|
for var i := 0 to High(input) do
|
|
inputc[i] := VarComplexCreate(input[i]);
|
|
|
|
FFT(inputc);
|
|
|
|
for var c in inputc do
|
|
writeln(c);
|
|
readln;
|
|
end.
|