Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(57495)

Side by Side Diff: Modules/_decimal/libmpdec/literature/six-step.txt

Issue 7652: Merge C version of decimal into py3k.
Patch Set: Created 7 years, 3 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View unified diff | Download patch
OLDNEW
(Empty)
1
2
3 (* Copyright (c) 2011 Stefan Krah. All rights reserved. *)
4
5
6 The Six Step Transform:
7 =======================
8
9 In libmpdec, the six-step transform is the Matrix Fourier Transform (See
10 matrix-transform.txt) in disguise. It is called six-step transform after
11 a variant that appears in [1]. The algorithm requires that the input
12 array can be viewed as an R*C matrix.
13
14
15 Algorithm six-step (forward transform):
16 ---------------------------------------
17
18 1a) Transpose the matrix.
19
20 1b) Apply a length R FNT to each row.
21
22 1c) Transpose the matrix.
23
24 2) Multiply each matrix element (addressed by j*C+m) by r**(j*m).
25
26 3) Apply a length C FNT to each row.
27
28 4) Transpose the matrix.
29
30 Note that steps 1a) - 1c) are exactly equivalent to step 1) of the Matrix
31 Fourier Transform. For large R, it is faster to transpose twice and do
32 a transform on the rows than to perform a column transpose directly.
33
34
35
36 Algorithm six-step (inverse transform):
37 ---------------------------------------
38
39 0) View the matrix as a C*R matrix.
40
41 1) Transpose the matrix, producing an R*C matrix.
42
43 2) Apply a length C FNT to each row.
44
45 3) Multiply each matrix element (addressed by i*C+n) by r**(i*n).
46
47 4a) Transpose the matrix.
48
49 4b) Apply a length R FNT to each row.
50
51 4c) Transpose the matrix.
52
53 Again, steps 4a) - 4c) are equivalent to step 4) of the Matrix Fourier
54 Transform.
55
56
57
58 --
59
60 [1] David H. Bailey: FFTs in External or Hierarchical Memory
61 http://crd.lbl.gov/~dhbailey/dhbpapers/
62
63
OLDNEW
« no previous file with comments | « Modules/_decimal/libmpdec/literature/REFERENCES.txt ('k') | Modules/_decimal/libmpdec/literature/umodarith.lisp » ('j') | no next file with comments »

RSS Feeds Recent Issues | This issue
This is Rietveld 894c83f36cb7+