Erann Gat's wizzy piece of code for computing digits of pi:
(defun compute-pi-decimal (n &aux (p 0) r)
(dotimes (i n)
(incf p (/ (- (/ 4 (+ 1 (* 8 i)))
(/ 2 (+ 4 (* 8 i)))
(/ 1 (+ 5 (* 8 i)))
(/ 1 (+ 6 (* 8 i))))
(expt 16 i))))
(dotimes (i n)
(multiple-value-setq (r p) (truncate p 10))
(format t "~X" r)
(if (= (mod i 10) 1) (princ #\space))
(setf p (* p 10))))
Using bignums and 1.5 GB seems a little luxurious in comparison to Wozniak's using all of 48K (including video RAM) on an Apple II (which didn't even have integer multiply or divide) to compute 116,000 digits of e, but it's kind of neat.
CL-USER(19): (time (compute-pi-decimal 300)) 03 1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 8214808651 3282306647 0938446095 5058223172 5359408128 4811174502 8410270193 8521105559 6446229489 5493038196 4428810975 6659334461 2847564823 3786783165 2712019091 4564856692 3460348610 4543266482 1339360726 02491412 ; cpu time (non-gc) 23,090 msec user, 180 msec system ; cpu time (gc) 2,680 msec user, 30 msec system ; cpu time (total) 25,770 msec user, 210 msec system ; real time 32,284 msec ; space allocation: ; 3,937 cons cells, 1,685,652,448 other bytes, 0 static bytesPosted by jjwiseman at June 26, 2002 11:11 AM
Here's a way that's a bit faster...
It's one of the corman lisp examples.
(defun pi-atan (k n)
(do* ((a 0) (w (* n k)) (k2 (* k k)) (i -1))
((= w 0) a)
(setq w (truncate w k2))
(incf i 2)
(incf a (truncate w i))
(setq w (truncate w k2))
(incf i 2)
(decf a (truncate w i))))
(defun calc-pi (digits)
(let* ((n digits) (m (+ n 3)) (tenpower (expt 10 m)))
(values (truncate (- (+ (pi-atan 18 (* tenpower 48))
(pi-atan 57 (* tenpower 32)))
(pi-atan 239 (* tenpower 20)))
1000))))
Whoa, significantly faster. :)
200,000 digits in 14 minutes and 40 seconds, 2.9 GB of garbage.
Posted by: jjwiseman on July 9, 2002 11:58 PMEvaluation of (CALC-PI 10000) took 985.409670 seconds of elapsed time including:
13.422 seconds processing sequence breaks,
79.570 seconds in the storage system (including 0.831 seconds waiting for pages):
3.021 seconds processing 9309 page faults including 37 fetches,
76.157 seconds in creating and destroying pages, and
0.392 seconds in miscellaneous storage system tasks.
The garbage collector has flipped; so no consing was measured.
Symbolics 3640 with 7.5M word Physical memory running Genera 8.3
clisp has uncommonly good bignum support:
[2]> (time (compute-pi-decimal 300))
03 1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 8214808651 3282306647 0938446095 5058223172 5359408128 4811174502 8410270193 8521105559 6446229489 5493038196 4428810975 6659334461 2847564823 3786783165 2712019091 4564856692 3460348610 4543266482 1339360726 02491412
Real time: 0.039416 sec.
Run time: 0.03 sec.
Space: 1816928 Bytes
GC: 3, GC time: 0.0 sec.