Matters Computational: Ideas, Algorithms, Source Code

Free

Description

Contents

Reviews

Language

English

ISBN

Unknown

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

The book hasn't received reviews yet.