Monday, March 14, 2022

π fs - the data-free filesystem, with Pi spigot algorithm

 philipl/pifs: πfs - the data-free filesystem!

"π (or pi) is one of the most important constants in mathematics and has a variety of interesting properties (which you can read about at wikipedia)

One of the properties that π is conjectured to have is that it is normal, which is to say that its digits are all distributed evenly, with the implication that it is a disjunctive sequence, meaning that all possible finite sequences of digits will be present somewhere in it. If we consider π in base 16 (hexadecimal) , it is trivial to see that if this conjecture is true, then all possible finite files must exist within π. The first record of this observation dates back to 2001.

πfs is a revolutionary new file system that, instead of wasting space storing your data on your hard drive, stores your data in π! You'll never run out of space again - π holds every file that could possibly exist! They said 100% compression was impossible? You're looking at it!"


Bailey–Borwein–Plouffe formula - Wikipedia

is a formula for π.

The BBP formula gives rise to a spigot algorithm for computing the nth base-16 (hexadecimal) digit of π (and therefore also the 4nth binary digit of π) without computing the preceding digits. This does not compute the nth decimal of π (i.e., in base 10).[3] BBP and BBP-inspired algorithms have been used in projects such as PiHex[4] for calculating many digits of π using distributed computing.


With a nod to fellow pi-hound Dik T Winter, three equal lines of C give 32k digits of pi:

http://leapsecond.com/tools/pi3.c

brilliant method of embedding his name in the code without wasting lines for comments

iijlab-seminar-20170327.pdf


A Spigot Algorithm for the Digits of π Authors: Stanley Rabinowitz and Stan Wagon



Here's a C version from Winter and Flammenkamp:

