Digits Of E

June 19, 2012

  modulus 2 3 4 5 6 7 8 9 10 11
   
2 initialization 1 1 1 1 1 1 1 1 1 1
   
  times ten 10 10 10 10 10 10 10 10 10 10
  carry 4 3 2 1 1 1 1 1 0
  sum 14 13 12 11 11 11 11 11 10 10
7 quotient 7 4 3 2 1 1 1 1 1 0
  remainder 0 1 0 1 5 4 3 2 0 10
   
  times ten 0 10 0 10 50 40 30 20 0 100
  carry 3 0 3 9 6 4 2 0 9
  sum 3 10 3 19 56 44 32 20 9 100
1 quotient 1 3 0 3 9 6 4 2 0 9
  remainder 1 1 3 4 2 2 0 2 9 1
   
  times ten 10 10 30 40 20 20 0 20 90 10
  carry 6 9 8 3 2 0 3 9 0
  sum 16 19 38 43 22 20 3 29 90 10
8 quotient 8 6 9 8 3 2 0 3 9 0
  remainder 0 1 2 3 4 6 3 2 0 10
   
  times ten 0 10 20 30 40 60 30 20 0 100
  carry 5 6 7 8 9 4 2 0 9
  sum 5 16 27 38 49 64 32 20 9 100
2 quotient 2 5 6 7 8 9 4 2 0 9
  remainder 1 1 3 3 1 1 0 2 9 1
   
  times ten 10 10 30 30 10 10 0 20 90 10
  carry 6 9 6 1 1 0 3 9 0
  sum 16 19 36 31 11 10 3 29 90 10
8 quotient 8 6 9 6 1 1 0 3 9 0
  remainder 0 1 0 1 5 3 3 2 0 10
   
  times ten 0 10 0 10 50 30 30 20 0 100
  carry 3 0 3 9 4 4 2 0 9
  sum 3 10 3 19 54 34 32 20 9 100
1 quotient 1 3 0 3 9 4 4 2 0 9
  remainder 1 1 3 4 0 6 0 2 9 1
   
  times ten 10 10 30 40 0 60 0 20 90 10
  carry 6 9 8 1 8 0 3 9 0
  sum 16 19 38 41 8 60 3 29 90 10
8 quotient 8 6 9 8 1 8 0 3 9 0
  remainder 0 1 2 1 2 4 3 2 0 10
   
  times ten 0 10 20 10 20 40 30 20 0 100
  carry 5 5 2 4 6 4 2 0 9
  sum 5 15 22 14 26 44 32 20 9 100
2 quotient 2 5 5 2 4 6 4 2 0 9
  remainder 1 0 2 4 2 2 0 2 9 1
   
  times ten 10 0 20 40 20 20 0 20 90 10
  carry 2 7 8 3 2 0 3 9 0
  sum 12 7 28 43 22 20 3 29 90 10
6 quotient 6 2 7 8 3 2 0 3 9 0
  remainder 0 1 0 3 4 6 3 2 0 10
About these ads

Pages: 1 2 3

6 Responses to “Digits Of E”

  1. […] today’s Programming Praxis exercise, our goal is to implement two algorithms to calculate the digits of e […]

  2. Here’s my Haskell solution for the first algorithm (since my solution for the second one has already been posted in the exercise). A version with comments can be found at http://bonsaicode.wordpress.com/2012/06/19/programming-praxis-digits-of-e/ .

    import Data.List
    
    spigot_e :: Int -> [Int]
    spigot_e n = 2 : take (n - 1) (f $ replicate (n + 1) 1) where
        f = (\(d,xs) -> d : f xs) .
            mapAccumR (\a (i,x) -> divMod (10*x+a) i) 0 . zip [2..]
    
  3. […] First we reuse the unbounded spigot algorithm for calculating e from the last exercise; […]

  4. Miracle said

    Does anybody share a Java or C# code for this exercises?

  5. Mike said

    Basically a direct translation of the haskell code into Python 2.7. I create the input stream and initialize the state vector (z) in ‘stream()’ and eliminated ‘streamDigits()’.

    
    from itertools import count, imap
    
    def stream(lo, hi, f):
        def approx((a,b,c), n): return (a*n + b)//c
        def mul((a,b,c),(d,e,f)): return a*d, a*e + b*f, c*f
        
        xs = ((n, a*d, d) for n,d,a in imap(f, count(1)))
        z = 1, 0, 1
        while True:
            lbound = approx(z, lo)
            if lbound == approx(z, hi):
                yield lbound
                z = mul((10, -10*lbound, 1), z)
    
            else:
                z = mul(z, next(xs))
    
    			
    def pi_digits():
        return stream(3, 4, lambda k: (k, 2*k + 1, 2))
    
    def e_digits():
        return stream(1, 2, lambda k: (1, k, 1))
    
    # test
    from itertools import islice
    
    print ''.join(str(d) for d in islice(pi_digits, 10))   # returns "3141592653"
    print ''.join(imap(str, islice(e_digits, 14)))         # returns "27182818284590"
    
    
  6. David said

    Here is FORTH code for the first algorithm (by Stan & Stanley) Though space is proportional to n, not sure why you mention n**2.

    100 constant #digits
    : int-array  create cells allot  does> swap cells + ;
    
    #digits 1+ int-array e-digits[]
    
    : init-e ( -- )
       [ #digits 1+ ] literal 0 DO
          1  i e-digits[]  !
       LOOP
       cr ." 2." ;
    
    : .e  ( -- )
       init-e
       [ #digits 1- ] literal 0 DO
          0  \ carry
          0 #digits DO
             i e-digits[] dup @  10 *  rot +  i 2 + /mod -rot  swap !
          -1 +LOOP
          0 .r
       LOOP ;
    
    .e
    2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427 ok
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: