User guide

222 CHAPTER 13. EXAMPLE PROGRAMS
AND reorder(v, n) BE
{ LET j = 0
FOR i = 0 TO n-2 DO
{ LET k = n>>1
// j is i with its bits is reverse order
IF i<j DO { LET t = v!j; v!j := v!i; v!i := t }
// k = 100..00 10..0000..00
// j = 0xx..xx 11..10xx..xx
// j’ = 1xx..xx 00..01xx..xx
// k’ = 100..00 00..0100..00
WHILE k<=j DO { j := j-k; k := k>>1 } //) "increment" j
j := j+k //)
}
}
AND check(w, n) BE
{ // Check that w is a principal nth root of unity
LET x = 1
FOR i = 1 TO n-1 DO { x := mul(x, w)
IF x=1 DO writef("omega****%n = 1*n", i)
}
UNLESS mul(x, w)=1 DO writef("Bad omega**%n should be 1*n", n)
}
AND pr(v, max) BE
{ FOR i = 0 TO max DO { writef("%I5 ", v!i)
IF i REM 8 = 7 DO newline()
}
newline()
}
AND dv(a, m, b, n) = a=1 -> m,
a=0 -> m-n,
a<b -> dv(a, m, b REM a, m*(b/a)+n),
dv(a REM b, m+n*(a/b), b, n)
AND inv(x) = dv(x, 1, modulus-x, 1)
AND add(x, y) = VALOF
{ LET a = x+y
IF a<modulus RESULTIS a
RESULTIS a-modulus
}
AND sub(x, y) = add(x, neg(y))
AND neg(x) = modulus-x
AND mul(x, y) = x=0 -> 0,
(x&1)=0 -> mul(x>>1, add(y,y)),
add(y, mul(x>>1, add(y,y)))
AND ovr(x, y) = mul(x, inv(y))