Arndt - Algorithms for Programmers, страница 56

LIST OF IMPORTANT SYMBOLS333Appendix AList of important Symbols<xreal part of x=ximaginary part of xx∗complex conjugate of xaa sequence, e.g. {a0 , a1 , ..., an−1 }, the index always starts with zero.âtransformed (e.g. Fourier transformed) sequencemF −1 [a]emphasize that the sequences to the left and right are all of length mPn−1xk(discrete) Fourier transform (FT) of a, ck = √1nwhere z = e±2 π i/nx=0 ax zPn−1−x kinverse (discrete) Fourier transform (IFT) of a, F −1 [a]k = √1nx=0 ax zSkaa sequence c with elements cx := ax e± k 2 π i x/nH [a]discrete Hartley transform (HT) of aasequence reversed around element with index n/2aSthe symmetric part of a sequence: aS := a + aaAthe antisymmetric part of a sequence: aA := a − aZ [a]discrete z-transform (ZT) of aWv [a]discrete weighted transform of a, weight (sequence) vWv−1inverse discrete weighted transform of a, weight v=F [a](= c)[a]a~bcyclic (or circular) convolution of sequence a with sequence ba ~ac bacyclic (or linear) convolution of sequencesa ~− bnegacyclic (or skew circular) convolution of sequencesa ~{v} bweighted convolution of sequences with weight va~ bˆa∗bdyadic convolution of sequencesa ∗ac bacyclic (linear) correlationn\Nn divides Nn⊥mgcd(n, m) = 1(j%m)cyclic correlationTBD: replace ugly symbolasequence consisting of the elements of a with indices k: k ≡ j mod me.g.a(even) , a(odd)a(0%2) , a(1%2)a(j/m)sequence consisting of the elements of a with indices k: j · n/m ≤ k < (j + 1) · n/me.g.Appendix BThe pseudo language SpracheMany algorithms in this book are given in a pseudo language called Sprache.

Sprache is meant to beimmediately understandable for everyone who ever had contact with programming languages like C,FORTRAN, Pascal or Algol. Sprache is hopefully self explanatory. The intention of using Spracheinstead of e.g. mathematical formulas (cf. [4]) or description by words (cf. [11] or [19]) was to minimizethe work it takes to translate the given algorithm to one’s favorite programming language, it should bemere syntax adaptation.By the way ‘Sprache’ is the German word for language,// a comment:// comments are useful.// assignment:t := 2.71// parallel assignment:{s, t, u} := {5, 6, 7}// same as:s := 5t := 6u := 7{s, t} := {s+t, s-t}// same as (avoiding the temporary):temp := s + tt := s - ts := temp//if//if{}if conditional:a==b then a:=3with blocka>=3 then// do something ...// a function returns a value:function plus_three(x){return x + 3}// a procedure works on data:procedure increment_copy(f[],g[],n)// real f[0..n-1] input// real g[0..n-1] result{for k:=0 to n-1{g[k] := f[k] + 1}}334APPENDIX B.

THE PSEUDO LANGUAGE SPRACHE335// for loop with stepsize:for i:=0 to n step 2 // i:=0,2,4,6,...{// do something}// for loop with multiplication:for i:=1 to 32 mul_step 2{print i, ", "}will print1, 2, 4, 8, 16, 32,// for loop with division:for i:=32 to 8 div_step 2{print i, ", "}will print32, 16, 8,// while loop:i:=5while i>0{// do something 5 times...i := i - 1}The usage of foreach emphasizes that no particular order is needed in the array access (so parallelizationis possible):procedure has_element(f[],x){foreach t in f[]{if t==x then return TRUE}return FALSE}Emphasize type and range of arrays:realcomplexmod_typeintegera[0..n-1],b[0..2**n-1]m[729..1728]i[]////////hashashashasn elements (floating point reals)2**n elements (floating point complex)1000 elements (modular integers)? elements (integers)Arithmetical operators: +, -, *, /, % and ** for powering.

