numeric.md

Numeric data structures and algorithms

Table of contents

• Introduction and overview
• Floating-point arithmetic
  • IEEE 754
    • Denormal numbers
    • NaNs
  • Applications
  • History
• Arithmetic algorithms
  • Common functions
    • Powers and logarithms
    • Square root
    • Inverse square root
  • Greatest common divisor (GCD)
    • Euclidean algorithm
    • Binary Euclidean algorithm (Stein’s algorithm)
  • Interpolation
  • Arithmetic means
  • Binomial coefficient
  • Division algorithms
    • Integer division
  • Horner’s method
  • Kahan summation algorithm
• Prime numbers
• Linear equations solution algorithms
  • Iterative methods
    • Jacobi method
• Matrix diagonalization
  • Jacobi eigenvalue algorithm
• Wavelets
• Applications
  • Finite elements and finite volume methods

---

Introduction and overview

🔗

• R.Munafo. Notable properties of specific numbers

🎥

• S.Strogatz. The beauty of calculus (2019)
• S.Strogatz. The joy of x: A guided tour of math (2014)

---

Floating-point arithmetic

Floating-point arithmetic is arithmetic in which real numbers are represented approximately to a fixed number of significant digits and scaled using an exponent in some fixed base: r = significand × baseexponent. The relative error due to rounding is uniform, i.e. it is independent of the magnitude of the number. The binary-based floating-point system has the smallest possible wobble (a range of relative errors).

🔗

• Floating-point arithmetic – Wikipedia
• C.Moler. Floating point arithmetic before IEEE 754 (2019)

📖

• Essay 3: Floating-point arithmetic, Essay 5: Safe math – P.J.Plauger. Programming on purpose III: Essays on software technology (1994)

📄

• J.Gustafson, I.Yonemoto. Beating floating point at its own game: Posit arithmetic

IEEE 754

IEEE 754 is a technical standard for floating-point arithmetic established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). If two (non-extended) floating-point numbers in the same format are ordered, then they are ordered the same way when their bits are reinterpreted as sign-magnitude integers. NaNs are endowed with a field of bits into which software can record, say, how and/or where the NaN came into existence; no software exists now to exploit this feature.

🔗

• R.Harris. You’re going to have to think! – Overload 99 (2010)
• R.Harris. Why fixed point won’t cure your floating point blues – Overload 100 (2011)
• R.Harris. Why rationals won’t cure your floating point blues – Overload 101 (2011)
• D.Goldberg. What every computer scientist should know about floating-point arithmetic (1991)

❔

• How many unique values are there between 0 and 1 of a standard float? – Stack Overflow
• Why does IEEE 754 reserve so many NaN values? – Stack Overflow
• How many normalized numbers can be represented using IEEE-754 single precision? – Stack Overflow
• Is assigning two doubles guaranteed to yield the same bitset patterns? – Stack Overflow

📄

• W.Kahan. Lecture notes on the status of IEEE standard 754 for binary floating-point arithmetic (1997)
• C.Allison. Where did all my decimals go? (2006)

📖

• M.L.Overton. Numerical computing with IEEE floating point arithmetic – SIAM (2001)
• Sec. 2.5: Floating-point arithmetic – D.H.Eberly. GPGPU programming for games and science – CRC Press (2014)
• C.Allison. Floating-point numbers aren’t real – K.Henney. 97 things every programmer should know (2010)

🎥

• J.Farrier. Demystifying floating point – CppCon (2015)
• J.Gustafson. Beating floats at their own game – HPC Advisory Council Australia Conference (2017)

⚓

• IEEE 754 – Wikipedia

Denormal numbers

🔗

• Denormal number – Wikipedia
• C.Moler. Floating point denormals, insignificant but controversial (2014)

🎥

• D.Kohlbrenner. On subnormal floating point and abnormal timing – IEEE Symposium on Security and Privacy (2015)

NaNs

🔗

• A.Cherkaev. The secret life of NaN (2018)

❔

• What is the rationale for all comparisons returning false for IEEE 754 NaN values? – Stack Overflow

🎥

• A.Cherkaev. The secret life of Not-a-Number – Con West (2019)

Applications

🔗

• M.Rayman. How many decimals of π do we really need? – NASA (2016)

History

🔗

• C.Severance. An interview with the old man of floating-point (1998)

---

Arithmetic algorithms

🔗

