Forum: Ruby Digits of e (#226)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
33117162fff8a9cf50544a604f60c045?d=identicon&s=25 Daniel X Moore (yahivin)
on 2010-01-08 06:27
(Received via mailing list)
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have elapsed from the time this message was
sent.

2.  Support Ruby Quiz by submitting ideas and responses
as often as you can.

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk follow the discussion.  Please reply to
the original quiz message, if you can.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

RSS Feed: http://rubyquiz.strd6.com/quizzes.rss

Suggestions?: http://rubyquiz.strd6.com/suggestions

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

## Digits of e (#226)

Wayumbe Rubyists,

The mathematical constant e is the unique real number such that the
value of the derivative (slope of the tangent line) of the function
f(x) = e^x at the point x = 0 is exactly 1. The function e^x so
defined is called the exponential function, and its inverse is the
natural logarithm, or logarithm to base e.[1]

e is one of the most important numbers in mathematics, alongside the
additive and multiplicative identities 0 and 1, the constant ð, and
the imaginary unit i. These are the five constants appearing in one
formulation of [Euler's identity][2].

This week¢s quiz is to write a Ruby program that can compute the first
100,000 digits of e.

Have fun!

[1]: http://en.wikipedia.org/wiki/E_(mathematical_constant)
[2]: http://en.wikipedia.org/wiki/Euler's_identity
Ff413dd3f90e6f605a6a35e417299b6a?d=identicon&s=25 Jack Rouse (Guest)
on 2010-01-10 17:51
(Received via mailing list)
Daniel Moore wrote:
> This week¢s quiz is to write a Ruby program that can compute the first
> 100,000 digits of e.
>
> Have fun!
>
> [1]: http://en.wikipedia.org/wiki/E_(mathematical_constant)
> [2]: http://en.wikipedia.org/wiki/Euler's_identity

I used the fast converging continued fraction series from the first
Wikipedia article:

# compute e*10**digits as a rounded integer
def calc_e(digits)
   limit = 10**((digits+3)/2)
   p = [2, 3]
   q = [2, 1]
   n = 1
   begin
     if p.length.even?
       a = 4*(4*n-1)
     else
       a = 4*n+1
       n += 1
     end
     p << a*p[-1] + p[-2]
     q << a*q[-1] + q[-2]
   end while p.last <= limit
   (p.last*10**(digits+3)/q.last+500)/1000
end

if __FILE__ == $0
   p calc_e(if ARGV.length.zero? then 100_000 else Integer(ARGV[0]) end)
end
7838393e522d4b6daf208ee3c30ff2e9?d=identicon&s=25 Jean-Julien Fleck (Guest)
on 2010-01-10 18:33
(Received via mailing list)
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,
D91f9adf63acfa73b50ebab43f10d7ee?d=identicon&s=25 Thorsten Hater (Guest)
on 2010-01-11 14:58
(Received via mailing list)
Hello,

based on the spigot algorithm of Rabonitz and Wagon [1]:

#!/usr/bin/ruby

def spigot n
   e = []
   arr = [2] + Array.new(n+1,1)
   (n-1).times do |i|
     (n+1).downto 0 do |j|
       arr[j] *= 10
     end
     q = 0
     (n+1).downto 0 do |j|
       arr[j] += q
       q = arr[j]/(j+1)
       arr[j] %= j+1
     end
     e << q
   end
   e[0]/= 10.0
   puts e.join('')
end

if $0 == __FILE__
   spigot ARGV[0].to_i
end

[1] http://www.mathpropress.com/stan/bibliography/spigot.pdf : citing
the easier case of e

Am 08.01.2010 06:26, schrieb Daniel Moore:
D91f9adf63acfa73b50ebab43f10d7ee?d=identicon&s=25 Thorsten Hater (Guest)
on 2010-01-11 15:00
(Received via mailing list)
Sorry, Rabonitz meant Rabinowitz, ugly typo.

Am 11.01.2010 14:57, schrieb Thorsten Hater:
C38efb262ff32d9599c4935507ae5cf7?d=identicon&s=25 William Rutiser (Guest)
on 2010-01-13 22:59
(Received via mailing list)
After recovering some vaguely remembered math, and trying not to look to
closely at any code
on the net, here is my solution.

The reference data for testing, from Project Gutenberg, has been
truncated for
this posting. The program will report "Incorrect" for more than a couple
of hundred digits.

Bill Rutiser
wrutiser AT gmail DOT com

# Produce digits of e
# wrutiser AT gmail DOT com

#
# The Loop Invariant requires the following conceptual numbers to sum to
_e_.
#   (1) The number represented by the decimal digits previously
generated.
#
#   (2) An intermediate fraction having the value of the sum of several
#   terms taken from the infinite series expansion that have yet to be
#   included in (1)
#
#   (3) The tail of the infinite series expansion.
#
# The generated digits are contained in the variable _z_ but are not
used
# in the generation of the subsequent bits.
#
# The current term of the infinite series is represented by the variable
_i_.
# The term itself, given by the expression "1/factorial( i )", is never
actually
# computed.
#
# The sum of the intermediate terms is represented by the variables
_nn_,
# _dd_, and _mm_. While the sum itself is never actually computed, it is
# equivalent to the expression "nn / (mm * dd)".
#
# _mm_ is a power of 10, increasing as each digit is extracted.
# _dd_ is maintained equal to factorial( i ).
#
# _nn_ is the numerator of the conceptional rational number.
#
# Each loop interation:
#   removes the first remaining term from the series
#
#   adds the removed term to the intermediate fraction
#
#   computes the leading two digits of the fraction
#
#   if these digits are the same as those computed for the
#   previous term, one digit is extracted.
#

def digits_int( n_terms )

  nn = 0
  dd = 1
  mm = 1

  q1 = -1

  z = "2.\n"
  digits = 0

  2.upto(n_terms) do |i|

    dd *= i
    nn *= i
    nn += mm

    q2, r2 = (nn * 100).divmod( dd )

    if( q1 == q2 )
      q, r = (nn * 10).divmod( dd )
      z << q.to_s

      digits += 1
      z << " " if 0 == digits % 10
      z << "\n" if 0 == digits % 50

      mm *= 10
      nn = r
      q1 = -1
    else
      q1 = q2
    end
  end

  puts( "\ndigits: #{digits}  n_terms: #{n_terms}" \
        "  terms/digit: #{Float(n_terms) /digits}" )
  puts( "dd.size: #{dd.size}   nn.size: #{nn.size}" )
  puts z

  if compare?( $gutenberg_digits, z )
    puts "Correct!!"
  else
    puts "Not correct."
  end
end

def compare?( ssx, ssy )
  sx = ssx.delete( " \n" )
  sy = ssy.delete( " \n" )
  sx.start_with?( sy )
end

# Digits from http://www.gutenberg.org/files/127/127.txt
<http://www.gutenberg.org/files/127/127.txt>
# Computed by Robert Nemiroff and Jerry Bonnell.
# See the file itself for details, license, copyrights, etc.

$gutenberg_digits = <<HERE
  2.
7182818284590452353602874713526624977572470936999595749669676277240766303535
47594571382178525166427427466391932003059921817413596629043572900334295260595630
73813232862794349076323382988075319525101901157383418793070215408914993488416750
 #### thousands of digits removed from email posting ####
HERE

$gutenberg_digits = $gutenberg_digits.delete( " \n" )
puts "gutenberg_digits.length: #{$gutenberg_digits.length}"
0ea7f61aec8fee539be0cf39b7bab77c?d=identicon&s=25 Benoit Daloze (Guest)
on 2010-01-14 18:46
(Received via mailing list)
Attachment: e.rb (2 KB)
Hello,

2010/1/8 Daniel Moore <yahivin@gmail.com>

>
> Suggestions?: http://rubyquiz.strd6.com/suggestions
> defined is called the exponential function, and its inverse is the
> Have fun!
>
> [1]: 
http://en.wikipedia.org/wiki/E_(mathematical_const...
> [2]: 
http://en.wikipedia.org/wiki/Euler's_identity<http...
>
> --
> -Daniel
> http://rubyquiz.strd6.com
>
>
I got some fun playing with computing e. I didn't get any formal
solution
(it definitely takes too long ...)

So, e.rb contains 8 basic methods to compute e, using basic Float of
ruby(so
don't exepect to get a ot of precision).

Anyway, we can see the continuous fraction is good, and it's the only
one
who worked easily with BigDecimal(I got only 113 digits, shame on me
...).

Here is the output of e.rb
-------------------------------------------------------
2.718281828459045

lim(n->∞) (1+1/n)**n with n = 100000000
2.7182817983473577
3.011168736577474e-08

lim(n->0) (1+n)**(1/n) with n = 1.0e-08
2.7182817983473577
3.011168736577474e-08

Σ(n=0,∞) 1/n! with n = 17
2.7182818284590455
-4.440892098500626e-16

lim(n->∞) n/(√(n,n!)) with n : 170
2.663087878748024
0.055193949711020984

[[2;1,2,1,1,4,1,1,6,1,1,8,1,1,...,2n,1,1,...]] with 23 numbers
2.718281828459045
0.0

[[1,0,1,1,2,1,1,4,1,1,6,1,1,8,1,1,...]] with 25 numbers
2.718281828459045
0.0

[[1,0.5,12,5,28,9,44,13,60,17,...,4(4n-1),4n+1,...]] with 10 numbers
2.718281828459045
0.0

Global maximum of f(x) = √(x,x) with p = 16
2.7182818284590446
4.440892098500626e-16
-------------------------------------------------------

And I got also a strange thing. I saw somewhere it's possible to compute
e
with lim(n->inf) ((2n+1)/(2n-1))**n, but changing the limit to 0 gives π
(hum, the complex part of the result, divided by n), awesome :D (or this
is
surprising me at least :) )

include Math
p E # 2.718281828459045
puts

formula = -> n { ((2*n+1)/(2*n-1).to_f)**n }

puts "lim(n->inf) ((2n+1)/(2n-1))**n with n = #{n = 100_000}"
puts "e"
p e = formula[n] # 2.718281828493031
p e - E # 3.398570314061544e-11

puts "lim(n->0) ((2n+1)/(2n-1))**n with n = #{n = 1.0/100_000_000}"
puts "Ï€"
p pi = formula[n] # (1.0+3.141592653589794e-08i)
p pi = pi.imaginary / n # 3.1415926535897936
p pi - PI # 4.440892098500626e-16

Cheers,

B.D.
2fa5dcd1ca7a14b99a5ed1cc26787c63?d=identicon&s=25 Jay Anderson (horndude77)
on 2010-01-18 05:20
> ## Digits of e (#226)
>
> This week�s quiz is to write a Ruby program that can compute the first
> 100,000 digits of e.

$ cat e.rb
digits = 100000
fudge = 10
unity = 10**(digits + fudge)
e = unity
n = unity
i = 0
while (n>0)
  i += 1
  n /= i
  e += n
end
e /= 10**fudge
p e
$ time ruby e.rb > /dev/null

real  0m4.023s
user  0m3.940s
sys  0m0.087s

This uses the taylor series definition of e which actually converges
quite fast.

-----Jay
51031c23a5b18196d9527c6b366a6928?d=identicon&s=25 David Springer (dnspringer)
on 2010-03-09 00:11
I decided to work on an old quiz.
----------------------
> This week's quiz is to write a Ruby program that can compute the first
> 100,000 digits of e.

Here is what I came up with:
---------------------------------------------------------
PLACES = 100_000

euler = 0
big_one = 10**(PLACES+5)
nxt_one = big_one
n = 1

while (nxt_one != 0)
n += 1
nxt_one /= n
euler += nxt_one
end

puts "2."+euler.to_s[0..PLACES-1]
---------------------------------------------------------

It ended up looking a lot like Jay's solution.
753dcb78b3a3651127665da4bed3c782?d=identicon&s=25 Brian Candler (candlerb)
on 2010-03-09 10:59
51031c23a5b18196d9527c6b366a6928?d=identicon&s=25 David Springer (dnspringer)
on 2010-03-09 23:58
Math::E**Math::PI-Math::PI ### ;)
=> 19.9990999791895
33117162fff8a9cf50544a604f60c045?d=identicon&s=25 Daniel X Moore (yahivin)
on 2010-04-22 23:24
(Received via mailing list)
Attachment: 226.tar.gz (4 KB)
This quiz harkens back to another mathematically themed computation
competition Digits of Pi (#202)[1]. Many of the same techniques that can
be
applied to the computation of pi can be applied to the computation of e,
and
there are some surprising results.

Jack Rouse used the fast converging continued fraction series from
Wikipedia[2] to create a short program that quickly calculates e to
100_000
digits. Jack's solution is quite quick, yielding the output within
several
seconds.

Jean-Julien Fleck started with a benchmark of the the standard library
call
and estimated that it would take 10**5 seconds to compute the first
100_000
digits. Jean-Julien provides a handy one liner that can be used in irb:

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

This computation makes use of the Taylor series definition. The results
use
Rational, so can be quite slow, it is advised to start with a smaller
number
of iterations, possibly 500 or so.

Thorsten Hater created a program based on the spigot algorithm from
Rabonitz
and Wagon[3]. From the paper:

    > This algorithm is a "spigot" algorithm: it pumps out digits one
    > at a time and does not use the digits after they are computed
[...];
    > the entire algorithm uses only ordinary integer arithmetic on
    > relatively small integers.

The paper is actually about computing the digits of pi with the same
method,
but in doing so covers the case of e, which is simpler. An interesting
approach, and worth looking at if you are into mathematics.

Benoit Daloze explored eight different methods of computing e with a
focus
on breadth rather than depth. See them all in the attached solutions
supplement. Benoit also came across this interesting bit of information:

    lim(n->inf) ((2n+1)/(2n-1))**n    => e
    lim(n->0)   ((2n+1)/(2n-1))**n    => π

Jay Anderson and and David Springer used the Taylor series definition of
e,
which is quite fast at converging and delivering 100_000 digits. These
solutions are much faster that other Taylor series implementations
because
they use only integer arithmatic and a very simple loop.

Here is Jay Anderson's solution:

    digits = 100000
    fudge = 10
    unity = 10**(digits + fudge)

    e = unity
    n = unity
    i = 0

    while (n>0)
      i += 1
      n /= i
      e += n
    end

    e /= 10**fudge
    p e

Setting unity to be 10^digits shifts everything into the integers so
that
floating point math won't be required. The extra fudge factor ensures
that
there aren't rounding errors near the end. Each step of the loop
requires
only an increment, an integer division, and an addition. Notice how the
division in the loop accumulates the factorial, because the result of
1/2 is
stored when it is divided by 3 it is set equal to 1/3!. The loop
terminates
when the series term becomes 0, i.e. too small to add anything that will
matter within the chosen number of digits.

Thanks everyone for your solutions to the quiz!

[Digits of e (#226) - Solutions][4]

P.S. Brian Candler linked to an xkcd comic involving e and π[5], not all
contributions need to be code.

[1] http://rubyquiz.strd6.com/quizzes/202-digits-of-pi
[2] http://en.wikipedia.org/wiki/E_(mathematical_constant)
[3] http://www.mathpropress.com/stan/bibliography/spigot.pdf
[4] http://rubyquiz.strd6.com/quizzes/226.tar.gz
[5] http://xkcd.com/217/
This topic is locked and can not be replied to.