A wild e appears
Here’s a fun math tidbit:
Select a random number between 0 and 1. Now select another and add it to the first. Keep doing this, piling on random numbers. How many random numbers, on average, do you need to make the total greater than 1? Answer: 2.71828….
– John Derbyshire, Prime Obsession
The inimitable MathWorld has more info on it, and the first link above has a nice proof sketch involving the standard simplex (modified from Derbyshire’s book), as well as some Clojure code.
Repo, Man
I’ve used this problem for a short programming exercise a number of times, and I really like it. Besides the fun math involved, it can give a decent understanding of how to get things done in a language. For instance, tackling it in Haskell can lead to thinking about monads (or not), while doing it in a high performance language can make one think about ways to squeeze out every last drop of performance. I’ve collected implementations in a number of different languages here. Some highlights and/or interesting points:
- The Rust version uses
rayon
for parallelism and a modification of Welford’s online algorithm for calculating the mean. This problem has a lot of room for exploring parallelism, trading memory for time, and more. - The array language versions in BQN and ngn/k do an approximation where they build a large matrix of uniform variates and approximate from there, rather than relying on loops or recursion.
- Writing WebAssembly by hand and calling it from TypeScript is surprisingly
painless (thanks to a
pcg
implementation I found); What’s more, it’s competitive with the more “low-level” C/C++ and their ilk. - Some things are much easier to package in a
nix
flake than others.