RE: Pi digits (again) - an unbounded spigot program
(05-18-2024 08:03 AM)EdS2 Wrote: I never had a clue how to rewrite Haskell into something I could understand.
These are translations to Python that are closer to the original Haskell programs.
They use typing and itertools which is missing in MicroPython.
So I had to remove them in the program for the Prime.
I'm using version 3.12.2.
There were some changes in the area of typing, so it might not work with older versions of Python.
Rabinowitz and Wagon
Code:
from fractions import Fraction
from itertools import count, islice
from sys import argv
from typing import Callable, Generator
State = tuple[int, int, int, int]
def main(n: int, k: int):
def stream(
next: Callable[[State], int],
safe: Callable[[State, int], bool],
prod: Callable[[State, int], State],
cons: Callable[[State, State], State],
z: State,
lfts: Generator[State, None, None],
) -> Generator[int, None, None]:
while True:
y = next(z)
if safe(z, y):
yield y
z = prod(z, y)
else:
[x] = list(islice(lfts, 1))
z = cons(z, x)
def extr(lft: State, x: int) -> Fraction:
"""
| q r | | x | = | q*x+r |
| s t | | 1 | | s*x+t |
"""
q, r, s, t = lft
return Fraction(q * x + r, s * x + t)
def prod(z: State, n: int) -> State:
"""
| 10 -10n | * z -> z
| 0 1 |
"""
return comp((10, -10 * n, 0, 1), z)
def comp(a: State, b: State) -> State:
"""
| q r | | u v | = | q*u+r*w q*v+r*x |
| s t | | w x | | s*u+t*w s*v+t*x |
"""
q, r, s, t = a
u, v, w, x = b
return q * u + r * w, q * v + r * x, s * u + t * w, s * v + t * x
cons = comp
init = (1, 0, 0, 1)
lfts = ((k, 4 * k + 2, 0, 2 * k + 1) for k in count(1))
pi = stream(next, safe, prod, cons, init, lfts)
for _ in range(n):
print("".join(map(str, islice(pi, k))))
if __name__ == "__main__":
n, k, *_ = argv[1:]
main(int(n), int(k))
Lambert
Code:
from fractions import Fraction
from itertools import count, islice
from sys import argv
from typing import Callable, Generator
LFT = tuple[int, int, int, int]
State = tuple[LFT, int]
def main(n: int, k: int):
def stream(
next: Callable[[State], int],
safe: Callable[[State, int], bool],
prod: Callable[[State, int], State],
cons: Callable[[State, LFT], State],
z: State,
lfts: Generator[LFT, None, None],
) -> Generator[int, None, None]:
while True:
y = next(z)
if safe(z, y):
yield y
z = prod(z, y)
else:
[x] = list(islice(lfts, 1))
z = cons(z, x)
def next(z: State) -> int:
[[q, r, s, t], i] = z
x = 2 * i - 1
return int(Fraction(q * x + r, s * x + t))
def safe(z: State, n: int) -> bool:
[[q, r, s, t], i] = z
x = 5 * i - 2
return n == int(Fraction(q * x + 2 * r, s * x + 2 * t))
def prod(s: State, n: int) -> State:
"""
| 10 -10n | * z -> z
| 0 1 |
"""
z, i = s
return comp((10, -10 * n, 0, 1), z), i
def cons(s: State, x: LFT) -> State:
z, i = s
return comp(z, x), i + 1
def comp(a: LFT, b: LFT) -> LFT:
"""
| q r | | u v | = | q*u+r*w q*v+r*x |
| s t | | w x | | s*u+t*w s*v+t*x |
"""
q, r, s, t = a
u, v, w, x = b
return q * u + r * w, q * v + r * x, s * u + t * w, s * v + t * x
init = ((0, 4, 1, 0), 1)
lfts = ((2 * i - 1, i**2, 1, 0) for i in count(1))
pi = stream(next, safe, prod, cons, init, lfts)
for _ in range(n):
print("".join(map(str, islice(pi, k))))
if __name__ == "__main__":
n, k, *_ = argv[1:]
main(int(n), int(k))
Gosper
Code:
from itertools import count, islice
from sys import argv
from typing import Callable, Generator
LFT = tuple[int, int, int, int]
State = tuple[LFT, int]
def main(n: int, k: int):
def stream(
next: Callable[[State], int],
prod: Callable[[State, int], State],
cons: Callable[[State, LFT], State],
u: State,
lfts: Generator[LFT, None, None],
) -> Generator[int, None, None]:
while True:
[x] = list(islice(lfts, 1))
v = cons(u, x)
y = next(v)
yield y
u = prod(v, y)
def next(z: State) -> int:
[[q, r, s, t], i] = z
x = 27 * i + 15
return (q * x + 5 * r) // (s * x + 5 * t)
def prod(s: State, n: int) -> State:
"""
| 10 -10n | * z -> z
| 0 1 |
"""
z, i = s
return comp((10, -10 * n, 0, 1), z), i
def cons(s: State, x: LFT) -> State:
z, i = s
return comp(z, x), i + 1
def comp(a: LFT, b: LFT) -> LFT:
"""
| q r | | u v | = | q*u+r*w q*v+r*x |
| s t | | w x | | s*u+t*w s*v+t*x |
"""
q, r, s, t = a
u, v, w, x = b
return q * u + r * w, q * v + r * x, s * u + t * w, s * v + t * x
init = ((1, 0, 0, 1), 1)
lfts = (
(i * (2 * i - 1), j * (5 * i - 2), 0, j)
for i, j in ((i, 3 * (3 * i + 1) * (3 * i + 2)) for i in count(1))
)
pi = stream(next, prod, cons, init, lfts)
for _ in range(n):
print("".join(map(str, islice(pi, k))))
if __name__ == "__main__":
n, k, *_ = argv[1:]
main(int(n), int(k))
You may have noticed though, that I replaced the recursive call to stream by an infinite loop.
Well, Pythonlacks tail call optimization, so we could end up with a stack overflow. Archive: unbounded-spigot.zip
Length Date Time Name
--------- ---------- ----- ----
1790 05-20-2024 11:17 pi-rabinowitz-wagon.py
1840 05-20-2024 11:17 pi-lambert.py
1630 05-20-2024 11:17 pi-gosper.py
--------- -------
5260 3 files
Search
Member List
Calendar
Help
/
Pi digits (again) - an unbounded spigot program
