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
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
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
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:
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)
GoogleCloudPlatform/pi-delivery @GitHub source
REST API to fetch 100 digits of Pi from the specified starting point
(max 1000 digits per request), example:
more info:
The most distant spacecraft from Earth is Voyager 1. It is about 12.5 billion miles away.
... calculated circumference of the 25 billion mile diameter circle would be wrong by 1.5 inches.
No comments:
Post a Comment