Fast Fourier transform: Difference between revisions
Content added Content deleted
m (un-capitalized 's' in Golfscript) |
MaiconSoft (talk | contribs) (Added Delphi example) |
||
Line 776: | Line 776: | ||
{{out}} |
{{out}} |
||
<pre>[4+0i, 1-2.41421i, 0+0i, 1-0.414214i, 0+0i, 1+0.414214i, 0+0i, 1+2.41421i]</pre> |
<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}}== |
=={{header|EchoLisp}}== |