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