Arithmetical functions: min(), max(),gcd(), lcm(), ...Mathematical functions:acos(), atan(), ...sqr(), sqrt(), pow(), exp(), log(), sin(), cos(), tan(), asin(),Bitwise operators: ~, &, |, ^ for negation, and, or, xor, respectively. Bit shift operators: a<<3 shifts(the integer) a 3 bits to the left a>>1 shifts a 1 bits to the right.Comparison operators: ==, !=, <, > ,<=, >=There is no operator ‘=’ in Sprache, only ‘==’ (for testing equality) and ‘:=’ (assignment operator).A well known constant: PI = 3.14159265 . .

.The complex square root of minus one in the upper half plane: I =√−1Boolean values TRUE and FALSELogical operators: NOT, AND, OR, XORModular arithmetic: x := a * b mod m shall do what it says, i := a**(-1) mod m shall set i to themodular inverse of a.Bibliography— Textbooks & Thesis —[1] H.S.Wilf: Algorithms and Complexity, internet edition, 1994,online at ftp://ftp.cis.upenn.edu/pub/wilf/AlgComp.ps.Z[2] H.J.Nussbaumer: Fast Fourier Transform and Convolution Algorithms, 2.ed, Springer 1982[3] J.D.Lipson: Elements of algebra and algebraic computing, Addison-Wesley 1981[4] R.Tolimieri, M.An, C.Lu: Algorithms for Discrete Fourier Transform and Convolution, Springer1997 (second edition)[5] Hari Krishna Grag: Digital Signal Processing Algorithms, CRC Press, 1998[6] Charles Van Loan: Computational Frameworks for the Fast Fourier Transform, SIAM, 1992[7] Louis V.King: On the Direct Numerical Calculation of Elliptic Functions and Integrals, Cambridge University Press 1924[8] J.M.Borwein, P.B.Borwein: Pi and the AGM, Wiley 1987[9] E.Schröder: On Infinitely Many Algorithms for Solving Equations (translation by G.W.Stewartof: Ueber unendlich viele Algorithmen zur Auflösung der Gleichungen, which appeared 1870in the ‘Mathematische Annalen’)online at ftp://thales.cs.umd.edu/pub/reports/[10] Householder: The Numerical Treatment of a Single Nonlinear Equation, McGraw-Hill 1970[11] D.E.Knuth: The Art of Computer Programming, 2.edition, Volume 2: Seminumerical Algorithms, Addison-Wesley 1981,online errata list at http://www-cs-staff.stanford.edu/~knuth/[12] D.E.Knuth: The Art of Computer Programming, pre-fascicles for Volume 4,online at http://www-cs-staff.stanford.edu/~knuth/[13] R.L.Graham, D.E.Knuth, O.Patashnik: Concrete Mathematics, second printing, Addison-Wesley,New York 1988[14] J.H.van Lint, R.M.Wilson: A Course in Combinatorics, Cambridge University Press, 1992[15] H.-D.Ebbinghaus, H.Hermes, F.Hirzebruch, M.Koecher, K.Mainzer, J.Neukirch, A.Prestel,R.Remmert: Zahlen, second edition, (english translation: Numbers) Springer, 1988[16] W.H.Press, S.A.Teukolsky, W.T.Vetterling, B.P.Flannery: Numerical Recipes in C, CambridgeUniversity Press, 1988, 2nd Edition 1992online at http://nr.harvard.edu/nr/336BIBLIOGRAPHY337[17] I.N.Bronstein, K.A.Semendjajew, G.Grosche, V.Ziegler, D.Ziegler, ed: E.Zeidler: TeubnerTaschenbuch der Mathematik, vol.

