Newsgroups: sci.math From: frb6006@cs.rit.edu (Frank R Bernhart) Subject: Re: More fractions Date: Fri, 1 Mar 1996 13:43:49 GMT Kami Rousseau wrote: : >I need to find a way the find the simplest fraction between two given : >real numbers. What I mean by simplest is the fraction that uses the : >smallest numbers. I have seen several answers to this. I am surprised that no one has described the procedure related to continued fractions and Farey sequences. Suppose you specify two real numbers r < s and desire a fraction p/q between them, as simple as possible. One shd. be able to set whole numbers n,m so that n < r < s < m. Of course, the smallest whole number between r,s, if it exists, should be the answer, including endpoints r,s if either is integer. So we assume m= n+1. Set two fraction variables a/b := n/1, c/d := (n+1)/1. Now form the _mediant_ p/q = (a+c)/(b+d). If r < p/q < s, then p/q is the answer you want. If p/q = r or p/q = s, still the best, but of course you are free to make the quest-ion rule this out. If p/q < r, then redefine a/b := p/q, and similarly if s < p/q, redefine c/d = p/q. Here p/q is always in lowest terms, and a/b,c/d squeeze together, hence with repetition, you will find answer between r,s. Frank R. Bernhart - lower City^ ============================================================================== Newsgroups: sci.math From: rjohnson@apple.com (Robert Johnson) Subject: Re: More fractions Date: Fri, 1 Mar 1996 11:13:31 GMT In article <3134D543.4BD6@login.net>, Kami Rousseau wrote: >I need to find a way the find the simplest fraction between two given >real numbers. What I mean by simplest is the fraction that uses the >smallest numbers. First, generate the continued fractions for the two real numbers. To generate the continued fraction for a real number r, or to reconstruct a rational number from its continued fraction, use this algorithm: Initialize: r = r 0 a = 0, a = 1 -2 -1 b = 1, b = 0 -2 -1 Iterate: c = int(r ) ]- generate continued fraction k k a = c a + a -+ k k k-1 k-2 | +- reconstruct rational number b = c b + b | k k k-1 k-2 -+ Terminate if r_k = c_k, otherwise continue: r = 1/(r - c ) ]- compute next remainder k+1 k k Remarks: The sequence { c_k } is a shorthand for the continued fraction for r. It stands for c_0 + 1/(c_1 + 1/(c_2 + 1/(c_3 + ...))). The sequence { a_k/b_k } converges to r. When comparing continued fractions, there are 3 cases: Case 1: If the first differing term is the final term of one of the sequences and that final term is 1 greater than the corresponding term in the other sequence, subtract 1 from that final term and append a 1 to its sequence. The sequences now match further; start again. Case 2: If the continued fractions match until one terminates, find the term in the longer sequence that matches the final term in the shorter sequence. Add 1 to the next term and truncate its sequence. This is the answer. Case 3: If neither case 1 nor case 2 apply, find the first differing term and add 1 to the smaller term and truncate its sequence. This is the answer. Example 1: 4/3 = 1,3 7/5 = 1,2,2 Case 1 applies, so we alter the first sequence: 4/3 = 1,2,1 7/5 = 1,2,2 Case 1 applies again, so we alter the second sequence: 4/3 = 1,2,1 7/5 = 1,2,1,1 Case 2 applies, so the answer is 1,2,1,2 = 11/8 Example 2: 1.48438468 = 1,2,15,... 1.54385785 = 1,1,1,... Case 3 applies, so the answer is 1,2 = 3/2 Example 3: 1.8 = 1,1,4 2.1 = 2,10 Case 3 applies, so the answer is 2 = 2/1 Example 4: pi = 3,7,15,1,292,1,1,1,2,1,3,1,14,... 22/7 = 3,7 Case 2 applies, so the answer is 3,7,16 = 355/113 Example 5: pi = 3,7,15,1,292,1,1,1,2,1,3,1,14,... 355/113 = 3,7,16 Case 1 applies, so we alter the second sequence: pi = 3,7,15,1,292,1,1,1,2,1,3,1,14,... 355/113 = 3,7,15,1 Case 2 applies, so the answer is 3,7,15,1,293 = 104348/33215 This is another reason why 355/113 is such a good approximation to pi; all rational numbers between pi and 355/113 have denominator at least 33215. Rob Johnson Apple Computer, Inc. rjohnson@apple.com