Euler's constant in bash

June 9, 2012

Compute euler's constant in bash.

I saw this today on HN. The idea is to write a bash script to compute $e$ in bash. The catch is obvious: bash natively supports only integer arithmetic. If one takes the bait they can use bc, as it is only natural to use bash for relatively simply tasks,and call in other programs for the rest. However it is possible to accomplish this task with just integer manipulations native to bash.
This is the idea for the algorithm. A base $10$ number, $4.745...$ can be written as $$\color{red}{4} + \frac{1}{10}\left( \color{red}{7} +\frac{1}{10} \left(\color{red}{4}+\frac{1}{10}\left(\color{red}{5}+\frac{1}{10}\left(\cdots\right)\right)\right)\right) $$ In this representation it is written as $[4;7,4,5,\cdots]_b$ where the base $b$ is $[1/10,1/10,1/10,\cdots]$. Turning to euler's number, it is $[2;7,1,2,8\cdots]$ in the same base. Factoring the series expression, we can write $e$ as $[2;1,1,1,\cdots]_{b'}$ in the base $b'=[1/2,1/3,1/4,\cdots]$. To compute the digits in the decimal version, we would follow something like, $b_0=e$, $b_n=10\{b_{n-1}\}$ getting $d_n=\lfloor b_n \rfloor$. The same principle is applied here. The spigot algorithm systematically computes each digit by converting the mixed base digits (which are already known) to the decimal system. It is described in full here.

Sample Output

[bin]$ eulernumer 500 # returns
2.7182 8182 8459 0452 3536 0287 4713 5266 2497 7572 4709 3699 9595 7496 6967 6277 2407
  6630 3535 4759 4571 3821 7852 5166 4274 2746 6391 9320 0305 9921 8174 1359 6629 0435
  7290 0334 2952 6059 5630 7381 3232 8627 9434 9076 3233 8298 8075 3195 2510 1901 1573
  8341 8793 0702 1540 8914 9934 8841 6750 9244 7614 6066 8082 2648 0016 8477 4118 5374
  2345 4424 3710 7539 0777 4499 2069 5517 0276 1838 6062 6133 1384 5830 0075 2044 9338
  2656 0297 6067 3711 3200 7093 2870 9127 4437 4704 7230 6969 7720 9310 1416 9283 6819
  0255 1510 8657 4637 7211 1252 3897 8442 5056 9536 9677 0785 4499 6996 7946 8644 5490
  5987 9316 3688 9230 0987 9312

Test

Comparing against Unix's arbitrary precision library.

[bin]$ diff -s <(echo 'scale=500;e(1)' | bc -l | tr -d [:space:] | tr -d '\\') <(eulernumber 500 | tr -d [:space:])

Files /dev/fd/63 and /dev/fd/62 are identical

Looks good.

Code

#!/bin/bash

    ####--------EULERNUMBER------------
    # Computes euler's number using the
    # algorithm of Rabinowitz and Wagon[1].
    # Implemented in (ba)sh by D Jha. 
    # Last Modified: 06/08/12
    # [1] "A Spigot Algorithm for the Digits of Pi"
    ####-------------------------------

    if [ $BASH_VERSINFO -lt 3 ]; then
        echo "Warning: Version may be too old" >&2
    fi

    if [ $# -gt 0 ]; then
        N=$1
    else
        echo -n 'Enter the number of digits: '
        read N
    fi

    #### SPIGOT ALGORITHM
    echo -n '2.'

    for ((i=0;i<N;i++)) do
        A[i]=1
    done

    for ((i=0;i<N;i++)) do
        q=0
        for ((j=N-1;j>=0;)) do
            (( A[j]=10*A[j]+q ))
            (( q=A[j]/(j+2) ))
            (( A[j]= A[j]%(j+2) ))
            (( j-- ))
        done
        echo -n $q
        #Comment out this if-block if piping the output/running diff, etc
        # or, strip out spaces. eg $> eulernumber 43 | tr -d [:space:]
        if (( ($i+1)%4 == 0 )); then 
      echo -n ' ' #nicer formatting
        fi
    done

    echo