unsigned s, P, I, g[109970], o = 10000, t = 109970, by, Dik, T, Winter;
main() {
  for (; s = t, t -= 14; Winter = printf("%04d", Dik + P / o), Dik = P % o)
    while (I = --s * 2)
      P = T * s + o * (Winter ? g[s] : o / 5), T = P / --I, g[s] = P - I * T;

"Pi" day: pi digits & code

Pi - Wikipedia  π

fast "PI" calculation is now possible thanks to (relatively) new algorithm
and languages as Python and now JavaScript that support "unlimited" digits numbers

Pi - Rosetta Code, in many programming languages

cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf

Unbounded Spigot Algorithms for the Digits of Pi Jeremy Gibbons

PY: pi digits: 10000 time:  11.72525 sec JS: PiGen digits: 10000 time: 26.08004309999943 sec
C#: Pi digits: 10000 time: 15.902 sec Go: GenPiA digits: 10000 time: 6.1173453s

BigInt - JavaScript | MDN

BigIntBigInt is a special numeric type that provides support for integers of arbitrary length.

BigInt | Can I use... Support tables for HTML5, CSS3, etc

BigInt numbers in JavaScript have "n" suffix when assigned

JavaScript

function* genPi() {
  var [q, r, t, k, n, l, nn, nr] = [1n, 0n, 1n, 1n, 3n, 3n, 0n, 0n]
  while (true) {
    if (4n * q + r - t < n * t) {
      yield n
      nr = 10n * (r - n * t)
      n = (10n * (3n * q + r)) / t - 10n * n
      q *= 10n
      r = nr
    } else {
      nr = (2n * q + r) * l
      nn = (q * (7n * k) + 2n + (r * l)) / (t * l)
      q *= k
      t *= l
      l += 2n
      k += 1n
      n = nn
      r = nr
    }
  }
}

const pi = genPi();
for (var i = 0; i < 1000; i++) {
  console.log(pi.next().value.toString());
}

Pi - Rosetta Code: Python

def gen_pi():
    q, r, t, k, n, l = 1, 0, 1, 1, 3, 3
    while True:
        if 4*q+r-t < n*t:
            yield n
            nr = 10*(r-n*t)
            n = ((10*(3*q+r))//t)-10*n
            q *= 10
            r = nr
        else:
            nr = (2*q+r)*l
            nn = (q*(7*k)+2+(r*l))//(t*l)
            q *= k
            t *= l
            l += 2
            k += 1
            n = nn
            r = nr

count = 0
for d in gen_pi():
    sys.stdout.write(str(d))
    count += 1
    if count >= 1000:
        break
3141592653589793238462643383279502884197
1693993751058209749445923078164062862089
9862803482534211706798214808651328230664
7093844609550582231725359408128481117450
2841027019385211055596446229489549303819
6442881097566593344612847564823378678316
5271201909145648566923460348610454326648
2133936072602491412737245870066063155881
7488152092096282925409171536436789259036
0011330530548820466521384146951941511609
4330572703657595919530921861173819326117
...

C# (dotnet)

  public static IEnumerable<BigInteger> GenPiDigits()
  {
    BigInteger b1 = BigInteger.One, b2 = new BigInteger(2), b3 = new BigInteger(3),
      b4 = new BigInteger(4), b7 = new BigInteger(7), b10 = new BigInteger(10),
      k = b1, l = b3, n = b3, q = b1, r = BigInteger.Zero, t = b1, nn, nr;
    while (true)
    {
      if ((b4 * q + r - t).CompareTo(n * t) == -1)
      {
        yield return n;
        nr = b10 * (r - (n * t));
        n = b10 * (b3 * q + r) / t - (b10 * n);
        q *= b10;
        r = nr;
      }
      else
      {
        nr = (b2 * q + r) * l;
        nn = (q * (b7 * k) + b2 + r * l) / (t * l);
        q *= k;
        t *= l;
        l += b2;
        k += b1;
        n = nn;
        r = nr;
      }
    }
  }

 int i = 0;
  foreach (var n in Algorithms.GenPiDigits())
  {
Console.Write(n.ToString());
    if (i++ > 1000) break;
  }

GoLang

import (
  "math/big" // https://pkg.go.dev/math/big#Int
)

// returns an array (slice) of "max" digits of pi
// the BitInt lib has specific syntax that makes code more complex; it is fast though :)
func GenPiA(max int) []int {
  _1, _2, _3, _4, _7, _10 := big.NewInt(1), big.NewInt(2), big.NewInt(3), big.NewInt(4), big.NewInt(7), big.NewInt(10)
  q, r, t, k, n, l, nn, nr := big.NewInt(1), big.NewInt(0), big.NewInt(1), big.NewInt(1), big.NewInt(3), big.NewInt(3), big.NewInt(0), big.NewInt(0)
  _x, _y := new(big.Int), new(big.Int)
  i := 0
  var digits []int = make([]int, max)
  for {
    // if (4n * q + r - t < n * t) {
    if _x.Mul(_4, q).Add(_x, r).Sub(_x, t).Cmp(_y.Mul(n, t)) == -1 {
      digits[i] = int(n.Int64())
      i += 1
      if i >= max {
        return digits
      }
      // nr = 10n * (r - n * t)
      nr.Mul(_10, _x.Sub(r, _y.Mul(n, t)))
      // n = (10n * (3n * q + r)) / t - 10n * n
      n.Mul(_3, q).Add(n, r).Mul(n, _10).Div(n, t).Sub(n, _y.Mul(_10, n))
      q.Mul(q, _10) // q *= 10n
      r.Set(nr)     // r = nr
    } else {
      // nr = (2n * q + r) * l
      nr.Mul(_x.Add(_y.Mul(_2, q), r), l)
      // nn = (q * (7n * k) + 2n + (r * l)) / (t * l)
      nn.Mul(_7, k).Mul(nn, q).Add(nn, _2).Add(nn, _x.Mul(r, l)).Div(nn, _y.Mul(t, l))
      q.Mul(q, k)  // q *= k
      t.Mul(t, l)  // t *= l
      l.Add(l, _2) // l += 2n
      k.Add(k, _1) // k += 1n
      n.Set(nn)    // n = nn
      r.Set(nr)    // r = nr
    }
  }
}


Pi - Rosetta Code PicoLisp

picolisp/picolisp: PicoLisp is an open source Lisp dialect. It runs on Linux and other POSIX-compliant systems. Its most prominent features are simplicity and minimalism. @GitHub

Pi - Rosetta Code: C

Pi - Rosetta Code: Go




This algorithm is based on an unproven conjecture but successfully produces at least the first 1 million digits. Read more about it here: https://www.gavalas.dev/blog/spigot-algorithms-for-pi-in-python/

Python: less code, more time

def gospers_pi_unproven():
    q, r, t, i = 1, 180, 60, 2
    while True:
        u, y = 3*(3*i+1)*(3*i+2), (q*(27*i-12)+5*r)//(5*t)
        yield y
        q, r, t, i = 10*q*i*(2*i-1), 10*u*(q*(5*i-2)+r-y*t), t*u, i+1

JavaScript

// Calculate digits of π, yields digits one by one
function* GenPi2() {
  let q = 1n, r = 180n, t = 60n
  for (let i = 2n; ; i += 1n) {
    let y = (q * (27n * i - 12n) + 5n * r) / (5n * t)
    let u = 3n * (3n * i + 1n) * (3n * i + 2n)
    r = 10n * u * (q * (5n * i - 2n) + r - y * t)
    q = 10n * q * i * (2n * i - 1n)
    t = t * u
    yield Number(y)
  }
}

GoLang: more code, less execution time :) Was not easy to make it work... 

// returns an array (slice) of "max" digits of pi
// the BitInt lib has specific syntax that makes code much more complex; it is fast though :)
func GenPi2A(max int) []int {
  _1, _2, _3, _5, _10, _12, _27 :=
    big.NewInt(1), big.NewInt(2), big.NewInt(3), big.NewInt(5), big.NewInt(10), big.NewInt(12), big.NewInt(27)
  // q = 1, r = 180, t = 60, i = 2
  q, r, t, i := big.NewInt(1), big.NewInt(180), big.NewInt(60), big.NewInt(2)
  y, u, x := new(big.Int), new(big.Int), new(big.Int)
  var digits []int = make([]int, max)
  for count := 0; count < max; count++ {
    // y = (q * (27 * i - 12) + 5 * r) / (5 * t) = ((27 * i - 12) * q + (5 * r)) / (5 * t)
    y.Mul(_27, i).Sub(y, _12).Mul(y, q).Add(y, x.Mul(_5, r)).Div(y, x.Mul(_5, t))
    // u = 3 * (3 * i + 1) * (3 * i + 2) = ((3 * i) + 1) * ((3 * i) + 2) * 3
    // u.Mul(_3, i).Add(u, _1).Mul(u, _3).Mul(u, x.Mul(_3, i).Add(x, _2)) // 6 calls
    u.Add(x.Mul(_3, i), _1).Mul(u, x.Add(x, _2)).Mul(u, _3) // 5 calls, better, faster
    // r = 10 * u * (q * (5 * i - 2) + r - y * t) = (r - (y * t) + (5 * i - 2) * q) * 10 * u
    r.Sub(r, x.Mul(y, t)).Add(r, x.Mul(_5, i).Sub(x, _2).Mul(x, q)).Mul(r, _10).Mul(r, u)
    // q = 10 * q * i * (2 * i - 1)
    q.Mul(_10, q).Mul(q, i).Mul(q, x.Mul(_2, i).Sub(x, _1))
    // t = t * u
    t.Mul(t, u)
    // digits[count] = Number(y)
    digits[count] = int(y.Int64())
    // i += 1
    i.Add(i, _1)
  }
  return digits
}


there is "official" competition of programming languages and algorithms, here:

pidigits (Benchmarks Game)

The Computer Language
22.03 Benchmarks Game



digits of Pi are also available online

including first 1000 digits of Pi


a very large number of digits of Pi is calculated by Google (as world record) and available as API

Google: serving the Pi (world record)




REST API to fetch 100 digits of Pi from the specified starting point 
(max 1000 digits per request), example:


more info: