108 lines
2.6 KiB
Text
108 lines
2.6 KiB
Text
1) the function fft
|
|
|
|
{def fft
|
|
{lambda {:s :x}
|
|
{if {= {list.length :x} 1}
|
|
then :x
|
|
else {let { {:s :s}
|
|
{:ev {fft :s {evens :x}} }
|
|
{:od {fft :s {odds :x}} } }
|
|
{let { {:ev :ev} {:t {rotate :s :od 0 {list.length :od}}} }
|
|
{list.append {list.map Cadd :ev :t}
|
|
{list.map Csub :ev :t}} }}}}}
|
|
|
|
{def rotate
|
|
{lambda {:s :f :k :N}
|
|
{if {list.null? :f}
|
|
then nil
|
|
else {cons {Cmul {car :f} {Cexp {Cnew 0 {/ {* :s {PI} :k} :N}}}}
|
|
{rotate :s {cdr :f} {+ :k 1} :N}}}}}
|
|
|
|
2) functions for lists
|
|
|
|
We add to the existing {lambda talk}'s list primitives a small set of functions required by the function fft.
|
|
|
|
{def evens
|
|
{lambda {:l}
|
|
{if {list.null? :l}
|
|
then nil
|
|
else {cons {car :l} {evens {cdr {cdr :l}}}}}}}
|
|
|
|
{def odds
|
|
{lambda {:l}
|
|
{if {list.null? {cdr :l}}
|
|
then nil
|
|
else {cons {car {cdr :l}} {odds {cdr {cdr :l}}}}}}}
|
|
|
|
{def list.map
|
|
{def list.map.r
|
|
{lambda {:f :a :b :c}
|
|
{if {list.null? :a}
|
|
then :c
|
|
else {list.map.r :f {cdr :a} {cdr :b}
|
|
{cons {:f {car :a} {car :b}} :c}} }}}
|
|
{lambda {:f :a :b}
|
|
{list.map.r :f {list.reverse :a} {list.reverse :b} nil}}}
|
|
|
|
{def list.append
|
|
{def list.append.r
|
|
{lambda {:a :b}
|
|
{if {list.null? :b}
|
|
then :a
|
|
else {list.append.r {cons {car :b} :a} {cdr :b}}}}}
|
|
{lambda {:a :b}
|
|
{list.append.r :b {list.reverse :a}} }}
|
|
|
|
3) functions for Cnumbers
|
|
|
|
{lambda talk} has no primitive functions working on complex numbers. We add the minimal set required by the function fft.
|
|
|
|
{def Cnew
|
|
{lambda {:x :y}
|
|
{cons :x :y} }}
|
|
|
|
{def Cnorm
|
|
{lambda {:c}
|
|
{sqrt {+ {* {car :c} {car :c}}
|
|
{* {cdr :c} {cdr :c}}}} }}
|
|
|
|
{def Cadd
|
|
{lambda {:x :y}
|
|
{cons {+ {car :x} {car :y}}
|
|
{+ {cdr :x} {cdr :y}}} }}
|
|
|
|
{def Csub
|
|
{lambda {:x :y}
|
|
{cons {- {car :x} {car :y}}
|
|
{- {cdr :x} {cdr :y}}} }}
|
|
|
|
{def Cmul
|
|
{lambda {:x :y}
|
|
{cons {- {* {car :x} {car :y}} {* {cdr :x} {cdr :y}}}
|
|
{+ {* {car :x} {cdr :y}} {* {cdr :x} {car :y}}}} }}
|
|
|
|
{def Cexp
|
|
{lambda {:x}
|
|
{cons {* {exp {car :x}} {cos {cdr :x}}}
|
|
{* {exp {car :x}} {sin {cdr :x}}}} }}
|
|
|
|
{def Clist
|
|
{lambda {:s}
|
|
{list.new {map {lambda {:i} {cons :i 0}} :s}}}}
|
|
|
|
4) testing
|
|
|
|
Applying the fft function on such a sample (1 1 1 1 0 0 0 0) where numbers have been promoted as complex
|
|
|
|
{list.disp {fft -1 {Clist 1 1 1 1 0 0 0 0}}} ->
|
|
|
|
(4 0)
|
|
(1 -2.414213562373095)
|
|
(0 0)
|
|
(1 -0.4142135623730949)
|
|
(0 0)
|
|
(0.9999999999999999 0.4142135623730949)
|
|
(0 0)
|
|
(0.9999999999999997 2.414213562373095)
|
|
|
|
A more usefull example can be seen in http://lambdaway.free.fr/lambdaspeech/?view=zorg
|