Computers deal in fixed-size bit sequences. For instance, a dedicated machine instruction on a so-called "64-bit machine" may take two 64-bit sequences as input, and produce a 64-bit sequence as output. If you need more than 64 bits for your intermediate results, you must resort to issueing multiple such (or similar) instructions.

Intuitively, this bears resemblance to a common grade school mantra like:

> Doing arithmetic with up to 3-4 decimal places should be sufficient for all practical intents and purposes.

The purpose of this notebook is to showcase some practical examples where 64 bits proves insufficient. We take 64 bits since this is default in R. In particular, R uses double-precision binary floating-point numbers. We begin with a brief recap of what that means, more conretely.

## Binary Approximation

Computers deal in bit sequences, and so all data must be represented in binary notation, in one way or another.

The reader is humbly assumed to be familiar with the classical binary representation of the natural numbers i.e., the numbers 0, 1, 2, 3, ... This is a positional notation, where the symbols `0` or `1` (bits) are put in a sequence, with each position signifying the inclusion of a power of 2, with the most-signficant bit on the left end, and the least-signifcant bit to the right end of the sequence.

For instance, the 6-bit sequence `101010` signifies the number

\begin{align}
1\cdot2^5 + 0\cdot2^4 + 1\cdot2^3 + 0\cdot2^2 + 1\cdot 2^1 + 0 \cdot 2^0
&= 1\cdot2^5 + 1\cdot2^3 + 1\cdot 2^1 \\
&= 32 + 8 + 2 \\
&= 42
\end{align}

This notation bears structural resemblance to the classical decimal notation we learn in grade school. This too, is a positional notation, except that the symbols are `0`, `1`, `2`, ... , `9` (digits), and a position signifies the magnitude of an inclusion of a power of 10.

For instance, the 4-digit sequence `1337` signifies the number

\begin{align}
1\cdot{10}^{3} + 3\cdot{10}^{2} + 3\cdot{10}^{1} + 7\cdot{10}^{0}
&= 1000 + 300 + 30 + 7 \\
&= 1337
\end{align}

Classical binary represenation is elegant because there is a one-to-one mapping between natural numbers sequences of bits.

This elegance, much like one's spirit in grade school, breaks down with the introduction of fractions. Some fractions have a finite, decimal representation, compossed of a "decimal" and a "fractional" part, separated by a "radix point".

Numerically, we extend the powers of 10, right of 0, into the negative.

For instance, the 4-digit sequence `13.37` signifies the number

\begin{align}
1\cdot{10}^{1} + 3\cdot{10}^{0} + 3\cdot{10}^{-1} + 7\cdot{10}^{-2}
&= 10 + 3 + 0.3 + 0.07 \\
&= 13.37
\end{align}

This representation is useful for numbers where it applies since many standard algorithms, which worked for natural numbers, work for this representation, if we disregard the radix point until the very last.

There is no one-to-one mapping between the binary and decimal numbers, as soon as there is a radix point involved.

The following sections discuss two classical arithmetics, which are commonly supported directly in computer hardware. "Direct support" means that there typically exists a single machine instruction for every single operation we discuss, on most modern CPUs and GPUs.

Which (few) numbers can be represented exactly?

## Scientific Notation

## Combinators



### Sum

Here's a simple implementation of a summation function. This example is interesting also because you can imagine a summation intertwined with another operation.


```R
fpa_sum0 <- function (xs) {
  sum <- 0.0
  for (x in xs) {
    sum <- sum + x;
  }
  return(sum)
}
```

This seems good and dandy for small, and even some fairly large data sets:


```R
lapply(list(
  c(0.25, 0.25, 0.25),
  rep(0.25,100),
  rep(0.25,100000)
), fpa_sum0)
```

Yet, it yields some odd results for some fairly small data sets:


```R
lapply(list(
  rep(0.1,80),
  rep(0.2,120),
  rep(0.3,150)
), fpa_sum0)
```

Fortunately, if you use the built-in `sum`, you avoid such problems.


```R
lapply(list(
  c(0.25, 0.25, 0.25),
  rep(0.25,100),
  rep(0.25,100000)
), sum)
```


```R
lapply(list(
  rep(0.1,100),
  rep(0.2,150),
  rep(0.3,200)
), sum)
```

# Conclusion

The take-away from this is two-fold:

1. Use built-in, or carefully constructed combinators to gain a greater numerical stability.
2. Avoid a word-at-a-time style of programming. [(Backus, 1978)](#cite-backus-1978)

# References

1. <a name="cite-backus-1978"></a>John Backus. 1978. *Can programming be liberated from the von Neumann style? A functional style and its algebra of programs.* Commun. ACM 21, 8 (August 1978), 613-641.

b6a81672c7c8afc71f647c3db786bb55c06e8458
ipynb
Jupyter Notebook
notebooks/Numerical Literacy in R.ipynb
HIPERFIT/recipes
fa0106921054b78b06ff1dc5a0449c09840a73fa
MIT
2016-08-07T21:16:27.000Z
2016-12-03T01:54:38.000Z
notebooks/Numerical Literacy in R.ipynb
HIPERFIT/recipes
fa0106921054b78b06ff1dc5a0449c09840a73fa
MIT
2016-03-04T15:10:08.000Z
2016-05-10T14:27:33.000Z
notebooks/Numerical Literacy in R.ipynb
HIPERFIT/recipes
fa0106921054b78b06ff1dc5a0449c09840a73fa
MIT
2016-03-08T09:50:06.000Z
2020-10-16T02:24:31.000Z
Qwen/Qwen-72B
1. YES
2. YES