From: William Rutiser <wruyahoo05@...>
Date: 2010-01-14T06:56:56+09:00
Subject: 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}"