2
* Copyright (c) 1997-1999 Massachusetts Institute of Technology
4
* This program is free software; you can redistribute it and/or modify
5
* it under the terms of the GNU General Public License as published by
6
* the Free Software Foundation; either version 2 of the License, or
7
* (at your option) any later version.
9
* This program is distributed in the hope that it will be useful,
10
* but WITHOUT ANY WARRANTY; without even the implied warranty of
11
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12
* GNU General Public License for more details.
14
* You should have received a copy of the GNU General Public License
15
* along with this program; if not, write to the Free Software
16
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20
(* $Id: twiddle.ml,v 1.2 1999/02/19 17:22:19 athena Exp $ *)
22
(* This file implements various policies for either loading the twiddle
23
* factors according to various algorithms. *)
29
if (!Magic.use_wsquare) then
34
(* various policies for computing/loading twiddle factors *)
35
(* load all twiddle factors *)
36
let twiddle_policy_load_all =
37
let twiddle_expression n i _ =
38
load_var (access_twiddle (i - 1))
39
and num_twiddle n = (n - 1)
40
and twiddle_order n = forall_flat 1 n (fun i -> [i])
41
in twiddle_expression, num_twiddle, twiddle_order
44
* if n is even, compute w^n = (w^{n/2})^2, else
47
let twiddle_policy_load_odd =
48
let twiddle_expression n i twiddles =
49
if ((i mod 2) == 0) then
50
square (twiddles (i / 2))
51
else load_var (access_twiddle ((i - 1) / 2))
52
and num_twiddle n = (n / 2)
53
and twiddle_order n = forall_flat 1 n (fun i ->
54
if ((i mod 2) == 1) then [i] else [])
55
in twiddle_expression, num_twiddle, twiddle_order
57
(* compute w^n = w w^{n-1} *)
58
let twiddle_policy_iter =
59
let twiddle_expression n i twiddles =
60
if (i == 1) then load_var (access_twiddle (i - 1))
61
else times (twiddles (i - 1)) (twiddles 1)
63
and twiddle_order n = [1]
64
in twiddle_expression, num_twiddle, twiddle_order
67
* if n is even, compute w^n = (w^{n/2})^2, else
70
let twiddle_policy_square1 =
71
let twiddle_expression n i twiddles =
72
if (i == 1) then load_var (access_twiddle (i - 1))
73
else if ((i mod 2) == 0) then
74
square (twiddles (i / 2))
75
else times (twiddles (i - 1)) (twiddles 1)
77
and twiddle_order n = [1]
78
in twiddle_expression, num_twiddle, twiddle_order
81
* if n is even, compute w^n = (w^{n/2})^2, else
82
* compute w^n from w^{n-1}, w^{n-2}, and w
84
let twiddle_policy_square2 =
85
let twiddle_expression n i twiddles =
86
if (i == 1) then load_var (access_twiddle (i - 1))
87
else if ((i mod 2) == 0) then
88
square (twiddles (i / 2))
90
wthree (twiddles (i - 1)) (twiddles (i - 2)) (twiddles 1)
92
and twiddle_order n = [1]
93
in twiddle_expression, num_twiddle, twiddle_order
96
* if n is even, compute w^n = (w^{n/2})^2, else
97
* w^n = w^{floor(n/2)} w^{ceil(n/2)}
99
let twiddle_policy_square3 =
100
let twiddle_expression n i twiddles =
101
if (i == 1) then load_var (access_twiddle (i - 1))
102
else if ((i mod 2) == 0) then
103
square (twiddles (i / 2))
104
else times (twiddles (i / 2)) (twiddles (i - i / 2))
105
and num_twiddle n = 1
106
and twiddle_order n = [1]
107
in twiddle_expression, num_twiddle, twiddle_order
109
let twiddle_policy () =
110
match !Magic.twiddle_policy with
111
Magic.TWIDDLE_LOAD_ALL -> twiddle_policy_load_all
112
| Magic.TWIDDLE_ITER -> twiddle_policy_iter
113
| Magic.TWIDDLE_LOAD_ODD -> twiddle_policy_load_odd
114
| Magic.TWIDDLE_SQUARE1 -> twiddle_policy_square1
115
| Magic.TWIDDLE_SQUARE2 -> twiddle_policy_square2
116
| Magic.TWIDDLE_SQUARE3 -> twiddle_policy_square3
added
removed
gensrc/twiddle.ml
