ALGORITHMS FOR PROGRAMMERS
CONTENTS I LOW LEVEL ALGORITHMS BIT WIZARDRY TRIVIA OPERATIONS ON INDIVIDUAL BITS OPERATIONS ON LOW BITS OR BLOCKS OF A WORD ISOLATING BLOCKS OF BITS AND SINGLE BITS COMPUTING THE INDEX OF A SINGLE SET BIT OPERATIONS ON HIGH BITS OR BLOCKS OF A WORD FUNCTIONS RELATED TO THE BASE-2 LOGARITHM COUNTING BITS AND BLOCKS OF A WORD BIT SET LOOKUP AVOIDING BRANCHES BIT-WISE ROTATION OF A WORD FUNCTIONS RELATED TO BIT-WISE ROTATION * REVERSING THE BITS OF A WORD BIT-WISE ZIP GRAY CODE AND PARITY BIT SEQUENCY POWERS OF THE GRAY CODE INVERTIBLE TRANSFORMS ON WORDS MOVES OF THE HILBERT CURVE THE Z-ORDER SCANNING FOR ZERO BYTES 2-ADIC INVERSE AND SQUARE ROOT RADIX ?2 REPRESENTATION A SPARSE SIGNED BINARY REPRESENTATION GENERATING BIT COMBINATIONS GENERATING BIT SUBSETS OF A GIVEN WORD BINARY WORDS AS SUBSETS IN LEXICOGRAPHIC ORDER MINIMAL-CHANGE BIT COMBINATIONS FIBONACCI WORDS BINARY WORDS AND PARENTHESES STRINGS * ERROR DETECTION BY HASHING: THE CRC PERMUTATIONS VIA PRIMITIVES CPU INSTRUCTIONS OFTEN MISSED PERMUTATIONS THE REVBIN PERMUTATION THE RADIX PERMUTATION IN-PLACE MATRIX TRANSPOSITION REVBIN PERMUTATION AND MATRIX TRANSPOSITION * THE ZIP PERMUTATION THE REVERSED ZIP PERMUTATION THE XOR PERMUTATION THE GRAY CODE PERMUTATION THE REVERSED GRAY CODE PERMUTATION DECOMPOSING PERMUTATIONS * GENERAL PERMUTATIONS AND THEIR OPERATIONS SORTING AND SEARCHING SORTING BINARY SEARCH POINTER SORTING SORTING BY A SUPPLIED COMPARISON FUNCTION DETERMINATION OF UNIQUE ELEMENTS UNIQUE ELEMENTS WITH INEXACT TYPES DETERMINATION OF EQUIVALENCE CLASSES DETERMINATION OF MONOTONICITY AND CONVEXITY * HEAPSORT COUNTING SORT AND RADIX SORT SEARCHING IN UNSORTED ARRAYS DATA STRUCTURES STACK (LIFO) RING BU?ER QUEUE (FIFO) DEQUE (DOUBLE-ENDED QUEUE) HEAP AND PRIORITY QUEUE BIT-ARRAY FINITE-STATE MACHINES EMULATION OF COROUTINES II COMBINATORIAL GENERATION CONVENTIONS AND CONSIDERATIONS ABOUT REPRESENTATIONS AND ORDERS RANKING, UNRANKING, AND COUNTING CHARACTERISTICS OF THE ALGORITHMS OPTIMIZATION TECHNIQUES REMARKS ABOUT THE C++ IMPLEMENTATIONS COMBINATIONS LEXICOGRAPHIC AND CO-LEXICOGRAPHIC ORDER ORDER BY PRE?X SHIFTS (COOL-LEX) MINIMAL-CHANGE ORDER THE EADES-MCKAY STRONG MINIMAL-CHANGE ORDER TWO-CLOSE ORDERINGS VIA ENDO/ENUP MOVES RECURSIVE GENERATION OF CERTAIN ORDERINGS COMPOSITIONS CO-LEXICOGRAPHIC ORDER CO-LEXICOGRAPHIC ORDER FOR COMPOSITIONS INTO EXACTLY K PARTS COMPOSITIONS AND COMBINATIONS MINIMAL-CHANGE ORDERS SUBSETS LEXICOGRAPHIC ORDER ORDERING WITH DE BRUIJN SEQUENCES SHIFTS-ORDER FOR SUBSETS K-SUBSETS WHERE K LIES IN A GIVEN RANGE MIXED RADIX NUMBERS COUNTING ORDER GRAY CODE ORDER GSLEX ORDER ENDO ORDER GRAY CODE FOR ENDO ORDER 10 PERMUTATIONS FACTORIAL REPRESENTATIONS OF PERMUTATIONS AN ORDER FROM REVERSING PRE?XES MINIMAL-CHANGE ORDER (HEAP’S ALGORITHM) LIPSKI’S MINIMAL-CHANGE ORDERS STRONG MINIMAL-CHANGE ORDER (TROTTER’S ALGORITHM) MINIMAL-CHANGE ORDERS FROM FACTORIAL NUMBERS ORDERS WHERE THE SMALLEST ELEMENT ALWAYS MOVES RIGHT 10 10 SINGLE TRACK ORDERS 10 11 STAR-TRANSPOSITION ORDER 10 12 DERANGEMENT ORDER 10 13 RECURSIVE ALGORITHM FOR CYCLIC PERMUTATIONS 10 14 MINIMAL-CHANGE ORDER FOR CYCLIC PERMUTATIONS 10 15 PERMUTATIONS WITH SPECIAL PROPERTIES 11 SUBSETS AND PERMUTATIONS OF A MULTISET SUBSETS OF A MULTISET PERMUTATIONS OF A MULTISET 12 GRAY CODES FOR STRINGS WITH RESTRICTIONS GENERALIZED FIBONACCI WORDS DIGIT X FOLLOWED BY AT LEAST X ZEROS GENERALIZED PELL WORDS SPARSE SIGNED BINARY WORDS STRINGS WITH NO TWO SUCCESSIVE NONZERO DIGITS STRINGS WITH NO TWO SUCCESSIVE ZEROS BINARY STRINGS WITHOUT SUBSTRINGS 1X1 13 PARENTHESIS STRINGS GRAY CODE VIA RESTRICTED GROWTH STRINGS THE NUMBER OF PARENTHESIS STRINGS: CATALAN NUMBERS INCREMENT-I RGS AND K-ARY TREES 14 INTEGER PARTITIONS RECURSIVE SOLUTION OF A GENERALIZED PROBLEM ITERATIVE ALGORITHM PARTITIONS INTO M PARTS THE NUMBER OF INTEGER PARTITIONS 15 SET PARTITIONS THE NUMBER OF SET PARTITIONS: STIRLING SET NUMBERS AND BELL NUMBERS GENERATION IN MINIMAL-CHANGE ORDER 16 A STRING SUBSTITUTION ENGINE 17 NECKLACES AND LYNDON WORDS GENERATING ALL NECKLACES THE NUMBER OF BINARY NECKLACES THE NUMBER OF BINARY NECKLACES WITH ?XED CONTENT 18 HADAMARD AND CONFERENCE MATRICES HADAMARD MATRICES VIA LFSR HADAMARD MATRICES VIA CONFERENCE MATRICES CONFERENCE MATRICES VIA ?NITE ?ELDS 19 SEARCHING PATHS IN DIRECTED GRAPHS REPRESENTATION OF DIGRAPHS SEARCHING FULL PATHS CONDITIONAL SEARCH EDGE SORTING AND LUCKY PATHS GRAY CODES FOR LYNDON WORDS III FAST ORTHOGONAL TRANSFORMS 20 THE FOURIER TRANSFORM THE DISCRETE FOURIER TRANSFORM SUMMARY OF DE?NITIONS OF FOURIER TRANSFORMS * RADIX-2 FFT ALGORITHMS SAVING TRIGONOMETRIC COMPUTATIONS HIGHER RADIX FFT ALGORITHMS SPLIT-RADIX FOURIER TRANSFORMS SYMMETRIES OF THE FOURIER TRANSFORM INVERSE FFT FOR FREE REAL VALUED FOURIER TRANSFORMS 20 10 MULTIDIMENSIONAL FOURIER TRANSFORMS 20 11 THE MATRIX FOURIER ALGORITHM (MFA) 21 ALGORITHMS FOR FAST CONVOLUTION CONVOLUTION CORRELATION WEIGHTED FOURIER TRANSFORMS AND CONVOLUTIONS CONVOLUTION USING THE MFA THE Z-TRANSFORM (ZT) PRIME LENGTH FFTS 22 THE WALSH TRANSFORM AND ITS RELATIVES THE WALSH TRANSFORM: WALSH-KRONECKER BASIS EIGENVECTORS OF THE WALSH TRANSFORM * THE KRONECKER PRODUCT A VARIANT OF THE WALSH TRANSFORM * HIGHER RADIX WALSH TRANSFORMS LOCALIZED WALSH TRANSFORMS DYADIC (XOR) CONVOLUTION THE WALSH TRANSFORM: WALSH-PALEY BASIS SEQUENCY ORDERED WALSH TRANSFORMS 22 10 SLANT TRANSFORM 22 11 ARITHMETIC TRANSFORM 22 12 REED-MULLER TRANSFORM 22 13 THE OR-CONVOLUTION, AND THE AND-CONVOLUTION 23 THE HAAR TRANSFORM THE ‘STANDARD’ HAAR TRANSFORM IN-PLACE HAAR TRANSFORM NON-NORMALIZED HAAR TRANSFORMS TRANSPOSED HAAR TRANSFORMS THE REVERSED HAAR TRANSFORM RELATIONS BETWEEN WALSH AND HAAR TRANSFORMS NONSTANDARD SPLITTING SCHEMES * 24 THE HARTLEY TRANSFORM DE?NITION AND SYMMETRIES RADIX-2 FHT ALGORITHMS COMPLEX FT BY HT COMPLEX FT BY COMPLEX HT AND VICE VERSA REAL FT BY HT AND VICE VERSA HIGHER RADIX FHT ALGORITHMS CONVOLUTION VIA FHT NEGACYCLIC CONVOLUTION VIA FHT LOCALIZED FHT ALGORITHMS 24 10 TWO-DIMENSIONAL FHTS 24 11 DISCRETE COSINE TRANSFORM (DCT) BY HT 24 12 DISCRETE SINE TRANSFORM (DST) BY DCT 24 13 AUTOMATIC GENERATION OF TRANSFORM CODE 24 14 EIGENVECTORS OF THE FOURIER AND HARTLEY TRANSFORM * 25 NUMBER THEORETIC TRANSFORMS (NTTS) PRIME MODULI FOR NTTS IMPLEMENTATION OF NTTS CONVOLUTION WITH NTTS 26 FAST WAVELET TRANSFORMS WAVELET ?LTERS IMPLEMENTATION MOMENT CONDITIONS IV FAST ARITHMETIC 27 FAST MULTIPLICATION AND EXPONENTIATION ASYMPTOTICS OF ALGORITHMS SPLITTING SCHEMES FOR MULTIPLICATION FAST MULTIPLICATION VIA FFT RADIX/PRECISION CONSIDERATIONS WITH FFT MULTIPLICATION THE SUM-OF-DIGITS TEST BINARY EXPONENTIATION 28 ROOT EXTRACTION DIVISION, SQUARE ROOT AND CUBE ROOT ROOT EXTRACTION FOR RATIONALS DIVISIONLESS ITERATIONS FOR THE INVERSE A-TH ROOT INITIAL APPROXIMATIONS FOR ITERATIONS SOME APPLICATIONS OF THE MATRIX SQUARE ROOT GOLDSCHMIDT’S ALGORITHM PRODUCTS FOR THE A-TH ROOT DIVISIONLESS ITERATIONS FOR POLYNOMIAL ROOTS 29 ITERATIONS FOR THE INVERSION OF A FUNCTION ITERATIONS AND THEIR RATE OF CONVERGENCE SCHR¨ODER’S FORMULA HOUSEHOLDER’S FORMULA DEALING WITH MULTIPLE ROOTS MORE ITERATIONS IMPROVEMENTS BY THE DELTA SQUARED PROCESS 30 THE ARITHMETIC-GEOMETRIC MEAN (AGM) THE AGM THE ELLIPTIC FUNCTIONS K AND E AGM-TYPE ALGORITHMS FOR HYPERGEOMETRIC FUNCTIONS COMPUTATION OF ? ARCTANGENT RELATIONS FOR ? * 31 LOGARITHM AND EXPONENTIAL FUNCTION LOGARITHM EXPONENTIAL FUNCTION LOGARITHM AND EXPONENTIAL FUNCTION OF POWER SERIES SIMULTANEOUS COMPUTATION OF LOGARITHMS OF SMALL PRIMES 32 NUMERICAL EVALUATION OF POWER SERIES THE BINARY SPLITTING ALGORITHM FOR RATIONAL SERIES RECTANGULAR SCHEMES FOR EVALUATION OF POWER SERIES THE MAGIC SUMALT ALGORITHM FOR ALTERNATING SERIES 33 COMPUTING THE ELEMENTARY FUNCTIONS WITH LIMITED RESOURCES SHIFT-AND-ADD ALGORITHMS FOR LOGB(X) AND BX CORDIC ALGORITHMS 34 RECURRENCES AND CHEBYSHEV POLYNOMIALS RECURRENCES CHEBYSHEV POLYNOMIALS 35 CYCLOTOMIC POLYNOMIALS, HYPERGEOMETRIC FUNCTIONS, AND CONTINUED FRACTIONS CYLOTOMIC POLYNOMIALS, M¨OBIUS INVERSION, LAMBERT SERIES HYPERGEOMETRIC FUNCTIONS CONTINUED FRACTIONS 36 SYNTHETIC ITERATIONS * A VARIATION OF THE ITERATION FOR THE INVERSE AN ITERATION RELATED TO THE THUE CONSTANT AN ITERATION RELATED TO THE GOLAY-RUDIN-SHAPIRO SEQUENCE ITERATIONS RELATED TO THE RULER FUNCTION AN ITERATION RELATED TO THE PERIOD-DOUBLING SEQUENCE AN ITERATION FROM SUBSTITUTION RULES WITH SIGN ITERATIONS RELATED TO THE SUM OF DIGITS ITERATIONS RELATED TO THE BINARY GRAY CODE A FUNCTION THAT ENCODES THE HILBERT CURVE 36 10 SPARSE VARIANTS OF THE INVERSE 36 11 AN ITERATION RELATED TO THE FIBONACCI NUMBERS 36 12 ITERATIONS RELATED TO THE PELL NUMBERS V ALGORITHMS FOR ?NITE ?ELDS 37 MODULAR ARITHMETIC AND SOME NUMBER THEORY IMPLEMENTATION OF THE ARITHMETIC OPERATIONS MODULAR REDUCTION WITH STRUCTURED PRIMES THE SIEVE OF ERATOSTHENES THE ORDER OF AN ELEMENT PRIME MODULUS: THE ?ELD Z/PZ = FP = GF(P) COMPOSITE MODULUS: THE RING Z/MZ THE CHINESE REMAINDER THEOREM (CRT) QUADRATIC RESIDUES COMPUTATION OF A SQUARE ROOT MODULO M 37 10 THE RABIN-MILLER TEST FOR COMPOSITENESS 37 11 PROVING PRIMALITY 37 12 COMPLEX MODULI: GF(P2) 37 13 SOLVING THE PELL EQUATION 37 14 MULTIGRADES * 37 15 PROPERTIES OF THE CONVERGENTS OF ? 2 * 37 16 MULTIPLICATION OF HYPERCOMPLEX NUMBERS * 38 BINARY POLYNOMIALS THE BASIC ARITHMETICAL OPERATIONS MULTIPLICATION FOR POLYNOMIALS OF HIGH DEGREE MODULAR ARITHMETIC WITH BINARY POLYNOMIALS IRREDUCIBLE AND PRIMITIVE POLYNOMIALS THE NUMBER OF IRREDUCIBLE AND PRIMITIVE POLYNOMIALS GENERATING IRREDUCIBLE POLYNOMIALS FROM NECKLACES IRREDUCIBLE AND CYCLOTOMIC POLYNOMIALS * FACTORIZATION OF BINARY POLYNOMIALS 39 SHIFT REGISTERS LINEAR FEEDBACK SHIFT REGISTERS (LFSR) GALOIS AND FIBONACCI SETUP GENERATING ALL REVBIN PAIRS THE NUMBER OF M-SEQUENCES AND DE BRUIJN SEQUENCES AUTO CORRELATION OF M-SEQUENCES FEEDBACK CARRY SHIFT REGISTER (FCSR) LINEAR HYBRID CELLULAR AUTOMATA (LHCA) ADDITIVE LINEAR HYBRID CELLULAR AUTOMATA 40 BINARY ?NITE ?ELDS: GF(2N) ARITHMETIC AND BASIC PROPERTIES MINIMAL POLYNOMIALS COMPUTATION OF THE TRACE VECTOR VIA NEWTON’S FORMULA SOLVING QUADRATIC EQUATIONS REPRESENTATION BY MATRICES * REPRESENTATION BY NORMAL BASES CONVERSION BETWEEN NORMAL AND POLYNOMIAL REPRESENTATION OPTIMAL NORMAL BASES (ONB) GAUSSIAN NORMAL BASES