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

29, 1972, Retypedand converted to html by Henry Baker, April 1995,online at ftp://ftp.netcom.com/pub/hb/hbaker/[54] Advanced Micro Devices (AMD) Inc.: AMD Athlon Processor, x86 code optimization guide,Publication #22007, Revision H, June 2000online at http://www.amd.com/[55] P.Soderquist, M.Leeser: An Area/Performance Comparison of Subtractive and MultiplicativeDivide/Square Root Implementations, Cornell School of Electrical Engineeringonline at http://orac.ee.cornell.edu:80/unit1/pgs/#papers[56] F.L.Bauer: An Infinite Product for Square-Rooting with Cubic Convergence, The Mathematical Intelligencer, 1998[57] Bahman Kalantari, Jürgen Gerlach: Newton’s Method and Generation of a DeterminantalFamily of Iteration Functions, 1998[58] Nicholas J.Higham: Stable Iterations for the Matrix Square Root, August 1997[59] Eugene Salamin: Application of Quaternions to Computation with Rotations, Working Paper,Stanford AI Lab, 1979, Edited and TeX-formatted by Henry G.Baker, 1995online at ftp://ftp.netcom.com/pub/hb/hbaker/BIBLIOGRAPHY339[60] Thomas D.Howell, Jean-Claude Lafon: The Complexity of the Quaternion Product, Departmentof Computer Science, Cornell University, Ithaca, NY, June 1975online at ftp://ftp.netcom.com/pub/hb/hbaker/[61] PaweÃl Zieliński, Krystyna Ziȩtak: The Polar Decomposition – Properties, Applications andAlgorithms, Annals of the Polish Mathematical Society, 38, 1995online at http://citeseer.nj.nec.com/[62] Nicholas J.Higham: The Matrix Sign Decomposition and its Relation to the Polar Decomposition, Linear Algebra and Appl., 212/213, 1994[63] Erik Weisstein: MathWorld,online at http://mathworld.wolfram.com/[64] N.J.A.Sloane: The On-Line Encyclopedia of Integer Sequencesonline at http://www.research.att.com/~njas/sequences/[65] K.Cattel, S.Zhang, X.Sun, M.Serra, J.C.Muzio, D.M.Miller: One-Dimensional Linear HybridCellular Automata: Their Synthesis, Properties, and Applications in VLSI Testing,[66] Kevin Cattel, Shujian Zhang: Minimal Cost One-Dimensional Linear Hybrid Cellular Automata of Degree Through 500, 1994[67] Andrew Klapper, Mark Goresky: Feedback Shift Registers, 2-Adic Span and Combiners WithMemory, 1996[68] Mark Goresky, Andrew Klapper: Fibonacci and Galois Representations of Feedback with CarryShift Registers, 2000[69] Carla Savage: A Survey of Combinatorial Gray Codes,online at http://citeseer.nj.nec.com/[70] Nirmal R.Saxena,Edward J.McCluskey:Degree-r Primitive PolynomialO(r3 ) ∼ O(r4 ) Algorithms, Center for Reliable Computing, Stanford UniversityGeneration-[71] Kevin Cattell, Frank Ruskey, Joe Sawada, C.Robert Miers, Micaela Serra: Generating UnlabeledNecklaces and Irreducible Polynomials over GF(2), Department of Computer Science, Universityof Victoria, Canada, 1998[72] Frank Ruskey: Simple combinatorial Gray codes constructed by reversing sublists, Departmentof Computer Science, University of Victoria, Canada, 1993[73] T.A.Jenkyns: Loopless Gray Code Algorithms,— Software —[74] Mikko Tommila: apfloat, A High Performance Arbitrary Precision Arithmetic Package, 1996,online at http://www.jjj.de/mtommila/[75] The PARI Group (C.Batut, K.Belabas, D.Bernardi, H.Cohen, M.Olivier et.al.): PARI/GP,online at http://www.parigp-home.de/[76] The Free Software Foundation (FSF): GCC, the GNU Compiler Collection,online at http://www.gnu.org/gcc/IndexAcos rot() 64cosine transform (DCT) 64CRT for two moduli 76CRT, Chinese Remainder Theorem 76cube root extraction 285cycles, of a permutation 143cyclic convolution 41cyclic convolution, by FFT 42...............................................acyclic (linear) convolution 43AGM (arithmetic geometric mean) 303AGM, 4-th order variant 305apply permutation() 142arithmetic geometric mean (AGM) 303B...............................................basis functions, Reed-Muller transform 99binary search 201bit rotate sgn() 196bitarray (class) 221bitpol mult() 198bitpolmod mult() 198bsearch 201bsearch ge() 201CD...............................................DCT (discrete cosine transform) 64DCT via FHT 64dcth() 65dcth zapata() 65debruijn (class) 251DFT (discrete Fourier transform), definition 10direct mapped cache 36discrete cosine transform, inverse (IDCT) 65discrete Fourier transform, definition 10division, using only multiplication 283DST (discrete sine transform) 65dsth() 66...............................................C2RFT see real FFTC2RFT (complex to real FT) 28cache, direct mapped 36carry, in multiplication 281Catalan numbers 239Chinese Remainder Theorem 76comb alt minchange (class) 234comb colex (class) 232comb lex (class) 230comb minchange (class) 232composition lex (class) 243convexity 208convexity, strict 209convolution– acyclic (linear), 43– and multiplication, 280– by FHT, 66– cyclic, 41– cyclic, by FHT, 66– exact, 76– half cyclic, 49– linear, 43– mass storage, 46– negacyclic, 49, 68– right-angle, 49– skew circular, 49– weighted, 48E...............................................exact convolution 76exp, iteration for 306F...............................................fcsr (class) 269FFT– as polynomial evaluation, 282– radix 2 DIF, 18– radix 2 DIT, 16– radix 2 DIT, localized, 15– radix 4 DIF, 24– radix 4 DIT, 23– split radix DIF, 26FFT (fast Fourier transform) 11fft arblen() 54fft dif2() 18fft dif4() 25fft dif4 core() 25fft dif4l() 25fft dit2() 16fft dit4() 24340INDEXfft dit4 core() 24fft dit4l() 24fft fract() 54fft localized dit2() 16FHT– convolution by, 66– DIF step, 58– DIF, recursive, 58– DIT, recursive, 56– radix 2 DIF, 59– radix 2 DIT, 56– radix 2 DIT step, 55– shift operator, 56FHT (fast Hartley transform) 55fht auto convolution() 68fht complex real fft() 64fht convolution() 42, 67fht convolution0() 42fht dif2() 60fht dif core() 20, 62fht dit2() 58fht dit core() 62fht fft() 62fht fft conversion() 61, 62fht fft convolution() 42fht localized dif2() 60fht localized dit2() 58fht mul() 87fht negacyclic auto convolution() 68fht negacyclic convolution() 68fht real complex fft() 63fixed points, of lex-order words 171Fourier shift operator 15Fourier transform, definition 10fourier shift() 15FT (Fourier transform), definition 10funcemu (class) 235G...............................................green permute() 138grs negate() 85H...............................................haar() 106Haar transform, inverse, int to int 118haar i2i() 118haar inplace() 107haar inplace nn() 110haar nn() 109haar rev nn() 114half cyclic convolution 49Hartley shift 56Hartley transform see FHThartley shift 05() 56341hilbert() 186HT (Hartley transform), definition 55I................................................IDCT (inverse descrete cosine transform) 65IDCT by FHT 65idcth() 65IDST (inverse discrete sine transform) 66idsth() 66inverse cosine transform (IDCT) 65inverse cube root, iteration for 285inverse discrete sine transform (IDST) 66inverse Haar transform, int to int 118inverse modulo m 73inverse root extraction 287inverse root, iteration for 288inverse square root, iteration for 284inverse haar() 106inverse haar i2i() 119inverse haar inplace() 108inverse walsh gray() 85inversion, iteration for 283is lexrev fixed point() 172iteration– for exp, 306– for inverse cube root, 285– for inverse root, 288– for inverse square root, 284– for inversion, 283– for log, 305K...............................................Karatsuba multiplication 280L...............................................lfsr (class) 254lhca next() 270linear convolution 43log, iteration using exp 305long memchr() 186long strlen() 186lowest zero() 158M..............................................mass storage convolution 46matrix multiplication 88matrix fft auto convolution() 46matrix fft auto convolution0() 46matrix fft convolution() 46matrix fft convolution0() 46maxorder element mod() 73mean, arithmetic geometric 303mixed radix lex (class) 246mod (class) 73INDEXmodulus, composite 70modulus, prime 69monotonicity 207monotonicity, srict 208multiplication– by FFT, 280– carry, 281– is convolution, 280– Karatsuba, 280multiplication, of matrices 88multiplication, of quaternions 88N...............................................ndim fft() 35negacyclic convolution 49, 68negacyclic complex auto convolution() 49NTT– radix 2 DIF, 74– radix 2 DIT, 73– radix 4, 75ntt dif2() 75ntt dif4() 76ntt dit2() 74ntt dit4() 76O...............................................order of an element, maximal 71ordered rarray (class) 225P...............................................paren2 (class) 238partition (class) 241partitioning, for quicksort 200perm derange (class) 152perm derange::make next() 152perm lex (class) 148perm lex::next() 148perm minchange (class) 150perm minchange::make next() 150perm star (class) 153perm trotter (class) 151perm trotter::make next() 151perm visit (class) 154permutation, inverse of 143permutation, random 146phi function, number thoeretic 70power() 147prime string (class) 251primitive root 69primitive root, finding 70priority queue (class) 221Q...............................................quantise 206342quantise() 206quaternion multiplication 88queue (class) 214quicksort 200R...............................................R2CFT see real FFTR2CFT (real to complex FT) 28radix permute() 127random permutation 146rarray (class) 222real FFT– by FHT, 63– split radix algorithm, 31– with wrap routines, 29recursive fft dif2() 18recursive fft dit2() 15recursive fht dif2() 59recursive fht dit2() 56Reed-Muller transform, basis functions 99revbin-update 121revbin permute() 126revbin permute, naive 120revbin permute0() 126revbin update() 122reverse nh() 28right-angle convolution 49right angle complex auto convolution() 49ringbuffer (class) 213root extraction 287root, primitive 69rotate, by triple reversion 128rotate left() 128rotate right() 128rotate sgn() 101row column algorithm 35rset (class) 226S...............................................search, downward 201selection sort 199sequency 91shift operator, for Fourier transform 15shift, for FHT 56sine transform (DST) 65sine transform, inverse (IDST) 66skew circular convolution 49slant() 98slant transform 97slant transform, sequency ordered 98slow ft() 11sorting, of complex numbers 204split radix complex real fft() 34split radix fft() 27INDEXsplit radix fft convolution() 42split radix real complex fft() 32square root, iteration for 284subset debruijn (class) 251subset lex (class) 248subset minchange (class) 249subset monotone (class) 250symbolify by order() 206symbolify by size() 206T...............................................totient function 70transpose() 127transpose2 ba() 127, 221transpose ba() 127, 221transposed haar inplace nn() 113transposed haar nn() 111transposed haar rev nn() 114twodim fft() 35U...............................................ulong minweight lhca rule() 270ulong minweight primpoly() 257unique 205unzip() 130unzip rev() 131W..............................................walsh gray() 85walsh pal() 91walsh pal basefunc() 91walsh q1() 95walsh q1 basefunc() 97walsh q2() 95walsh q2 basefunc() 97walsh wak basefunc() 82walsh wak dif2() 82, 100walsh wak dit2() 81, 100walsh wal basefunc() 91walsh wal rev() 93, 94walsh wal rev basefunc() 95weighted convolution 48weighted complex auto convolution() 49weighted fft() 48weighted inverse fft() 48word reed muller basefunc() 102word reed muller dif2() 100wrap complex real fft() 31wrap real complex fft() 31X...............................................xor permute() 132xrevbin() 197343Z...............................................zip() 129zip rev() 131.