From: Jean-Julien Fleck <jeanjulien.fleck@...>
Date: 2010-01-11T02:32:32+09:00
Subject: Re: [QUIZ] Digits of e (#226)

Hello,

2010/1/8 Daniel Moore <yahivin@gmail.com>:
> This week’s quiz is to write a Ruby program that can compute the first
> 100,000 digits of e.
>
> Have fun!

Well I had :o)
I got inspired from Quiz Digits of Pi (#202) and tried to estimate how
long the standard library call could take (I didn't want to waste too
much CPU on this):

   require 'bigdecimal'
   require 'bigdecimal/math'
   include Math
   include BigMath

   d = [Time.now]

   1000.step(20000,1000) do |i|
     E(i)
     d << Time.now
     puts i.to_s + " needing #{d[-1] - d[-2]} s"
   end

which gives

1000 needing 0.147869 s
2000 needing 0.956326 s
3000 needing 2.993516 s
4000 needing 6.738271 s
5000 needing 12.78967 s
6000 needing 21.584826 s
7000 needing 34.154156 s
8000 needing 49.223259 s
9000 needing 69.57902 s
10000 needing 94.507271 s
11000 needing 123.327777 s
12000 needing 158.839553 s
13000 needing 198.976605 s
14000 needing 246.62736 s
15000 needing 300.471167 s
16000 needing 364.013845 s
^C

almost scaling as the cube of the digit number you ask for. So that it
should take around 10**5 s to compute E(100_000).

I then tried my own implementation using the definition exp(x) =
\Sum{n=0}{\infty} x^n/n! applied in x=1 and checking from E(number)
that it was correct. It's converging pretty fast (in term of iteration
number, only 34_000 to get 100_000 digits) but it's quite exactly 10
times slower than the standard method (and I didn't want to wait 10**6
s to get all the 100_000 digits :o).
The needed number of iterations is guessed using Stirling formula and
I discovered that each step does not take the same time (it gets
slower as time goes) whereas it does not depend on the initial number
of digits asked for (that is the 1000 first iterations take
approximately the same time when you ask for 10_000 digits or for
100_000 digits) which I couldn't really understand. I first thought
that the slowing-down was due to the fact that for more digits you
need bigger integers to play with but the latter observations seems to
invalidate this argument.. If anybody have an explanation, I will be
happy to hear it.

   require 'rational'
   require 'enumerator'
   require 'bigdecimal'
   require 'bigdecimal/math'
   include Math
   include BigMath

   d1 = Time.now
   precision = (ARGV[0] || 1000).to_i
   iterations = precision /(log10(precision)) +
                precision/(log10(precision))*log10(log10(precision))
   puts 'Approximate number of iterations needed: ' + iterations.to_i.to_s
   accuracy = 10**precision.to_i
   fact = 1
   final = accuracy
   other = false
   d = [d1]

   1.upto(iterations) do |i|
     if i%100 == 0
       d << Time.now
       puts i.to_s + " needing #{d[-1] - d[-2]} s"
     end
     fact *= i
     final_old = final
     final += Rational(accuracy,fact)
   end

   d2 = Time.now
   puts "Time elapsed in computation: " + (d2 - d1).to_s + ' s'
   puts "Computation terminated: computing E(#{precision}) now."
   puts "Delta * 10**(#{precision}): " + (final.round -
E(precision)*accuracy).to_s
   d3 = Time.now
   puts "Time elapsed calling E(#{precision}): " + (d3 - d2).to_s + ' s'


Last but not least, the same method could be called as one line in irb
using inject and getting the result in the form of a Rational:

fact = 1 ; (1..34_000).inject(1) {|sum,i| fact *= i ; sum + Rational(1,fact)}

but you will rather want to try with a smaller number of steps (say
500 to get 1000 digits, remember: 34_000 steps will take around 10**6
s...)

Cheers,

-- 
JJ Fleck
PCSI1 Lycée Kléber