home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 17870 < prev    next >
Encoding:
Internet Message Format  |  1993-01-08  |  3.1 KB
  1. Xref: sparky sci.math:17870 sci.math.num-analysis:3763
  2. Path: sparky!uunet!psinntp!kepler1!andrew
  3. From: andrew@rentec.com (Andrew Mullhaupt)
  4. Newsgroups: sci.math,sci.math.num-analysis
  5. Subject: Re: Approximating decimal fractions with proper fractions
  6. Keywords: fraction, approximation, number theory
  7. Message-ID: <1450@kepler1.rentec.com>
  8. Date: 8 Jan 93 22:40:51 GMT
  9. References: <C0ICCG.1BJ@hsi.com>
  10. Followup-To: sci.math
  11. Distribution: na
  12. Organization: Renaissance Technologies Corp., Setauket, NY.
  13. Lines: 77
  14.  
  15. In article <C0ICCG.1BJ@hsi.com> rogerh@code3 (Roger Harrison) writes:
  16. >I am looking for an algorithm (preferably a computationally cheap one)
  17. >to approximate a decimal fraction with a proper fraction for display 
  18. >purposes.  The ideal algorithm would take a decimal fraction and the 
  19. >maximum number of digits in the result's denominator to determine the 
  20. >proper fraction (in numerator/denominator form) which best approximates 
  21. >the original decimal fraction.
  22.  
  23.  
  24. I don't know what number theory books you looked in but any decent one
  25. should have done. What you are essentially looking for is the continued
  26. fraction, and it is usually computed by the Gauss transformation. You
  27. will find a discussion of this in Hardy and Wright's _Intro to Number Theory_
  28. and most other such texts, so I'll just sketch an example.
  29.  
  30.  
  31. Any real number x between 0 and 1 generates a 'continued fraction' of the
  32. following kind:
  33.  
  34.     x_0 = x;
  35.  
  36.     x_n-1 = (a_n + x_n)^-1; a_n positive integer, 0<x_n<1, for n>0.
  37.  
  38. If you do this with the fractional part of Euler's number (e-2) you get
  39. the sequence:
  40.  
  41.     a_1 = 1, a_2 = 2, a_3 = 1, a_4 = 1, a_5 = 4, ...
  42.  
  43. to make the pattern clear, you find that a_2 = 2, a_5 = 4, a_8 = 6, a_11 = 10,
  44. (i.e. a_(3k-1) = 2k) and a_n = 1 for n <> 3k-1.
  45.  
  46. You will have to be careful to evaluate e to lots of digits if you want to
  47. see the pattern clearly. The relevance of this sequence to your question is
  48. that we have the representation for e:
  49.  
  50.     e = 2 + 1/(1 + 1/(2 + 1/(1 + 1/(1 + 1/(4 + 1/(1 + ... ))))))
  51.  
  52. called a continued fraction. In the general case we write
  53.  
  54.     x = 1/(a_1 + 1/(a_2 + 1/(a_3 + ... )))
  55.  
  56. which is often abbreviated as:
  57.  
  58.     x = [a_1, a_2, a_3, ... ]
  59.  
  60. in our particular case:
  61.  
  62.     e = 2 + [1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12,1,...]
  63.  
  64.  
  65. Now if you start with a rational x, the continued fraction will terminate,
  66. and it is pretty clear that a terminating continued fraction must be rational.
  67. What isn't obvious, but the number theory books will spell out for you is
  68. that if you truncate a continued fraction, you get a rational approximation
  69. to x which is the best in a well defined sense. By successive truncations
  70. you get a sequence of approximating rationals, for example:
  71.  
  72.     e_1 = 2 + [1] = 3
  73.  
  74.     e_2 = 2 + [1,2] = 8/3 ~ 2.66667
  75.  
  76.     e_3 = 2 + [1,2,1] = 11/4 = 2.75
  77.  
  78.     e_4 = 2 + [1,2,1,1] =  19/7 ~ 2.714285
  79.  
  80.     e_5 = 2 + [1,2,1,1,4] = 87/32 ~ 2.71875
  81.  
  82. and these are clearly tending to e = 2.7182818....
  83.  
  84. So in order to find a good (in some sense best) approximation to a decimal
  85. number, work out the continued fraction and truncate it.
  86.  
  87. This is also the way to work out things like the minimum number of at bats
  88. you need to have a .327 batting average, etc.
  89.  
  90. Later,
  91. Andrew Mullhaupt
  92.