Hello,

2010/1/8 Daniel Moore said:

This week=92s quiz is to write a Ruby program that can compute the first

100,000 digits of e.

Have fun!

Well I had

)

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 =3D [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) =3D

\Sum{n=3D0}{\infty} x^n/n! applied in x=3D1 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

).

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 =3D Time.now

precision =3D (ARGV[0] || 1000).to_i

iterations =3D precision /(log10(precision)) +

precision/(log10(precision))*log10(log10(precision))

puts 'Approximate number of iterations needed: ' + iterations.to_i.to_s

accuracy =3D 10**precision.to_i

fact =3D 1

final =3D accuracy

other =3D false

d =3D [d1]

1.upto(iterations) do |i|

if i%100 =3D=3D 0

d << Time.now

puts i.to_s + " needing #{d[-1] - d[-2]} s"

end

fact *=3D i

final_old =3D final

final +=3D Rational(accuracy,fact)

end

d2 =3D 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 =3D 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 =3D 1 ; (1..34_000).inject(1) {|sum,i| fact *=3D 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,

--=20

JJ Fleck

PCSI1 Lyc=E9e Kl=E9ber