July 24, 2024
We give here a simple algorithm to compute digits of E. Its value is naturally available as a real number (type |(expt 1.)|), but it is significantly more difficult to determine more than, say, the 16 digits of 64-bit reals, for we must now develop the algorithm to compute the exponential.
It is a known fact (almost a definition !) that
Of course the numbers involved get extremely large or small, so we need some kind of computational trick to obtain a meaningful result. The idea is to represent e as a fixed-point multi-digit number in a variable base, and then convert it to decimal. Let us first refine these concepts.
A number x in b-base is a tuple (…x1x0.x-1…) such that
The numbers are represented as infinite sequences extending one way using streams (quick, dash to your manual to check your knowledge). The digits will then be computed on demand, with no limitation except memory and time.
This routine will convert the e-base number |x| to decimal. The basic algorithm goes:
Note the |(normalize 2 ...)| calls normalize with a source base of 2. Normalize increments this value for successive digits.
(define (convert x) (cons-stream (head x) (convert (normalize 2 (cons-stream 0 (mult (tail x)))))))
Multiply a number by 10. (define (mult x) (cons-stream (* 10 (head x)) (mult (tail x))))
Normalize the number. If its second digit is small enough, leave the current one unchanged; otherwise bump up the current digit and down the second one. Then call normalize recursively on the tail, incrementing the source base (|c|).
(define (normalize c x) (let ((d (head x)) (e (head (tail x)))) (if (< (+ e 9) c) (cons-stream d (normalize (+ c 1) (tail x))) (carry c (cons-stream d (normalize (+ c 1) (tail x)))))))
(define (carry c x) (cons-stream (+ (head x) (quotient (head (tail x)) c)) (cons-stream (remainder (head (tail x)) c) (tail (tail x)))))
This primitive will be useful in extracting a digit from the stream. |(nth 10)| would return the 10th digit of e.
(define (nth digit) ((named-lambda (n d s) (if (= d 0) (head s) (n (-1+ d) (tail s)))) digit e))
Here we cheat a little. E should be represented as 1.111…, but we prefer the representation 0.2111…, although this violates our definition. This is why the source base starts at 2 in |convert|.
(define ones (cons-stream 1 ones)) (define e (convert (cons-stream 2 ones)))
And finally something useful...
(define (digits n) (map nth ((named-lambda (loop from to) (if (> from to) '() (cons from (loop (1+ from) to)))) 0 n)))
This code could be described as giving an infinite number of digits in an infinite number of time. What we would like to know is how much time is needed to compute n digits.
Let us suppose k digits are used in e. Then |convert| gets called
k times, calling itself |normalize| k times. The fact that a 0 gets
inserted in the stream in |convert| shows us that
k n/2.
Then the running time is O(n2).