1+2, B.G.Teubner Stuttgart, Leipzig 1996, the new edition ofBronstein’s Handbook of Mathematics, (english edition in preparation)[18] J.Stoer, R.Bulirsch: Introduction to Numerical Analysis, Springer-Verlag, New York, Heidelberg,Berlin 1980[19] H.Cohen: A Course in Computational Algebraic Number Theory, Springer Verlag, Berlin Heidelberg, 1993[20] William Stein: An Explicit Approach to Elementary Number Theory, Harvard University, Fall2001[21] Thomas H.Corman, Charles E.Leiserson, Ronald L.Rivest: Introduction to Algorithms, MITPress, 1990 (twenty-first printing, 1998)[22] E.T.Whittaker, G.N.Whatson: A Course of Modern Analysis, Cambridge University Press,Fourth Edition, 1927, reprinted 1990[23] L.Lorentzen and H.Waadeland: Continued Fractions and Applications, North-Holland 1992[24] C.D.Olds: Continued Fractions, The Mathematical Association of America, 1963[25] Robert Sedgewick: Algorithms in C, Addison-Wesley, 1990[26] J.Brillhart, D.H.Lehmer, J.L.Selfridge, B.Tuckerman, S.S.Wagstaff Jr.: Factorizations of bn ±1 b = 2, 3, 5, 6, 10, 11 up to high powers, Contemporary Mathematics, Volume 22, Second Edition,American Mathematical Society, 1988online at http://www.ams.org/[27] Milton Abramowitz, Irene A.Stegun (Eds.): Handbook of mathematical Functions, NationalBureau of Standards, 1964, third printing, 1965— Papers —[28] P.Duhamel, H.Hollmann: Split radix FFT algorithm, Electronis Letters 20 pp.14-16, 1984[29] P.Duhamel: Implementation of ’split-radix’ FFT algorithms for complex, real and realsymmetric data, IEEE Transactions on Acoustics, Speech and Signal Processing, ASSP-34 pp.285295, 1986[30] M.A.Thornton, D.M.Miller, R.Drechsler: Transformations Amongst the Walsh, Haar, Arithmetic and Reed-Muller Spectral Domains,[31] Moon Ho Lee, B.Sundar Rajan, J.Y.Park: A Generalized Reverse Jacket Transform,[32] H.Malvar: Fast computation of the discrete cosine transform through fast Hartley transform,Electronics Letters 22 pp.352-353, 1986[33] H.Malvar: Fast Computation of the discrete cosine transform and the discrete Hartley transform, IEEE Transactions on Acoustics, Speech and Signal Processing, ASSP-35 pp.1484-1485, 1987[34] F.Arguello, E.L.Zapata: Fast Cosine Transform on the Successive Doubling Method,[35] S.Gudvangen: Practical Applications of Number Theoretic Transforms,[36] R.Crandall, B.Fagin: Discrete Weighted Transforms and Large Integer Arithmetic, Math.Comp.

(62) 1994 pp.305-324[37] Daniel J.Bernstein: Multidigit Multiplication for Mathematicians, 1998BIBLIOGRAPHY338[38] Susan Landau, Neil Immermann: The Similarities (and Differences) between Polynomials andIntegers, 1996[39] Peter John Potts: Computable Real Arithmetic Using Linear Fractional Transformations, 1996[40] Zhong-De Wang: New algorithm for the slant transform, IEEE Transactions Pattern Anal. Mach.Intell. PAMI-4, No.5, pp.551-555, September 1982[41] R.P.Brent: Fast multiple-precision evaluation of elementary functions, J. ACM (23) 1976pp.242-251[42] B.Haible, T.Papanikolaou: Fast multiprecision evaluation of series of rational numbers,[43] J.M.Borwein, P.B.Borwein: ?title?, Article in Scientific American, March 1988[44] D.H.Bailey, J.M.Borwein, P.B.Borwein and S.Plouffe: The Quest for Pi, 1996,online at http://www.cecm.sfu.ca/~pborwein/[45] J.M.Borwein, P.B.Borwein: Cubic and higher order algorithms for π , Canad.Math.Bull.

Vol.27(4), 1984, pp.436-443[46] J.M.Borwein, P.B.Borwein, F.G.Garvan: Some cubic modular identities of Ramanujan, Transactions A.M.S. 343, 1994, pp.35-47[47] J.M.Borwein, F.G.Garvan: Approximations to π via the Dedekind eta function, March 27, 1996[48] D.V.Chudnovsky, G.V.Chudnovsky: Classical constants and functions: computations and continued fraction expansions, in Number Theory: New York seminar 1989-1990, Springer Verlag1991[49] H.Cohen, F.R.Villegas, D.Zagier: Convergence acceleration of alternating series, 1997[50] D.H.Bailey: FFTs in External or Hierarchical Memory, 1989[51] D.H.Bailey: The Fractional Fourier Transform and Applications, 1995online at http://citeseer.nj.nec.com/[52] D.H.Bailey: On the Computation of FFT-based Linear Convolutions, June 1996[53] M.Beeler, R.W.Gosper, R.Schroeppel: HAKMEM, MIT AI Memo 239, Feb.