Re: Tail call optimization
On Thu, Feb 13, 2025 at 07:38:10AM +0100, Alexander Burger wrote: > When I built the tco version yesterday, I experimended with both > versions, and somehow the 'M' code was lost :( OK, I will settle with this version: # Print next digit of PI (de digit (Env) (job Env (tco (Q R S K N L) (if (>= (- (+ R (* 4 Q)) S) (* N S)) (tc (* Q K) (* L (+ R (* 2 Q))) (* S L) (inc K) (/ (+ (* Q (+ 2 (* 7 K))) (* R L)) (* S L)) (+ 2 L) ) ) (prog1 N (let M (- (/ (* 10 (+ R (* 3 Q))) S) (* 10 N)) (setq Q (* 10 Q) R (* 10 (- R (* N S))) N M) ) ) ) ) ) # Print 'N' or all digits of PI (de pi (N) (let E (env 'Q 1 'R 0 'S 1 'K 1 'N 3 'L 3) (prin (digit E) ".") (do (or N T) (prin (digit E)) (flush) ) ) (prinl) ) The 'job' environment is factored out of 'digit' so that 'pi' can be restarted like: $ ./pil misc/pi.l + : (pi 7) 3.1415926 -> NIL : (pi 30) 3.141592653589793238462643383279 -> NIL : (pi) 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669... ☺/ A!ex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Tail call optimization
On Thu, Feb 13, 2025 at 08:50:16AM -0800, Lindsay Lawrence wrote: > I think it is also a good a test/example of picolisp's support for bignums. Indeed. The numbers in the 'E' environment get quite big. After ten thousand digits of PI, 'S' and 'Q' have 145746 digits and 'R' has 145748 digits. I verified that the first hundred thousand ouput digits are correct. ☺/ A!ex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Tail call optimization
On Thu, Feb 13, 2025 at 9:37 AM Alexander Burger wrote: > On Thu, Feb 13, 2025 at 08:50:16AM -0800, Lindsay Lawrence wrote: > > I think it is also a good a test/example of picolisp's support for > bignums. > > Indeed. The numbers in the 'E' environment get quite big. After ten > thousand digits of PI, 'S' and 'Q' have 145746 digits and 'R' has 145748 > digits. > > I verified that the first hundred thousand ouput digits are correct. > > Super. I learned a new (to me) picolisp function from the updated code in your other email, 'env', as well as the utility of 'prog1'. It takes a while to get to 100K on my machine! Thanks! /Lindsay
Re: Tail call optimization
> > > > Sorry again for the confusion! > > 👍 I think it is also a good a test/example of picolisp's support for bignums. It could be a fun exercise to implement a version of this with one of the other Pi algorithms that discards already computed digits so it could essentially just churn out digits of pi as long as it existed without any loss of performance. /Lindsay
Re: Tail call optimization
On Thu, Feb 13, 2025 at 9:37 AM Alexander Burger
wrote:
> On Thu, Feb 13, 2025 at 08:50:16AM -0800, Lindsay Lawrence wrote:
> > I think it is also a good a test/example of picolisp's support for
> bignums.
>
> Indeed. The numbers in the 'E' environment get quite big. After ten
> thousand digits of PI, 'S' and 'Q' have 145746 digits and 'R' has 145748
> digits.
>
> I verified that the first hundred thousand ouput digits are correct.
>
A bit of searching came up with the paper with the haskell version
https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf
Interestingly enough there is another version of PI in there, recursive,
based on the Gosper series,
that a faster... although it is based on a conjecture they haven't proven
in that paper.
The picolisp version of that one is below ('tco' is a nice fit for it as
well!)
(de piDigits (N)
(default Q 1 R 180 S 60 I 2)
(tco
(Q R S I N)
(let
(U
(*
3
(+ (* 3 I) 1)
(+ (* 3 I) 2) )
Y
(/
(+
(* Q (- (* 27 I) 12))
(* 5 R) )
(* 5 S) ) )
(prin Y)
(if (or (not N) (gt0 N))
(tc
(* 10 Q I (- (* 2 I) 1))
(*
10
U
(-
(+ (* Q (- (* 5 I) 2)) R)
(* Y S) ) )
(* S U)
(+ I 1)
(dec N) ) ) ) ) )
On my machine that outputs digits of PI like below
: (bench (out "pi-digits.1.txt" (piDigits 1)))
8.751 sec
-> NIL
: (bench (out "pi-digits.1.txt" (piDigits 5)))
117.745 sec
-> NIL
: (bench (out "pi-digits.1.txt" (piDigits 10)))
613.212 sec
-> NIL
/Lindsay
