User guide

220 CHAPTER 13. EXAMPLE PROGRAMS
AND try(expr) BE
{ LET v = VEC 2000
space := v+2000
writef("Trying %s*n", expr)
writef("Answer: %n*n", eval(parse(expr), 0))
}
AND start() = VALOF
{ try("(Lx x+1) 2")
try("(Lx x) (Ly y) 99")
try("(Ls Lk s k k) (Lf Lg Lx f x (g x)) (Lx Ly x) (Lx x) 1234")
try("(Y (Lf Ln n=0->1,n**f(n-1))) 5")
RESULTIS 0
}
13.6 Fas t Fourier Transform
The following program is a simple demonstration of the algorithm for the fast fourier
transform. Instead of using complex numbers, it uses integer arithmetic modulo 65537
with an appropriate N
th
root of unity.
GET "libhdr"
MANIFEST {
modulus = #x10001 // 2**16 + 1
$$ln10 // Set condition compilation flag to select data size
//$$walsh
$<ln16 omega = #x00003; ln = 16 $>ln16 // omega**(2**16) = 1
$<ln12 omega = #x0ADF3; ln = 12 $>ln12 // omega**(2**12) = 1
$<ln10 omega = #x096ED; ln = 10 $>ln10 // omega**(2**10) = 1
$<ln4 omega = #x08000; ln = 4 $>ln4 // omega**(2**4) = 1
$<ln3 omega = #x0FFF1; ln = 3 $>ln3 // omega**(2**3) = 1
$<walsh omega=1 $>walsh // The Walsh transform
N = 1<<ln // N is a power of 2
upb = N-1
}
STATIC { data=0 }