Matters Computational: Ideas, Algorithms, Source Code

Matters Computational: Ideas, Algorithms, Source Code

By Jörg Arndt
Book Description

This book provides algorithms and ideas for computationalists. Subjects treated include low-level algorithms, bit wizardry, combinatorial generation, fast transforms like the Fourier transform, and fast arithmetic for both real numbers and finite fields. Various optimization techniques are described and the actual performance of many given implementations is examined. The focus is on material that does not usually appear in textbooks on algorithms. The implementations are done in C++ and the GP language, written for POSIX-compliant platforms such as the Linux and BSD operating systems.

Errata and other material available at the author's website. Available in Hardcover from Springer.

Table of Contents
  • Preface
  • I Low level algorithms
    • Bit wizardry
      • Trivia
      • Operations on individual bits
      • Operations on low bits or blocks of a word
      • Extraction of ones, zeros, or blocks near transitions
      • 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 the bits and blocks of a word
      • Words as bitsets
      • Index of the i-th set bit
      • Avoiding branches
      • Bit-wise rotation of a word
      • Binary necklaces
      • Reversing the bits of a word
      • Bit-wise zip
      • Gray code and parity
      • Bit sequency
      • Powers of the Gray code
      • Invertible transforms on words
      • Scanning for zero bytes
      • Inverse and square root modulo 2n
      • Radix -2 (minus two) representation
      • A sparse signed binary representation
      • Generating bit combinations
      • Generating bit subsets of a given word
      • Binary words in lexicographic order for subsets
      • Fibonacci words
      • Binary words and parentheses strings
      • Permutations via primitives
      • CPU instructions often missed
      • Some space filling curves
    • Permutations and their operations
      • Basic definitions and operations
      • Representation as disjoint cycles
      • Compositions of permutations
      • In-place methods to apply permutations to data
      • Random permutations
      • The revbin permutation
      • The radix permutation
      • In-place matrix transposition
      • Rotation by triple reversal
      • The zip permutation
      • The XOR permutation
      • The Gray permutation
      • The reversed Gray permutation
    • Sorting and searching
      • Sorting algorithms
      • Binary search
      • Variants of sorting methods
      • Searching in unsorted arrays
      • Determination of equivalence classes
    • Data structures
      • Stack (LIFO)
      • Ring buffer
      • Queue (FIFO)
      • Deque (double-ended queue)
      • Heap and priority queue
      • Bit-array
      • Left-right array
  • II Combinatorial generation
    • Conventions and considerations
      • Representations and orders
      • Ranking, unranking, and counting
      • Characteristics of the algorithms
      • Optimization techniques
      • Implementations, demo-programs, and timings
    • Combinations
      • Binomial coefficients
      • Lexicographic and co-lexicographic order
      • Order by prefix 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
      • Minimal-change order
      • Ordering with De Bruijn sequences
      • Shifts-order for subsets
      • k-subsets where k lies in a given range
    • Mixed radix numbers
      • Counting (lexicographic) order
      • Minimal-change (Gray code) order
      • gslex order
      • endo order
      • Gray code for endo order
      • Fixed sum of digits
    • Permutations
      • Factorial representations of permutations
      • Lexicographic order
      • Co-lexicographic order
      • An order from reversing prefixes
      • Minimal-change order (Heap's algorithm)
      • Lipski's Minimal-change orders
      • Strong minimal-change order (Trotter's algorithm)
      • Star-transposition order
      • Minimal-change orders from factorial numbers
      • Derangement order
      • Orders where the smallest element always moves right
      • Single track orders
    • Permutations with special properties
      • The number of certain permutations
      • Permutations with distance restrictions
      • Self-inverse permutations (involutions)
      • Cyclic permutations
    • k-permutations
      • Lexicographic order
      • Minimal-change order
    • Multisets
      • Subsets of a multiset
      • Permutations of a multiset
    • Gray codes for strings with restrictions
      • List recursions
      • Fibonacci words
      • Generalized Fibonacci words
      • Run-length limited (RLL) words
      • Digit x followed by at least x zeros
      • Generalized Pell words
      • Sparse signed binary words
      • Strings with no two consecutive nonzero digits
      • Strings with no two consecutive zeros
      • Binary strings without substrings 1x1 or 1xy1
    • Parentheses strings
      • Co-lexicographic order
      • Gray code via restricted growth strings
      • Order by prefix shifts (cool-lex)
      • Catalan numbers
      • Increment-i RGS, k-ary Dyck words, and k-ary trees
    • Integer partitions
      • Solution of a generalized problem
      • Iterative algorithm
      • Partitions into m parts
      • The number of integer partitions
    • Set partitions
      • Recursive generation
      • The number of set partitions: Stirling set numbers and Bell numbers
      • Restricted growth strings
    • Necklaces and Lyndon words
      • Generating all necklaces
      • Lex-min De Bruijn sequence from necklaces
      • The number of binary necklaces
      • Sums of roots of unity that are zero
    • Hadamard and conference matrices
      • Hadamard matrices via LFSR
      • Hadamard matrices via conference matrices
      • Conference matrices via finite fields
    • 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 transforms
    • The Fourier transform
      • The discrete Fourier transform
      • Radix-2 FFT algorithms
      • Saving trigonometric computations
      • Higher radix FFT algorithms
      • Split-radix algorithm
      • Symmetries of the Fourier transform
      • Inverse FFT for free
      • Real-valued Fourier transforms
      • Multi-dimensional Fourier transforms
      • The matrix Fourier algorithm (MFA)
    • Convolution, correlation, and more FFT algorithms
      • Convolution
      • Correlation
      • Correlation, convolution, and circulant matrices
      • Weighted Fourier transforms and convolutions
      • Convolution using the MFA
      • The z-transform (ZT)
      • Prime length FFTs
    • The Walsh transform and its relatives
      • Transform with Walsh-Kronecker basis
      • Eigenvectors of the Walsh transform
      • The Kronecker product
      • Higher radix Walsh transforms
      • Localized Walsh transforms
      • Transform with Walsh-Paley basis
      • Sequency-ordered Walsh transforms
      • XOR (dyadic) convolution
      • Slant transform
      • Arithmetic transform
      • Reed-Muller transform
      • The OR-convolution and the AND-convolution
      • The MAX-convolution
      • Weighted arithmetic transform and subset convolution
    • 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
      • Prefix transform and prefix convolution
      • Nonstandard splitting schemes
    • The Hartley transform
      • Definition and symmetries
      • Radix-2 FHT algorithms
      • Complex FFT by FHT
      • Complex FFT by complex FHT and vice versa
      • Real FFT by FHT and vice versa
      • Higher radix FHT algorithms
      • Convolution via FHT
      • Localized FHT algorithms
      • 2-dimensional FHTs
      • Automatic generation of transform code
      • Eigenvectors of the Fourier and Hartley transform
    • Number theoretic transforms (NTTs)
      • Prime moduli for NTTs
      • Implementation of NTTs
      • Convolution with NTTs
    • Fast wavelet transforms
      • Wavelet filters
      • Implementation
      • Moment conditions
  • IV Fast arithmetic
    • Fast multiplication and exponentiation
      • Splitting schemes for multiplication
      • Fast multiplication via FFT
      • Radix/precision considerations with FFT multiplication
      • The sum-of-digits test
      • Binary exponentiation
    • 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
    • Iterations for the inversion of a function
      • Iterations and their rate of convergence
      • Schröder's formula
      • Householder's formula
      • Dealing with multiple roots
      • More iterations
      • Convergence improvement by the delta squared process
    • The AGM, elliptic integrals, and algorithms for computing
      • The arithmetic-geometric mean (AGM)
      • The elliptic integrals K and E
      • Theta functions, eta functions, and singular values
      • AGM-type algorithms for hypergeometric functions
      • Computation of
    • Logarithm and exponential function
      • Logarithm
      • Exponential function
      • Logarithm and exponential function of power series
      • Simultaneous computation of logarithms of small primes
      • Arctangent relations for
    • Computing the elementary functions with limited resources
      • Shift-and-add algorithms for logb(x) and bx
      • CORDIC algorithms
    • 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
    • Recurrences and Chebyshev polynomials
      • Recurrences
      • Chebyshev polynomials
    • Hypergeometric series
      • Definition and basic operations
      • Transformations of hypergeometric series
      • Examples: elementary functions
      • Transformations for elliptic integrals
      • The function xx
    • Cyclotomic polynomials, product forms, and continued fractions
      • Cyclotomic polynomials, Möbius inversion, Lambert series
      • Conversion of power series to infinite products
      • Continued fractions
    • 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
      • Iteration 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 encoding the Hilbert curve
      • Sparse power series
      • An iteration related to the Fibonacci numbers
      • Iterations related to the Pell numbers
  • V Algorithms for finite fields
    • Modular arithmetic and some number theory
      • Implementation of the arithmetic operations
      • Modular reduction with structured primes
      • The sieve of Eratosthenes
      • The Chinese Remainder Theorem (CRT)
      • The order of an element
      • Prime modulus: the field Z/pZ=Fp=GF(p)
      • Composite modulus: the ring Z/mZ
      • Quadratic residues
      • Computation of a square root modulo m
      • The Rabin-Miller test for compositeness
      • Proving primality
      • Complex modulus: the field GF(p2)
      • Solving the Pell equation
      • Multiplication of hypercomplex numbers
    • Binary polynomials
      • The basic arithmetical operations
      • Multiplying binary polynomials of high degree
      • Modular arithmetic with binary polynomials
      • Irreducible polynomials
      • Primitive polynomials
      • The number of irreducible and primitive polynomials
      • Transformations that preserve irreducibility
      • Self-reciprocal polynomials
      • Irreducible and primitive polynomials of special forms
      • Generating irreducible polynomials from Lyndon words
      • Irreducible and cyclotomic polynomials
      • Factorization of binary polynomials
    • Shift registers
      • Linear feedback shift registers (LFSR)
      • Galois and Fibonacci setup
      • Error detection by hashing: the CRC
      • Generating all revbin pairs
      • The number of m-sequences and De Bruijn sequences
      • Auto-correlation of m-sequences
      • Feedback carry shift registers (FCSR)
      • Linear hybrid cellular automata (LHCA)
      • Additive linear hybrid cellular automata
    • Binary finite fields: GF(2n)
      • Arithmetic and basic properties
      • Minimal polynomials
      • Fast computation of the trace vector
      • Solving quadratic equations
      • Representation by matrices
      • Representation by normal bases
      • Conversion between normal and polynomial representation
      • Optimal normal bases (ONB)
      • Gaussian normal bases
    • The electronic version of the book
    • Machine used for benchmarking
    • The GP language
    • Bibliography
    • Index
    No review for this book yet, be the first to review.
      No comment for this book yet, be the first to comment
      You May Also Like
      Also Available On
      App store smallGoogle play small
      Curated Lists
      • Pattern Recognition and Machine Learning (Information Science and Statistics)
        by Christopher M. Bishop
        Data mining
        by I. H. Witten
        The Elements of Statistical Learning: Data Mining, Inference, and Prediction
        by Various
        See more...
      • CK-12 Chemistry
        by Various
        Concept Development Studies in Chemistry
        by John Hutchinson
        An Introduction to Chemistry - Atoms First
        by Mark Bishop
        See more...
      • Microsoft Word - How to Use Advanced Algebra II.doc
        by Jonathan Emmons
        Advanced Algebra II: Activities and Homework
        by Kenny Felder
        See more...
      • The Sun Who Lost His Way
        Tania is a Detective
        by Kanika G
        See more...
      • Java 3D Programming
        by Daniel Selman
        The Java EE 6 Tutorial
        by Oracle Corporation
        See more...