Index 951 Index Symbols ..................................... algebra 815 -2 (minus two), representations with radix -2 58 all-ones polynomial 852, 912 2n -ions (hypercomplex numbers) 816 all-ones polynomials, trace vector 896 999, computation 454 all_irredpoly (C++ class) 857 E, elliptic integral 603 alternating permutations 281 K, elliptic integral 601 alternating series, and continued fractions 722 2, 3, and 4 (theta functions) 604 alternating series, sumalt algorithm 662 ", cyclic convolution 440 AND-convolution 490 "{v} , weighted convolution 449 applying a permutation to data, in-place 109 "lin, linear convolution 443 approximations, initial, for iterations 575 ss computation arbitrary length FFT 455 - AGM vs. binary splitting, 656 arc (edge) of a digraph 391 - iterative algorithms, 615 arctan relations for ss 633 - with arctan relations, 633 arctan, computation by rectangular scheme 658 oee(n), sum of e-th powers of divisors of n 708 argument reduction '(n), Euler's totient function 776 - for arctan, 625 ii = exp (-ss=2), computation 627 - for cos, 629 zz , series for 702 - for exp, 629 j -function (eta function) 344, 607, 711 - for log, 625 ~ (n), M"obius function 705 arithmetic transform Wv [], weighted transform 448 - (definition), 483 \ (d\n means "d divides n") 535 - convolution property, 489 2D FHT 530 - reversed, 485 2D Hilbert curve 83, 747 - weighted, 492 arithmetic, modular 764 A ................................................ arithmetic-geometric mean (AGM) 599 AC (adjacent changes), Gray code 399 arithmetical shift, of a binary word 3 acceleration of convergence, sumalt algorithm 662 array notation 172 ACF (auto-correlation function) 445, 875 array, of bits 164 acyclic (linear) convolution 443 asm trick, with GCC 3, 532 acyclic (linear) correlation 444 auto-correlation function (ACF) 445, 875 addition, modulo m 764 average, of two integers, without overflow 5 additive group, with a ring 775 additive inverse, modulo m 767 B ................................................. adjacency matrix of a graph 391 backtracking 391 adjacent changes (AC), Gray code 399 bag (multiset) 295 adjacent nodes in a graph 391 base (radix) conversion 656 AGM base field 804, 886 - (arithmetic-geometric mean), 599 basis functions - 4th order variant, 600 - arithmetic transform, 483 - and hypergeometric functions, 611 - blue, yellow, red, green transform, 488 - vs. binary splitting, 656 - Fibonacci-Haar transform, 513 952 Index - Fibonacci-Walsh transform, 513 bitrev permutation 118 - Haar transform, 498 BITS_PER_LONG 2 - in-place Haar transform, 499 bitset, testing for subset 23 - Mersenne-Walsh transform, 514 blocks of bits, counting 20 - prefix transform, 511 blocks of bits, creation 11 - Reed-Muller transform, 486 blocks, swapping via quadruple reversal 124 - reversed arithmetic transform, 485 blue code 49, 377 - reversed Haar transform, 505 blue code, fixed points 53 - Walsh transform (Walsh-Kacmarz), 474 bracelets, as equivalence classes 150 - Walsh transform (Walsh-Kronecker), 461 branches, avoiding them 25 - Walsh transform (Walsh-Paley), 473 bsearch 141 - weighted arithmetic transform, 493 bswap instruction 34 Beatty sequence 756 built-ins, GCC 21 Bell numbers 151, 358 butterfly diagram, for radix-2 transforms 460 Bell polynomials 359 byte-wise Gray code and parity 42 Ben-Or test for irreducibility 837 BYTES_PER_LONG 2 Berlekamp's Q-matrix algorithm 858 Bhaskara equation 812 C ................................................. big endian machine 2 C++ class XYZ see XYZ (C++ class) binary exponentiation 563 C2RFT see real FFT binary finite field 804, 886 C2RFT (complex to real FFT) 431 binary GCD algorithm 767 carries with mixed radix counting 220 binary heap 160 carry, in multiplication 558 binary polynomial 822 CAT, constant amortized time 173 binary powering 563 catalan (C++ class) 325 binary relation 148 Catalan constant 663 binary search 141 Catalan numbers 331, 589 binary splitting Catalan objects (combinatorial structures counted - for rational series, 651 by Catalan numbers) 323 - vs. AGM, 656 Cayley numbers 816 - with continued fractions, 720 Cayley-Dickson construction 815 binary_debruijn (C++ class) 208, 379 characteristic polynomial binary_necklace (C++ class) 373 - of a matrix, 899 Binet form, of a recurrence 674 - of a recurrence relation, 666 binomial coefficient - with Fourier transform, 534 - and type-2 ONB, 913 characteristic, of a field 886 - modulo a prime, 914 Chase's sequence, for combinations 190 - number of combinations, 176 Chebyshev polynomials bit combinations 62 - (definition), 676 bit counting 18 - and Pell's equation, 814 bit subsets, via sparse counting 68 - and products for the square root, 684 bit-array 164 - and recurrence for subsequences, 672 bit-array, fitting in a word 24 - and square root approximants, 683 bit-block boundaries, determination 12 - as hypergeometric functions, 695 bit-reversal 34 - fast computation, 680 bit-reversal permutation 118 - with accelerated summation, 663 bit-wise checking pair, of arctan relations 640 - reversal, 33 Chinese Remainder Theorem (CRT) 772 - rotation, 27 Chinese Remainder Theorem, for convolution 542 - zip, 38 chirp z-transform 455 bit_fibgray (C++ class) 76 circuit in a graph 391 bit_necklace (C++ class) 30 circulant matrix 447, 905 bit_subset (C++ class) 68 Clausen's product 691 bit_subset_gray (C++ class) 69 CLHCA (cyclic LHCA) 883 bitarray (C++ class) 164 clz (Count Leading Zeros), GCC built-in 21 Index 953 co-lexicographic order - Komornik-Loreti, 729 - (definition), 172 - paper-folding, 744 - for combinations, 177 - parity number, 726 - for compositions, 194 - Pell, 758 - for permutations, 243 - Pell Gray code, 762 - for subsets of a multiset, 295 - Pell palindromic, 759 - with bit combinations, 62 - period-doubling, 735 colex (co-lexicographic) order 172 - rabbit, 753 comb_rec (C++ class) 191 - revbin, 741 combination_chase (C++ class) 191 - Roth's, 731 combination_colex (C++ class) 178 - ruler, 734 combination_emk (C++ class) 185 - sum of Gray code digits, 744 combination_enup (C++ class) 188 - sum-of-digits, 740 combination_lex (C++ class) 177 - Thue, 731 combination_mod (C++ class) 186 - weighted sum of Gray code digits, 747 combination_pref (C++ class) 180 - weighted sum-of-digits, 741 combination_revdoor (C++ class) 183 constant amortized time (CAT) 173 combinations (k-subsets) of a multiset 296 contiguous relations, for hypergeometric series 689 combinations, Gray code, with binary words 66 continued fraction 716 combinations, of k bits 62 continued fractions, as matrix products 720 combinatorial Gray code 172 convergent, of a continued fraction 716 companion matrix 667, 899 conversion, float to int 6 comparison function, for sorting 145 conversion, of the radix (base) 656 compiler, smarter than you thought 26 convolution complement, of a permutation 103 - acyclic (linear), 443 complement-shift sequences 397 - and Chinese Remainder Theorem, 542 complementary (dual) basis 908 - and circulant matrices, 447 complementing the sequency of a binary word 48 - and multiplication, 558 complete elliptic integral see elliptic integral - AND-convolution, 490 complete graph 393 - by FFT, without revbin permutations, 442 complex numbers, construction 804 - by FHT, 525 complex numbers, mult. via 3 real mult. 806 - cyclic, 440 complex numbers, sorting 146 - cyclic, by FHT, 525 composite modulus 776 - dyadic, 481 compositeness of an integer, test for 786 - exact, 542 composition of permutations 108 - linear, 443 composition, of permutations 105 - mass storage, 453 composition_colex (C++ class) 195 - MAX-convolution, 491 composition_colex2 (C++ class) 195 - negacyclic, 451, 528 composition_ex_colex (C++ class) 196 - OR-convolution, 489 compositions 194 - property, of the Fourier transform, 441 computation of ss, AGM vs. binary splitting 656 - right-angle, 450 conditional search, for paths in a graph 398 - skew circular, 451 conference matrix 386 - weighted, 449 conjugates of an element in GF(2n ) 892 - XOR-convolution, 481 connected permutation 103, 281 cool-lex order see prefix shifts order connected permutation, random 117 Cooley-Tukey FFT algorithm 412 connection polynomial 864 coprime: a coprime to b () gcd (a, b) = 1 535 constant copying one bit 7 - Catalan, 663 CORDIC algorithms 646 - CORDIC scaling, 647, 650 correlation 444 - Fibonacci parity, 755 and circulant matrices, 447 - Golay-Rudin-Shapiro, 732 cosine and cosh, as hypergeometric function 697 - Gray code, 742 cosine, by rectangular scheme 661 - GRS, 732 cosine, CORDIC algorithm 646 954 Index cosine, in a finite field 808 delta squared process 598 counting bits of a sparse word 20 demo-programs, and timing 175 counting bits of a word 18 deque (C++ class) 158 counting sort 136 deque (double-ended queue) 158 coupled iteration, for the square root 569 derangement 102, 280 CPU instructions, often missed 82 derangement order, for permutations 264 CRC (cyclic redundancy check) 868 derangement, random 115 crc32 (C++ class) 870 DFT (discrete Fourier transform) 410 crc64 (C++ class) 868 DIF (decimation in frequency) FFT 414 Creutzburg-Tasche primitive root 808 difference sets, and correlation 447 cross-correlation 445 digraph 391 CRT (Chinese Remainder Theorem) 772 digraph (C++ class) 392 ctz (Count Trailing Zeros), GCC built-in 21 digraph_paths (C++ class) 393 cube root extraction 569 directed graph 391 cubic convergence 587 discrete Fourier transform (DFT) 410 cycle in a graph 391 discrete Hartley transform 515 cycle type, of a permutation 278 DIT (decimation in time) FFT 412 cycle-leaders divides: d\n means "d divides n" 535 - of the Gray permutation, 128, 376 division cycles, of a permutation 104 - algorithm using only multiplication, 567 cyclic convolution - CORDIC algorithm, 648 - (definition), 440 - exact, by C = 2k 1, 57 - computation via FFT, 442 - exact, with polynomials over GF(2), 826 cyclic correlation 444 divisionless iterations for polynomial roots 586 cyclic distance, with binary words 32 divisors (C++ class) 295 cyclic group 778 divisors of n, sum of e-th powers, oee(n) 708 cyclic LHCA (CLHCA) 883 Dobinski's formula, for Bell numbers 359 cyclic period, of a binary word 30 double buffer, for mass storage convolution 454 cyclic permutation 105 double-ended queue (deque) 158 cyclic permutation, random 112 dragon curve sequence 90 cyclic permutations 285 dual basis 908 cyclic redundancy check (CRC) 868 dyadic convolution 481 cyclic XOR 32 Dyck words cyclic_perm (C++ class) 287 - k-ary, 333 cyclotomic polynomials - binary, 323 - (definition), 704 dyck_gray (C++ class) 333 - and primes, 802 dyck_gray2 (C++ class) 333 - and primitive binary polynomials, 857 dyck_rgs (C++ class) 333 D ................................................ E ................................................. Daubechies wavelets 547 E, elliptic integral 603 De Bruijn graph 395 Eades-McKay sequence, for combinations 183 De Bruijn sequence easy case, with combinatorial generation 174 - (definition), 873 edge of a graph 391 - for computing bit position, 14 edge sorting, with graph search 402 - lex-min DBS via necklaces, 377 EGCD (extended GCD) 768, 836 - number of DBSs, 874 EGCD, to compute Pad'e approximant 595 - with subsets, 208 EGF (exponential generating function) 173 De Bruijn sequence eigenvectors of the Fourier transform 533 - as path in a graph, 395 eight-square identity 819 debruijn (C++ class) 377 element of order n 535 decimation in frequency (DIF) FFT 414 elementary functions, as hypergeometric f. 694 decimation in time (DIT) FFT 412 elliptic E (complete elliptic integral) 603 delta sequence 447 elliptic K (complete elliptic integral) 601 delta set 172 elliptic integrals, as hypergeometric functions 700 Index 955 endian-ness, of a computer 2 ffs (Find First Set), GCC built-in 21 endo (Even Numbers DOwn) order 186 FFT endo order, for mixed radix numbers 226 - as polynomial evaluation, 559 enup (Even Numbers UP) order 187 - radix-2 DIF, 416 enup order for combinations 188 - radix-2 DIT, 414 enup order, with permutations 272 - radix-4 DIF, 423 equivalence classes 148 - radix-4 DIT, 420 equivalence relation 148 - split-radix algorithm, 425 equivalence relations, number of 151 FFT (fast Fourier transform) 411 Eratosthenes, prime sieve 770 FFT caching 564 eta function (j -function) 344, 607, 711 FFT, for multiplication 558 Euclidean algorithm 767 FFT-primes 536 Euler numbers 282 FHT Euler's identity, for hypergeometric functions 689 - convolution by, 525 Euler's totient function 776 - DIF step, 519 exact convolution 542 - DIF, recursive, 519 exact division 56 - DIT, recursive, 516 exact division, by C = 2k 1 57 - radix-2 DIF, 520 exact division, with polynomials over GF(2) 826 - radix-2 DIT, 517 expect (with branch prediction), GCC built-in 21 - radix-2 DIT step, 516 exponent, of a group 776 - shift operator, 516 exponential convergence 587 FHT (fast Hartley transform) 515 exponential function Fibbinary numbers 62, 755 - as hypergeometric function, 696 Fibonacci - bit-wise computation, 643 - k-step sequence, 309 - by rectangular scheme, 660 - parity, 754 - computation via q = exp (-ss K0=K), 627 - parity constant, 755 - iteration for, 627 - polynomials, 914 - of power series, 631 - representation, 754 exponential generating function (EGF) 173 - setup, of a shift register, 867 exponentiation - words, 305 - algorithms, 563 - words, Gray code, 76, 306 - modulo m, 766 - words, shifts-order, 210 extended GCD (EGCD) 768, 836 Fibonacci numbers 754 extended GCD, to compute Pad'e approximant 595 Fibonacci-Haar transform 512 extension field 804, 886 Fibonacci-Walsh transform 513 external algorithms 453 field polynomial 886 extraneous fixed point, of an iteration 593 FIFO (first-in, first-out), queue 156 filter, for wavelet transforms 544 F ................................................. finite field 804 factorial number system 232 finite field, binary 886 factorial numbers, and cyclic permutations 289 finite field, with prime modulus 776 factorial, binsplit algorithm for 651 Fisher-Yates shuffle 111 factorial, rising factorial power 685 fixed point, of a function 587 factorization of binary polynomials 858 fixed point, of an iteration, extraneous 593 falling factorial 176 fixed points, of the blue code 53 falling factorial base 232 FKM algorithm 371 fast Fourier transform (FFT) 411 FKM algorithm, for binary words 30 fast Hartley transform (FHT) 515 four step FFT 438 fcsr (C++ class) 876 four-square identity 819 FCSR (feedback carry shift register) 876 Fourier shift operator 413 feedback carry shift register (FCSR) 876 Fourier transform 410 Fermat numbers 795 Fourier transform, convolution property 441 Fermat primes 782 fractional (order) Fourier transform 533 Ferrers diagram (with integer partitions) 345 fractional Fourier transform 456 956 Index free element (normal element) 901 Halley's formula 588, 592 full path in a graph 391 Hamiltonian cycle 391 Hanoi, towers of, puzzle 735 G ................................................ Hartley shift 516 Galois field 886 Hartley transform 515 Galois setup, of a shift register 867 hashing, via CRC 868 Gauss' transformation 690 heap 160 Gaussian normal basis 914 Heap's algorithm for permutations 248 GCC, built-ins 21 heapsort 141 GCD (greatest common divisor), computation 767 Heighway dragon 90 generalized subset-lex (gslex) order 224 hexdragon 95 generating functions, for combinatorial objects 173 high bits of a word, operations on 14 generator in GF(2n ) 889 Hilbert curve generator of a group 776 - function encoding it, 747 generator, modulo p 457 - moves, 83 generator, program producing programs 531 - turns, 85, 749 GF(2n ) (binary finite field) 886 homogeneous moves, with combinations 183, 188 GF2n (C++ class) 890, 910 homogenous moves, with k-subsets 215 GNB (Gaussian normal basis) 914 Householder's iteration 592 Golay-Rudin-Shapiro constant 732 Householder's method 588 Golay-Rudin-Shapiro sequence 44, 731 hybrid linear cellular automaton (LHCA) 878 Goldschmidt algorithm 581 hyperbolic sine and cosine, by CORDIC 649 Gray code hypercomplex numbers 816 - and radix -2 representations, 59 hypergeometric function - binary, reversed, 45 - (definition), 685 - combinatorial (minimal-change order), 172 - AGM algorithms, 611 - constant, 742 hypergeometric series - for combinations, 182 - (definition), 685 - for combinations of a binary word, 66 - conversion to continued fraction, 724 - for Fibonacci words, 76, 306 - transformations, 688 - for Lyndon words, 403 - for mixed radix numbers, 220 I .................................................. - for multiset permutations, 301 identical permutation 102 - for Pell words, 313, 760 ii = exp (-ss=2), computation 627 - for sparse signed binary words, 315 in-place routine 413 - for subsets of a bitset, 69 indecomposable permutation 103, 281 - for subsets, with shifts-order, 209 indecomposable permutation, random 117 - of a binary word, 41 index of an element modulo m 775 - powers of, 48 index of the single set bit in a word 13 - single track, 403 index sort 142 Gray permutation 128 infinite products, from series 709 gray_cycle_leaders (C++ class) 129 inhomogeneous recurrence 670 greatest common divisor (GCD), computation 767 initial approximations, for iterations 575 green code 50 integer partitions 339 ground field 804, 886 integer sequence group, cyclic 778 - 1's-counting seq., 739 GRS (Golay-Rudin-Shapiro) sequence 44, 731 - Beatty seq. with , 756 GRS constant 732 - Bell numbers, 151, 358 gslex order, for mixed radix numbers 224 - Carmichael numbers, 786 - Catalan numbers, 331, 589 H ................................................ - connected permutations, 281 Haar transform 497 - dragon curve seq., 90 Hadamard matrix 384, 817 - Euler function '(n), 776 Hadamard transform 459 - Euler numbers, 282 half-trace, in GF(2n ) with n odd 898 - F-increment RGS, 368 Index 957 - Feigenbaum symbolic seq., 735 - A000009, 348 - Fibbinary numbers, 62, 755 - A000010, 776 - Fibonacci numbers, 309, 312, 754 - A000011, 151 - fixed points in lex-rev seq., 73 - A000013, 151, 408 - Golay-Rudin-Shapiro seq., 44, 731 - A000029, 151 - Gray codes, 742 - A000031, 151, 380 - GRS (Golay-Rudin-Shapiro) seq., 44, 731 - A000041, 345 - hypercomplex multiplication, 817 - A000043, 797 - indecomposable permutations, 281 - A000045, 309, 312, 314, 318, 320, 627, 754 - integer partitions, 345 - A000048, 408, 848 - involutions, 279 - A000073, 309 - irreducible polynomials, 843 - A000078, 309 - irreducible self-reciprocal polynomial, 846 - A000079, 282 - irreducible trinomials, 848 - A000085, 279 - K-increment RGS, 369 - A000108, 331, 337 - Kronecker symbol -1_n, 745 - A000110, 151, 358, 368 - Lyndon words, 843 - A000111, 282 - max-increment RGS, 364 - A000120, 493, 739 - Mephisto Waltz seq., 730 - A000123, 728 - Moser - De Bruijn sequence, 59, 750 - A000129, 627, 758 - necklaces, 380 - A000166, 280 - non-generous primes, 780 - A000201, 756 - number of XYZ, see number of, XYZ - A000203, 352 - optimal normal bases, type-1, 912 - A000213, 312 - optimal normal bases, type-2, 912 - A000255, 280 - paper-folding seq., 88, 744 - A000288, 312 - paper-folding seq., signed, 745 - A000296, 360 - paren words, 78 - A000322, 312 - partitions into distinct parts, 348 - A000383, 312 - partitions, of an integer, 345 - A000593, 352 - Pell equation not solvable, 813 - A000695, 59, 750 - period-doubling seq., 10, 735 - A000700, 349 - primes with primitive root 2, 852, 878 - A001037, 380, 843 - primitive roots of Mersenne primes, 373 - A001045, 315, 318 - primitive trinomials, 848 - A001122, 878 - quadratic residues all non-prime, 784 - A001220, 780 - rabbit seq., 513, 753 - A001227, 708 - radix -2 representations, 60 - A001262, 788 - restricted growth strings, 337 - A001318, 346 - ruler function, 733 - A001333, 314, 758 - sparse signed binary words, 315 - A001470, 280 - subfactorial numbers, 280 - A001511, 9, 733 - subset-lex words, 71 - A001591, 309 - sum of binary digits, 739 - A001592, 309 - sum of digits of binary Gray code, 744 - A001764, 337 - swaps with revbin permutation, 119 - A002293, 337 - Thue-Morse seq., 44, 461, 726, 817 - A002294, 337 - trinomial, irreducible, 848 - A002450, 59 - type-1 optimal normal bases, 912 - A002475, 850 - type-2 optimal normal bases, 912 - A002812, 797 - values of the M"obius function, 706 - A002997, 786 - Wieferich primes, 780 - A003010, 797 integer sequence, by OEIS number - A003106, 347 - A000003, 610 - A003114, 347, 350 - A000005, 708 - A003188, 742 958 Index - A003319, 281 - A029883, 739 - A003462, 649 - A031399, 813 - A003622, 754 - A034448, 353 - A003688, 314 - A034947, 745 - A003714, 62, 755, 756 - A035263, 10, 735 - A003849, 754 - A035457, 349 - A004211, 368 - A036991, 78 - A004212, 368 - A045687, 119 - A004213, 368 - A046116, 390 - A005011, 368 - A046699, 74 - A005351, 60 - A048146, 353 - A005352, 60 - A048250, 353 - A005418, 151, 733 - A051158, 740 - A005578, 315 - A054639, 912, 914 - A005614, 753 - A055578, 780 - A005727, 703 - A055881, 248 - A005797, 610 - A057460, 850 - A005811, 90, 744 - A057461, 850 - A006130, 318 - A057463, 850 - A006131, 318 - A057474, 850 - A006206, 710 - A057496, 851 - A006498, 321 - A061344, 389 - A006519, 9 - A064990, 730 - A006945, 789 - A065428, 784 - A007895, 754 - A067659, 350 - A008275, 277 - A067661, 350 - A008277, 358 - A069925, 848 - A008683, 706 - A071642, 853, 912, 914 - A010060, 44, 727 - A072226, 802 - A011260, 843 - A072276, 788 - A014565, 753 - A073571, 849 - A014577, 88, 744 - A073576, 351 - A014578, 731 - A073639, 850 - A015440, 318 - A073726, 849, 885 - A015441, 318 - A074071, 731 - A015442, 318 - A074710, 850 - A015443, 318 - A079471, 73 - A015448, 314 - A079559, 74 - A015449, 315 - A079972, 322 - A016031, 874 - A080337, 366 - A019320, 802 - A080764, 758 - A020229, 788 - A080846, 95 - A020985, 44, 732 - A086347, 320 - A022155, 45 - A087188, 351 - A022342, 754 - A091072, 88 - A025157, 350 - A095076, 754 - A025158, 350 - A096393, 373 - A025159, 350 - A100661, 72 - A025160, 350 - A101284, 914 - A025161, 350 - A102467, 840 - A025162, 350 - A103314, 383 - A027187, 347 - A104521, 759 - A027193, 347 - A106400, 726, 729 - A027362, 904 - A106665, 90 - A028859, 320 - A107220, 853 Index 959 - A107222, 904 inversion table, of a permutation 232 - A107877, 369 invertible modulo m 767 - A108918, 71 involution (self-inverse permutation) 106, 279 - A110981, 383 involution, random 114 - A114374, 351 irreducible polynomial 837 - A118666, 53 isolated ones or zeros in a word 11 - A118685, 817 iteration - A123400, 257 - and multiple roots, 593 - A125145, 320 - divisionless, for polynomial roots, 586 - A134337, 351 - for exp, 627 - A134345, 351 - for inverse, 567 - A135488, 909 - for inverse cube root, 569 - A135498, 909 - for inverse root, 573 - A136250, 914 - for inverse square root, 568 - A136415, 914 - for logarithm, 623 - A136416, 850 - for roots modulo pn , 569 - A137310, 914 - for the zero of a function, 587 - A137311, 914 - Goldschmidt, 581 - A137313, 914 - Householder's, 592 - A137314, 914 - Schr"oder's, 588 - A138933, 802 - synthetic, 726 - A143347, 744 - to compute ss, 615 - A159880, 257 Ives' algorithm for permutation generation 270 - A162296, 353 - A164896, 383 J ................................................. - A167654, 820 Jacobi matrix 548 - A175337, 95 Jacobi's identity 605 - A175338, 129 K ................................................ - A175339, 129 K, elliptic integral 601 - A175390, 855 k-ary - A176405, 99 - Dyck words, 333 - A176416, 100 - trees, 333 interleaving process k-compositions of n 194 - for set partitions, 354 k-permutations 291 - for Trotter's permutations, 254 k-subset 210 interpolation binary search 142 k-subsets (combinations) of a multiset 296 interpolation, linear 142 Karatsuba multiplication inverse - for integers, 550 - additive, modulo m, 767 - for polynomials, 827 - by exponentiation, 888 keys, sorting by keys 144 - cube root, iteration for, 569 Knuth shuffle 111 - in GF(Q), 888 Komornik-Loreti constant 729 - iteration for, 567 K"onig iteration functions 592 - modulo 2n (2-adic), 56 kperm_gray (C++ class) 293 - modulo m, by exponentiation, 781 Kronecker product - multiplicative, modulo m, 767 - (definition), 463 - of a circulant matrix, 906 - of Hadamard matrices, 388 - permutation, 106 Kronecker symbol 782 - permutation, in-place computation, 106 ksubset_gray (C++ class) 213 - power series over GF(2), 826 ksubset_rec (C++ class) 210 - root, iteration for, 573 ksubset_twoclose (C++ class) 215 - square root, iteration for, 568 Kummer's transformation 693 - XYZ transform, see XYZ transform inversion formula, Lagrange 590 L ................................................. inversion principle, M"obius 706 Lagrange inversion formula 590 960 Index Lambert series 707, 738 Lucas-Lehmer test, for Mersenne numbers 796 LCM, least common multiple 768 lucky path, in a graph 402 least common multiple (LCM) 768 Lunnon's Gray code for multiset permutations 301 left inversion, of a permutation 233 Lyndon words left-right array 166 - (definition), 370 left-right array, with Lehmer code 235 - and irreducible binary polynomials, 856 left-to-right powering 564 - and Mersenne primes, 373 left_right_array (C++ class) 166 - binary, number of, 380 Legendre symbol 782 - number of, 380 Legendre's relation 604, 701 - with even/odd weight, 382 Lehmer code, of a permutation 232 - with fixed content, 382 lex (lexicographic) order 172 - with fixed density, 382 lexicographic order Lyndon words, as binary word 30 - (definition), 172 lyndon_gray (C++ class) 406 - for bit combinations, 64 - for combinations, 177 M ................................................ - for multiset permutations, 296 m-sequence 384, 873 - for subsets, 202 MAC (modular adjacent changes), Gray code 399 - for subsets of a binary word, 70 mass storage convolution 453 - generalized, for mixed radix numbers, 224 matrix Fourier algorithm (MFA) 438 lfsr (C++ class) 865 matrix square root, applications 576 LFSR (linear feedback shift register) 864 matrix transposition, and zip permutation 127 LFSR, and Hadamard matrices 384 matrix transposition, in-place 122 LHCA (linear hybrid cellular automaton) 878 MAX-convolution 491 LIFO (last-in, first-out), stack 153 maximal order modulo m 774 LIMB (super-digit) 560 mean, arithmetic-geometric 599 linear convolution 443 median of three elements 135 linear correlation 444 Mephisto Waltz sequence 730 linear feedback shift register (LFSR) 864 merge sort 138 linear hybrid cellular automaton (LHCA) 878 Mersenne numbers, Lucas-Lehmer test 796 linear interpolation 142 Mersenne primes linear, function in a finite field 887 - 2j-th roots, 807 Lipski's Gray codes for permutations 250 - and Lyndon words, 373 list recursions 304 - generalized, 768 little endian machine 2 - Lucas-Lehmer test, 796 localized Hartley transform algorithm 529 Mersenne-Walsh transform 513 localized Walsh transform algorithm 468 MFA (matrix Fourier algorithm) 438 logarithm MFA convolution algorithm 452 - as hypergeometric function, 696 minimal polynomial, in GF(2n ) 892 - bit-wise computation, 641, 644 minimal-change order see Gray code - computation by rectangular scheme, 659 minimum, among bit-wise rotations 29 - computation via AGM, 622 missing, CPU instructions 82 - computation via ss= log(q), 622 mixed radix numbers 217 - curious series for, 626 mixedradix_endo (C++ class) 226 - iteration using exp, 623 mixedradix_endo_gray (C++ class) 228 - of power series, 630 mixedradix_gray (C++ class) 220 logarithmic generating function (LGF) 352 mixedradix_gslex (C++ class) 224 logical shift, of a binary word 3 mixedradix_gslex_alt (C++ class) 226 long division 567 mixedradix_lex (C++ class) 217 long multiplication 567 mixedradix_modular_gray (C++ class) 224 loop in a graph 391 mixedradix_modular_gray2 (C++ class) 223 loopless algorithm 173 mixedradix_sod_lex (C++ class) 229 low bits, operations on 8 M"obius function 705 LR-array (left-right array) 166 M"obius inversion principle 706 Lucas test, for primality 799 mod (C++ class) 537, 809 Index 961 mod m FFTs 535 - binary, number of, 379 modular adjacent changes (MAC), Gray code 399 - definition, 370 modular arithmetic 764 - with even/odd weight, 382 modular multiplication 765 - with fixed content, 382 modular reduction, with structured primes 768 - with fixed density, 382 modular square root 784 necklaces, as binary words 30 modulo, as equivalence classes 149 negacyclic convolution 451, 528 modulus neighbors of a node in a graph 391 - composite, 776 Newton's formula 895 - prime, 776 Newton's iteration, for vector-valued functions 548 - prime, with NTTs, 535 node (vertex) of a graph 391 moment conditions, for wavelet filters 546 non-generous primes 780 Moser - De Bruijn sequence 59, 750 non-residue (quadratic, modulo p) 781 moves, of the Hilbert curve 83 nonadjacent form (NAF) 61 mpartition (C++ class) 343 nonadjacent form (NAF), Gray code 315 mset_perm_gray (C++ class) 301 normal bases, for GF(2n ) 900 mset_perm_lex (C++ class) 298 normal basis, optimal 912 mset_perm_lex_rec (C++ class) 297 normal element (free element) 901 multi-dimensional Walsh transform 461 normal polynomial 900 multi-point iteration 597 NTT multigraph 391 - (number theoretic transforms), 535 multinomial coefficient 296, 383 - radix-2 DIF, 538 multiple roots, iterations for 593 - radix-2 DIT, 537 multiplication - radix-4, 540 - by FFT, 558 number of - carry, 558 - alternating permutations, 281 - integer vs. float, 6 - aperiodic necklaces, 380 - is convolution, 558 - binary necklaces, 379 - Karatsuba, 550 - binary partitions of even numbers, 728 - modulo m, 765 - binary reversible strings, 151 - of complex numbers via 3 real mult., 806 - binary words with at most r consecutive - of hypercomplex numbers, 815 ones, 308 - of octonions, 818 - bracelets, 150 - of polynomials, is linear convolution, 444 - carries, 220 - of quaternions, 818 - combinations, 176 - sum-of-digits test, 562 - connected permutations, 281 multiplication matrix, for normal bases 901 - cycles in De Bruijn graph, 397 multiplication table, of an algebra 815 - De Bruijn sequences, 874 multiplicative function 705, 777 - derangements, 280 multiplicative group 777 - divisors, 708 multiplicative group, with a ring 775 - equivalence relations, 151 multiplicative inverse, modulo m 767 - F-increment RGS, 368 multisection of power series 688 - fixed density Lyndon words, 382 multiset 295 - fixed density necklaces, 382 - generators modulo n, 780 N ................................................ - increment-i RGS, 337 N-polynomial (normal polynomial) 900 - indecomposable permutations, 281 n-set, a set with n elements 176 - integer partitions, 345 NAF (nonadjacent form) 61 - integers coprime to n, 776 NAF, Gray code 315 - inversions of a permutation, 236 necklace (C++ class) 372 - invertible circulant matrices, 905 necklace2bitpol (C++ class) 856 - involutions, 279 necklaces - irreducible polynomials, 843 - as equivalence classes, 149 - irreducible SRPs, 847 - binary, 30 - K-increment RGS, 369 962 Index - Lyndon words, 380, 843 paper-folding sequence 88, 744 - m-sequences, 873 parallel assignment (with pseudocode) 414 - max-increment RGS, 364 parameters, of a hypergeometric series 685 - necklaces, 150, 379 paren (C++ class) 323 - necklaces with even/odd weight, 382 paren_gray (C++ class) 329 - normal polynomials, 904, 907 parentheses, and binary words 78 - ones in binary Gray code, 744 parity - parentheses pairs, 331 - number, 726, 739 - partitions into distinct parts, 348 - of a binary word, 42 - partitions of a set, 358 - of a permutation, 105 - partitions of an integer, 345 - random permutation with given parity, 112 - permutations of a multiset, 296 parity (parity of a word), GCC built-in 21 - permutations whose order divides 3, 280 Parseval's equation 411 - permutations with m cycles, 277 partial unrolling of a loop 148 - primitive normal polynomials, 904 partition - primitive polynomials, 843 - of a set, 354 - primitive SRPs, 848 - of an integer, 339 - self-dual normal bases, 909 partition (C++ class) 341 - set partitions, 151, 358 partition_gen (C++ class) 339 - shift register sequences, 873 partitioning, for quicksort 135 - sparse signed binary words, 315 Pascal's triangle 177 - strings with fixed content, 383 path in a graph 391 - swaps with revbin permutation, 118 pattern, length-n with p letters 361 - units in GF(Q), 888 pcrc64 (C++ class) 871 - units modulo m, 777 Pell - unlabeled bracelets, 150 - constant, 758 - unlabeled necklaces, 150 - equation, 812 - zero-divisors of Cayley-Dickson algebras, - Gray code constant, 762 820 - palindromic constant, 759 number theoretic transforms (NTT) 535 Pell ruler function 760 Pell words, Gray code 313, 760 O ................................................ pentagonal number theorem 346 O(1) algorithm 173 pentanomial 851 octonions 816 Pepin's test, for Fermat numbers 795 OGF (ordinary generating function) 173 period of a polynomial 841 ONB (optimal normal basis) 912 period-doubling constant 735 one-point iteration 587 period-doubling sequence 10, 735 optimal normal basis (ONB) 912 perm_colex (C++ class) 243 optimization, with combinatorial generation 174 perm_derange (C++ class) 264 OR-convolution 489 perm_gray_ffact (C++ class) 259, 293 OR-convolution, weighted 493 perm_gray_ffact2 (C++ class) 258 order perm_gray_lipski (C++ class) 250 - of a polynomial, 841 perm_gray_rfact (C++ class) 260 - of an element modulo m, 774 perm_gray_rot1 (C++ class) 263 - of an iteration, 587 perm_gray_wells (C++ class) 252 ordinary generating function (OGF) 173 perm_heap (C++ class) 249 out of core algorithms 453 perm_heap2 (C++ class) 249 perm_heap2_swaps (C++ class) 250 P ................................................. perm_involution (C++ class) 284 Pad'e approximants 595 perm_ives (C++ class) 270 - for arctan, 624 perm_lex (C++ class) 242 - for exp, 628 perm_mv0 (C++ class) 267 - for the r-th root, 572 perm_rec (C++ class) 285 - for the logarithm, 623 perm_restrpref (C++ class) 278 - for the square root, 683 perm_rev (C++ class) 245 Index 963 perm_rev2 (C++ class) 247 prefix shifts, order for perm_rot (C++ class) 266 - combinations, 180 perm_st (C++ class) 271 - multiset permutations, 299 perm_st_gray (C++ class) 274 - paren strings, 330 perm_star (C++ class) 257 prefix transform 511 perm_star_swaps (C++ class) 257 prime length FFT, Rader's algorithm 457 perm_trotter (C++ class) 254 primes perm_trotter_lg (C++ class) 256 - and cyclotomic polynomials, 802 permutation - as modulus, 776 - alternating, 281 - as modulus, with NTTs, 535 - as path in the complete graph, 395 - non-generous, 780 - composition, 105 - sieve of Eratosthenes, 770 - connected, 281 - structured, 768 - cycle type, 278 - Wieferich, 780 - cycles, 104 - with primitive root 2, 878 - cyclic, random, 112 primitive n-th root, modulo m 535 - derangement, 280 primitive r-th root of unity 774 - indecomposable, 281 primitive elements, of a group 776 - inverse of, 106 primitive polynomial 841 - involution, 106, 279 primitive root - of a multiset, 296 - (definition), 776 - random, 111 - Creutzburg-Tasche, 808 - with m cycles, number of, 277 - in GF(2n ), 889 - with prescribed parity, random, 112 - of Mersenne primes, 373 Pfaff's reflection law 689 - with prime length FFT, 457 phi function, number theoretic 776 primitive trinomial 848, 885 ss, computation 615 priority queue 162 pitfall, shifts in C 4 priority_queue (C++ class) 162 pitfall, two's complement 4 product form Pocklington-Lehmer test, for primality 794 - for a-th root, 583 pointer sort 144 - for continued fractions, 720 pointer, size of 2 - for elliptic K, 602 polar decomposition, of a matrix 578 - for power series of exp, 631 polynomial - for square root, 684 - binary, 822 - from series, 709 - irreducible, 837 products of k out of n factors 179 - multiplication, is linear convolution, 444 products, infinite, from series 709 - multiplication, splitting schemes, 827 Proth's theorem 795 - primitive, 841 Prouhet-Thue-Morse constant 726 - roots, divisionless iterations for, 586 pseudo graph 391 - weight of a binary polynomial, 848 pseudo-inverse, of a matrix 579 popcount (bit-count), GCC built-in 21 pseudoprime 786 power series pseudoprime, strong (SPP) 786 - computation of exponential function, 631 - computation of logarithm, 630 Q ................................................ - reversion, 589 Q-matrix 858 powering quadratic convergence 587 - left-to-right method, 564 quadratic equation, with binary finite fields 896 - modulo m, 766 quadratic reciprocity 782 - of permutations, 108 quadratic residue (square) modulo p 781 - of the binary Gray code, 48 quadratic residues, and Hadamard matrices 386 - right-to-left method, 563 quadruple reversal technique 124 Pratt's certificate of primality 792 quartic convergence 587 prefetching a memory location, GCC built-in 21 quaternions 816 prefix convolution 511 queue (C++ class) 157 964 Index queue (FIFO) 156 revbin constant 741 quicksort 135 revbin pairs, via shift registers 873 revbin permutation 118 R ................................................ revbin permutation, and convolution by FFT 442 R2CFT see real FFT reversal bit-wise 33 R2CFT (real to complex FFT) 431 reversal, of a permutation 103 R5-dragon 95 reversed arithmetic transform 485 R7-dragon 95 reversed Gray code 45 rabbit constant 753 reversed Gray permutation 131 rabbit sequence 513, 753 reversed Haar transform 505 Rabin's test for irreducibility 838 reversed Reed-Muller transform 487 Rabin-Miller test, for compositeness 787 reversing the bits of a word 34 Rader's algorithm, for prime length FFT 457 reversion of power series radix -2 (minus two) representations 58 - (definition), 589 radix (base) conversion 656 - for Schr"oder's formula, 591 radix permutation 121 - with k-ary Dyck words, 337 radix sort 138 RGS (restricted growth string) 325 radix-r DIF FFT step 419 rgs_fincr (C++ class) 366 radix-r DIT FFT step 419 rgs_maxincr (C++ class) 364 random permutation 111 right inversion, of a permutation 232 random selection 111 right-angle convolution 450 ranking, with combinatorial objects 172 right-to-left powering 563 rational, square root iterations 570 ring buffer 155 re-orthogonalization, of a matrix 576 ringbuffer (C++ class) 155 real FFT rising factorial base 232 - by FHT, 523 RLL (run-length limited) words 310 - split-radix algorithm, 434 Rogers-Ramanujan identities 347 - with wrap routines, 432 root reciprocal polynomial 845 - extraction, 572 reciprocity, quadratic 782 - inverse, iteration for, 573 rectangular scheme - modulo pn (p-adic), 569 - for arctan and log, 658 - of a polynomial, divisionless iterations, 586 - for exp, sin, and cos, 660 - primitive, 776 recurrence - primitive, in GF(2n ), 889 - (definition), 666 - primitive, modulo m, 535 - inhomogeneous, 670 - primitive, of Mersenne primes, 373 - relation, 666 roots of unity, having sum zero 383 - relation, for subsequences, 672 rotation, bit-wise 27 red code 50 rotation, by triple reversal 123 reduction row-column algorithm 437 - modular, with structured primes, 768 ruler constant 734 - modulo x2 + x + 1 etc., 806 ruler function 207, 733 Reed-Muller transform ruler_func (C++ class) 207, 283 - (definition), 486 run-length limited (RLL) words 310 - and necklaces, 376 rejection method 117 S ................................................. relation, binary 148 Sande-Tukey FFT algorithm 414 representations, radix -2 (minus two) 58 Sattolo's algorithm 112 representatives, with equivalence classes 149 scalar multiplication 886 residue (quadratic, modulo p) 781 Schr"oder's formula 588 restricted growth strings (RGS) search, binary 141 - (definition), 325 searching, with unsorted arrays 147 - for parentheses strings, 325 secant method 587 - for set partitions, 357 sedenions 816 revbin (bit-wise reversal) 33 selection sort 134 Index 965 selection, of a random element 111 sparse words, bit counting 20 self-correlation 445 spectrum of a real number 756 self-dual (basis over GF(2n )) 908 SPI (strong pseudo-irreducible) 839 self-inverse permutation, random 114 split-radix FFT algorithm 425 self-reciprocal polynomial 846 splitting schemes for multiplication sentinel element 174 - for integers, 550 sequence see integer sequence - for polynomials over GF(2), 827 sequency 474 splitting, binary, for rational series 651 sequency of a binary word, complementing 48 SPP (strong pseudoprime) 786 sequency, of a binary word 46 square modulo p 781 set partition 354 square of a permutation 107 setpart (C++ class) 356 square root setpart_p_rgs_lex (C++ class) 361 - in GF(2n ), 888 setpart_rgs_gray (C++ class) 363 - iteration for, 568 setpart_rgs_lex (C++ class) 360 - modulo 2n , 57 shift operator, for Fourier transform 413 - modulo p, 784 shift operator, for Hartley transform 516 - of a matrix, applications, 576 shift register sequence (SRS) 864 square-free factorization, with polynomials 863 shift-and-add algorithms 641 square-free polynomials 858 shifts in C, pitfall 4 square-free, partitions into such parts 351 shifts, and division 3 SRS (shift register sequence) 864 shifts-order stable sort 137 - for bit combinations, 64 stack (C++ class) 153 - for Fibonacci words, 210 stack (LIFO) 153 - for subsets, 208 star-transposition order, for permutations 257 - Gray code, for subsets, 209 Stirling numbers short division 567 - of the first kind (cycle numbers), 277 short multiplication 567 - of the second kind (set numbers), 358 sieve of Eratosthenes 770 strings with fixed content 383 sign decomposition, of a matrix 579 strong minimal-change order 172, 254, 329 sign of a permutation 105 strong minimal-change order for combinations 183 sign of the Fourier transform 410 strong pseudo-irreducible (SPI) 839 signed binary representation 61 strong pseudoprime (SPP) 786 signed binary words, sparse, Gray code 315 structured primes 768 simple continued fraction 717 subdegree of a polynomial 852 simple path in a graph 391 subfactorial numbers 280 simple zero-divisors 820 subsequences, recurrence relations for 672 sine and sinh, as hypergeometric function 697 subset convolution 493 sine, CORDIC algorithm 646 subset of bitset, testing 23 sine, in a finite field 808 subset_debruijn (C++ class) 208 single track subset_deltalex (C++ class) 202 - Gray code, 403 subset_gray (C++ class) 206 - order for permutations, 271 subset_gray_delta (C++ class) 175, 204 - order for subsets, 208 subset_lex (C++ class) 203 singular value decomposition (SVD) 577 subsets singular values, with elliptic K 609 - of k bits (combinations), 62 skew circular convolution 451 - of a binary word, 68, 70 slant transform 482 - of a multiset, 295 slant transform, sequency-ordered 483 subtraction, modulo m 764 smart, your compiler 26 sum of digits, with mixed radix numbers 229 sorting by keys 144 sum of Gray code digits constant 744 sorting, edges in a graph 402 sum of two squares 810 sparse counting, and bit subsets 68 sum-of-digits constant 740 sparse signed binary representation 61 sum-of-digits test, with multiplication 562 sparse signed binary words, Gray code 315 sumalt algorithm 662 966 Index sums of divisors, and partitions 352 units (invertible elements) 767 super-linear iteration 587 universal cycle (for combinatorial objects) 874 SVD (singular value decomposition) 577 unlabeled bracelets 150 Swan's theorem 850 unranking, with combinatorial objects 172 swapping blocks via quadruple reversal 124 unrolling, of a loop 148 swapping two bits 8 unsorted arrays, searching 147 swapping variables without temporary 6 unzip permutation 126 symmetries - of the Fourier transform, 428 V ................................................ - of the revbin permutation, 119 vertex, of a graph 391 synthetic iterations 726 vertical addition 21 T ................................................. taps, with wavelet filter 543 W ............................................... tcrc64 (C++ class) 871 Walsh transform 459 tensor product 463 Walsh transform, multi-dimensional 461 terdragon curve 92 wavelet conditions 544 theta functions: 2, 3, and 4 604 wavelet filter 544 Thue constant 731 wavelet transform 543 Thue-Morse sequence 44, 461, 726, 817 wavelet_filter (C++ class) 544, 546 thue_morse (C++ class) 44 weight, of binary polynomial 848 timing, with demo-programs 175 weighted arithmetic transform 492 TMFA (transposed matrix Fourier algorithm) 438 weighted convolution 449 toggle between two values 5 weighted MFA convolution algorithm 452 Toom-Cook algorithm 551 weighted MFA convolution, mass storage 453 Toom-Cook algorithm for binary polynomials 831 weighted OR-convolution 493 totient function 776 weighted sum of Gray code digits constant 747 towers of Hanoi 735 weighted sum-of-digits constant 741 trace weighted transform 448 - of a polynomial, 900 Wells' Gray code for permutations 252 - of an element in GF(2n ), 887 Whipple's identity 690 - vector, fast computation, 895 Wieferich primes 780 - vector, in finite field, 888 trace-orthonormal basis 908 X ................................................ transformations, for elliptic K and E 700 XOR permutation 127 transformations, of hypergeometric series 688 XOR, cyclic 32 transforms, on binary words 49 XOR-convolution 481 transition count, for a Gray code 403 xx , series for 702 transposed matrix Fourier algorithm (TMFA) 438 transposition of a matrix, and zip permutation 127 Y ................................................ transposition of a matrix, in-place 122 yellow code 49, 376 transpositions of a permutation 105 Young diagram (with integer partitions) 345 trigonometric recursion 417 trinomial, primitive 848, 885 Z ................................................. triple reversal technique 123 Z-order 87 Trotter's algorithm for permutations 254 z-transform 454 two's complement, pitfall 4 Zeckendorf representation 754 two-close order for k-subsets 215 zero bytes, finding 55 two-close order for combinations 188 zero divisors, of an algebra 815 type, of a set partition 359 zero padding, for linear convolution 444 type-1 optimal normal basis 912 zero-divisors of the sedenions 820 type-2 optimal normal basis 912 zero-one transitions in a word 12 type-t Gaussian normal basis 914 zip permutation 125 U ................................................ zip,zbit-wise 38 unitary divisor 353 z , series for 702