jaffer@zurich.ai.mit.edu (Aubrey Jaffer) (05/04/91)
I have created new versions of the programs which take the number of
decimal digits in a group as the second argument. This will allow the
user to tailor the calculation to avoid bignums.
time pi 800 4
9.3u 0.1s 0:10 94%
With 4 digits per group and (declare (usual-integrations)), compiled
MITScheme is now 2.7 times as fast as scm2d.
MITScheme
(show-time (lambda () (pi 200 4))) ==>
process time: 5960; real time: 7790
scm2d (made with -O)
(pi 200 4)
;Evaluation took 20966 mSec (1083 in gc) 242882 cons work
scm2d (made with -O -DRECKLESS)
(pi 200 4)
;Evaluation took 18666 mSec (1083 in gc) 242882 cons work
RECKLESS turns off error checking. The type and error checking in
scm2d accounts for 12% of its runtime.
------------------------------------------------------------------------
/* 'Spigot' algorithm origionally due to Stanly Rabinowitz */
main(c,v)
int c;char **v;{
int n=200,j,m,b=2,k,t,r=1,d=5;
long q;
short *a;
if(c>1)n=atoi(v[1]);
if(c>2)d=atoi(v[2]);
while(k++<d)r=r*10;
n=n/d+1;
k=m=3.322*n*d;
a=calloc(1+m,2);
while(k)a[--k]=2;
for(a[m]=4;j<n;b=q%r){
q=0;
for(k=m;k;){
q+=a[k]*r;
t=(2*k+1);
a[k]=q%t;
q=q/t;
q*=k--;}
printf("%0*d%s",d,b+q/r,++j%10?" ":"\n");}
puts("");}
;;; (pi n d) prints out n digits of pi in groups of d digits.
;(declare (usual-integrations))
(define (pi n d)
(let* ((r (do ((s 1 (* 10 s))
(i 0 (+ 1 i)))
((>= i d) s)))
(n (+ (quotient n d) 1))
(m (quotient (* n d 3322) 1000))
(a (make-vector (+ 1 m) 2)))
(vector-set! a m 4)
(do ((j 1 (+ 1 j))
(q 0 0)
(b 2 (remainder q r)))
((> j n))
(do ((k m (- k 1)))
((zero? k))
(set! q (+ q (* (vector-ref a k) r)))
(let ((t (+ 1 (* 2 k))))
(vector-set! a k (remainder q t))
(set! q (* k (quotient q t)))))
(let ((s (number->string (+ b (quotient q r)))))
(do ((l (string-length s) (+ 1 l)))
((>= l d) (display s))
(display #\0)))
(display (if (zero? (modulo j 10)) #\newline #\ )))
(newline)))