Fast Fourier transform: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,473: / Line 1,473: @@
 =={{header|lambdatalk}}==
 <lang scheme>
-From a code written by Prasenjit Saha in https://www.physik.uzh.ch/~psaha/mus/fourlisp.php]] we build the FFT using lists.
 ) the function fft
 {def fft
- {lambda {:s :f}
+ {lambda {:s :x}
-  {if {= {list.length :f} 1}
+  {if {= {list.length :x} 1}
-   then :f
+   then :x
-   else {combine :s {fft :s {evens :f}}
+   else {let { {:s :s}
-                    {fft :s {odds :f}}} }}}
+               {:ev {fft :s {evens :x}} }
+               {:od {fft :s {odds  :x}} } }
+        {let { {:ev :ev} {:t {rotate :s :od 0 {list.length :od}}} }
-{def combine
- {lambda {:s :ev :od}
+        {list.append {list.map Cadd :ev :t}
-  {plusminus :ev {rotate :s 0 {list.length :od} :od}}}}
+                     {list.map Csub :ev :t}} }}}}}
-{def plusminus
- {lambda {:a :b}
-  {list.append {list.map Cadd :a :b}
-               {list.map Csub :a :b}}}}
 {def rotate
- {lambda {:s :k :N :f}
+ {lambda {:s :f :k :N}
   {if {list.null? :f}
    then nil
-   else {cons {Cmul {car :f}
+   else {cons {Cmul {car :f} {Cexp {Cnew 0 {/ {* :s {PI} :k} :N}}}}
-                    {Cexp {Cnew 0 {/ {* :s {PI} :k} :N}}}}
+              {rotate :s {cdr :f} {+ :k 1} :N}}}}}
-              {rotate :s {+ :k 1} :N {cdr :f}}}}}}
 ) functions for lists