[QUIZ] Digits of e (#226)

Discussion in 'Ruby' started by Daniel Moore, Jan 8, 2010.

  1. Daniel Moore

    Daniel Moore Guest

    -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=
    =3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-

    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

    -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=
    =3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-

    ## 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) =3D e^x at the point x =3D 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 =F0, and
    the imaginary unit i. These are the five constants appearing in one
    formulation of [Euler's identity][2].

    This week=A2s 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

    --=20
    -Daniel
    http://rubyquiz.strd6.com
     
    Daniel Moore, Jan 8, 2010
    #1
    1. Advertising

  2. Daniel Moore

    Jack Rouse Guest

    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

    --
    Jack Rouse
     
    Jack Rouse, Jan 10, 2010
    #2
    1. Advertising

  3. Hello,

    2010/1/8 Daniel Moore <>:
    > 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 :eek:)
    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 :eek:).
    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
     
    Jean-Julien Fleck, Jan 10, 2010
    #3
  4. 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:
    > -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
    >
    > 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
    >
    >



    --
    Thorsten Hater
    Institut fuer Theoretische Physik I
    Ruhr-Universitaet Bochum
    E-Mail:
    Tel.: 0234/32-23-441
     
    Thorsten Hater, Jan 11, 2010
    #4
  5. Sorry, Rabonitz meant Rabinowitz, ugly typo.

    Am 11.01.2010 14:57, schrieb Thorsten Hater:
    > 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:
    >> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
    >>
    >> 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
    >>

    >
    >



    --
    Thorsten Hater
    Institut fuer Theoretische Physik I
    Ruhr-Universitaet Bochum
    E-Mail:
    Tel.: 0234/32-23-441
     
    Thorsten Hater, Jan 11, 2010
    #5
  6. Re: [QUIZ] Digits of e (#226) Late solution

    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}"
     
    William Rutiser, Jan 13, 2010
    #6
  7. Daniel Moore

    Jay Anderson Guest

    Re: Digits of e (#226)

    > ## 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
    --
    Posted via http://www.ruby-forum.com/.
     
    Jay Anderson, Jan 18, 2010
    #7
  8. Re: Digits of e (#226)

    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.
    --
    Posted via http://www.ruby-forum.com/.
     
    David Springer, Mar 8, 2010
    #8
  9. Brian Candler, Mar 9, 2010
    #9
  10. David Springer, Mar 9, 2010
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Brendan

    ftplib - 226 message not received

    Brendan, Jan 8, 2009, in forum: Python
    Replies:
    1
    Views:
    444
    Brendan
    Jan 8, 2009
  2. Gabriel Genellina

    Re: Python-list Digest, Vol 75, Issue 226

    Gabriel Genellina, Dec 22, 2009, in forum: Python
    Replies:
    3
    Views:
    248
  3. Ruby Quiz

    [QUIZ] Animal Quiz (#15)

    Ruby Quiz, Jan 14, 2005, in forum: Ruby
    Replies:
    11
    Views:
    427
    James Edward Gray II
    Jan 18, 2005
  4. David Tran
    Replies:
    9
    Views:
    247
    David Tran
    Jan 21, 2005
  5. Daniel Moore

    [QUIZ] Digits of Pi (#202)

    Daniel Moore, Apr 24, 2009, in forum: Ruby
    Replies:
    19
    Views:
    302
    Daniel Moore
    May 3, 2009
Loading...

Share This Page