Approximating e With SQL

Posted on by lukaseder

If you’re running on PostgreSQL, you could try the following cool query:

WITH RECURSIVE
  r (r, i) AS (
    SELECT random(), i 
    FROM generate_series(1, 1000000) AS t (i)
  ),
  s (ri, s, i) AS (
    SELECT i, r, i
    FROM r
    UNION ALL
    SELECT s.ri, r.r + s.s, s.i + 1
    FROM r
    JOIN s ON r.i = s.i + 1
    WHERE r.r + s.s <= 1
  ),
  n (n) AS (
    SELECT max(i) - min(i) + 2
    FROM s
    GROUP BY ri
  )
SELECT avg(n)
FROM n

What does it print (after a while)? It prints e (almost). Here are some sample results:

2.7169115477960698
2.7164145522690296
2.7172065451410937
2.7170815462660836

Not perfect, sure, here’s a better approximation written in SQL:

SELECT exp(1);

Producing:

2.718281828459045

Close enough… How does it work? It’s a cool approximation that has been described many times, e.g. here. In prose:

On average, it takes e random values between 0 and 1 until the sum of those values exceeds 1.

Looking at the query again:

WITH RECURSIVE
  -- "random values between 0 and 1"
  r (r, i) AS (
    SELECT random(), i 
    FROM generate_series(1, 1000000) AS t (i)
  ),
  s (ri, s, i) AS (
    SELECT i, r, i
    FROM r
    UNION ALL
    SELECT s.ri, r.r + s.s, s.i + 1
    FROM r
    JOIN s ON r.i = s.i + 1
    -- "... until the sum exceeds 1"
    WHERE r.r + s.s <= 1
  ),
  -- "number of values taken until ..."
  n (n) AS (
    SELECT max(i) - min(i) + 2
    FROM s
    GROUP BY ri
  )
-- "on average"
SELECT avg(n)
FROM n

In prose, read from top to bottom:

  • I’m generating 1 million random values between 0 and 1
  • Starting from each one of those values, I’m adding consecutive values as long as their sum does not exceed 1
  • For each value, I check how many values it took until the sum exceeded 1
  • I take the average of that number of values

Highly inefficient, but that wasn’t the point. :-)

Published by lukaseder

I made jOOQ

3 thoughts on “Approximating e With SQL”

  1. A couple other approximations:

    1) I needed SQRT for a “real” project [ https://github.com/RANDCorporation/milliondigits/blob/master/reproduce_results.sql#L100 ] before sqlite had math functions built in by default, so I used the Newton-Raphson method to calculate it. Abbreviated version of the code that only does the sqrt approximation:

    sqlite> WITH RECURSIVE nr_sqrt(q,estimate,epsilon) AS (SELECT 2.0, 2.0, 1e-10
    UNION ALL SELECT q, (estimate+q/estimate)/2, epsilon FROM nr_sqrt
    WHERE epsilon

    2) The ratio of terms in the fibonacci sequence converges to the golden ratio:

    sqlite> WITH RECURSIVE fib(a,b,ratio,n) AS (SELECT 1,1,1,0 UNION ALL
    SELECT b, a+b, 1.0*(a+b)/b, n+1 FROM fib WHERE n

    Everyone had a project during early covid. Mine was a SQL reproduction of a 65-year venerated paper where I work. https://github.com/RANDCorporation/milliondigits

    Gary

    Reply

    2. Oops. Someone’s security thing clipped the less-than symbol and everything following it in the NR approximation. Flipping the inequality hopefully gets around that:

      WITH RECURSIVE nr_sqrt(q,estimate,epsilon) AS (SELECT 2.0, 2.0, 1e-10
      UNION ALL SELECT q, (estimate+q/estimate)/2, epsilon FROM nr_sqrt
      WHERE ABS(estimate*estimate-q)>epsilon)
      SELECT estimate FROM nr_sqrt;

      Reply

Leave a Reply