Anonymous user
Fast Fourier transform: Difference between revisions
m
→[[Fast_Fourier_transform#ALGOL 68]]: Translation of this Fast_Fourier_transform#python version
(→{{header|Go}}: library name update) |
m (→[[Fast_Fourier_transform#ALGOL 68]]: Translation of this Fast_Fourier_transform#python version) |
||
Line 93:
( 0.000, 0.000) ( 0.000, 0.000)
( 0.000, 0.000) ( 1.000, 2.414)
</pre>
=={{header|ALGOL 68}}==
{{trans|Python}}Note: This specimen retains the original [[#Python|Python]] coding style.
{{works with|ALGOL 68|Revision 1 - no extension to language.}}
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.3.5 algol68g-2.3.5].}}
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}
'''File: Fast_Fourier_transform.a68'''<lang algol68>#!/usr/local/bin/a68g --script #
# -*- coding: utf-8 -*- #
MODE VALUE = COMPL;
MODE OPTINT = UNION(INT, VOID),
SLICE = STRUCT(OPTINT lwb, by, upb);
FORMAT slice fmt = $"["g(0)":"g(0)":"g(0)"] "$;
OP ELEM = (SLICE slice, []VALUE array)[]VALUE: (
INT by = (by OF slice|(INT by): by|1);
INT lwb = (lwb OF slice|(INT lwb): lwb|LWB array);
INT upb = (upb OF slice|(INT upb): upb|UPB array);
(FALSE|printf(($"ELEM array in: "$, slice fmt, lwb, by, upb, $f(compl fmt)x$, array,$" => "$)));
[(upb-lwb)OVERby+1]VALUE out;
INT upb out := 0;
FOR index FROM lwb BY by TO upb DO
out[upb out+:=1] := array[index] OD;
(FALSE|printf(($"out: "$, slice fmt, lwb, by, upb, $f(compl fmt)x$, out,$l$)));
out
);
PROC fft = ([]VALUE in)[]VALUE: (
IF LWB in >= UPB in THEN in
ELSE
INT n = UPB in - LWB in + 1;
[LWB in: UPB in]VALUE out;
[]VALUE even = fft(SLICE(LWB in, 2,EMPTY) ELEM in),
odd = fft(SLICE(LWB in+1,2,EMPTY) ELEM in);
INT mid in = ( UPB in + LWB in ) OVER 2;
FOR i FROM LWB in TO mid in DO
INT k = i - LWB in;
COMPL exp = complex exp(-(0I2)*pi*k/n)*odd[i];
out[i] := even[i] + exp;
out[mid in + i] := even[i] - exp
OD;
out
FI
);
FORMAT real fmt = $g(0,real width OVER 3-2)$;
FORMAT compl fmt = $f(real fmt)"⊥"f(real fmt)$;
FORMAT array compl fmt = $f(compl fmt)", "$;
printf((
$f(array compl fmt)$, fft((1, 1, 1, 1, 0, 0, 0, 0)), $l$,
$f(array compl fmt)$,
fft((0, 0.924, 0.707,-0.383,-1,-0.383, 0.707, 0.924,
0,-0.924,-0.707, 0.383, 1, 0.383,-0.707,-0.924)), $l$
))</lang>'''Output:'''
<pre>
4.000⊥.000, 1.000⊥-2.414, .000⊥.000, 1.000⊥-.414, .000⊥.000, 1.000⊥.414, .000⊥.000, 1.000⊥2.414,
.000⊥.000, .000⊥.001, .000⊥.000, .000⊥-8.001, .000⊥.000, -.000⊥-.001, .000⊥.000, .000⊥.001, .000⊥.000, .000⊥-.001, .000⊥.000, -.000⊥.001, .000⊥.000, -.000⊥8.001, .000⊥.000, -.000⊥-.001,
</pre>
| |||