• T.Prince. Tuning up math functions – C/C++ Users Journal 10 (1992)

Common functions

📖

• Essay 6: Do-it-yourself math functions – P.J.Plauger. Programming on purpose III: Essays on software technology (1994)

Powers and logarithms

🔗

• How to check if an integer is a power of 3? – Stack Overflow

Square root

🔗

• Methods of computing square roots – Wikipedia
• P.Martin. Eight rooty pieces – Overload 135 (2016)

Inverse square root

🔗

• Fast inverse square root – Wikipedia
• C.Lomont. Fast inverse square root (2003)

Greatest common divisor (GCD)

Euclidean algorithm

🔗

• Euclidean algorithm – Wikipedia

Binary Euclidean algorithm (Stein’s algorithm)

🔗

• Binary GCD algorithm – Wikipedia

Interpolation

🔗

• J.Bloch. [Extra, Extra – Read all about it: Nearly all binary searches and mergesorts are broken] – Google AI blog (2006)

❔

• What are the differences between the two lerp functions? – Stack Overflow
• Floating point linear interpolation – Stack Overflow
• Accurate floating-point linear interpolation – Mathematics

⚓

• S.D.Herring. Well-behaved interpolation for numbers and pointers – WG21/P0811

Arithmetic means

To compute the arithmetic mean μ = 1 / N ∑ xi in a numerically stable way, the following recurrence relation can be used: μN = μN - 1 + 1 / N (xN - μN - 1).

🔗

• D.Assencio. Numerically stable computation of arithmetic means (2015)
• T.Finch. Incremental calculation of weighted mean and variance (2009)

Binomial coefficient

🔗

• M.Dominus. How to calculate binomial coefficients
• M.Dominus. How to calculate binomial coefficients, again

Division algorithms

Integer division

🔗

• I.Kaplan. Integer division (1996)

Horner’s method

Horner’s method is a polynomial evaluation method expressed by p(x) = a0 + a1 x + a2 x2 + ... + aN xN = a0 + x (a1 + x (a2 + ... + x (aN) ... )).

🔗

• Horner’s method – Wikipedia

Kahan summation algorithm

🔗

• Kahan summation algorithm – Wikipedia

❔

• Kahan summation – Stack Overflow

---

Prime numbers

❔

• How many prime numbers are there (available for RSA encryption)? – Stack Overflow

---

Linear equations solution algorithms

Iterative methods

🔗

• G.Strang. Iterative methods (2006)

📖

• Sec. 20.5: Relaxation methods for boundary value problems – W.H.Press et al. Numerical recipes: The art of scientific computing (2007)

Jacobi method

A recurrence relation: xK+1 = D-1 (D - A) xK + D-1 b, where the preconditioner D is the diagonal part of A: D = diag(A).

🔗

• Jacobi method – Wikipedia
• Jacobi method – Wolfram MathWorld

🎥

• G.Strang. Iterative methods and preconditioners – MIT 18.086 Mathematical methods for engineers II (2006)

---

Matrix diagonalization

Jacobi eigenvalue algorithm

🔗

• Jacobi eigenvalue algorithm – Wikipedia
• J.Lambers. Jacobi methods – CME 335 (2010)

📖

• Sec. 11.1: Jacobi transformations of a symmetric matrix – W.H.Press et al. Numerical recipes: The art of scientific computing (2007)
• Sec. 8.5: Jacobi methods – G.H.Golub, C.F.Van Loan. Matrix computations – SIAM (2013)
• H.Rutishause. Contrib. II/1: The Jacobi method for real symmetric matrices – J.H.Wilkinson, C.Reinsch. Handbook for automatic computation. Vol. II: Linear algebra (1971)

---

Wavelets

🎥

• G.Strang. Multiresolution, wavelet transform and scaling function – MIT 18.085 Computational science and engineering I (2008?)
• G.Strang. Splines and orthogonal wavelets: Daubechies construction – MIT 18.085 Computational science and engineering I (2008?)

📖

• Sec. 11.1: Jacobi transformations of a symmetric matrix – W.H.Press et al. Numerical recipes: The art of scientific computing (2007)

---

Applications

Finite elements and finite volume methods

🎥

• D.Arnold. The fundamental theorem of numerical analysis – Annual conference of the Great Lakes section of the SIAM (2015)
• P.Roe. Colorful fluid dynamics: Behind the scenes – AE585 Seminar lecture series (2014)