Fast Fourier transform: Difference between revisions
Added Delphi example
m (un-capitalized 's' in Golfscript) |
MaiconSoft (talk | contribs) (Added Delphi example) |
||
Line 776:
{{out}}
<pre>[4+0i, 1-2.41421i, 0+0i, 1-0.414214i, 0+0i, 1+0.414214i, 0+0i, 1+2.41421i]</pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{libheader| System.VarCmplx}}
{{libheader| System.Math}}
{{Trans|C#}}
<lang Delphi>
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.</lang>
{{out}}
<pre>4 + 0i
1 - 2,41421356237309i
0 + 0i
1 - 0,414213562373095i
0 + 0i
1 + 0,414213562373095i
0 + 0i
1 + 2,41421356237309i</pre>
=={{header|EchoLisp}}==
| |||