Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If we have two fractions $a = { a_1 \over a_2} $ and $c = {c_1 \over c_2}$ with $a<c$,

how to find the fraction

$b = { b_1 \over b_2 }$ , $a < b < c$

for which some measure of simpleness like

$b_1^2+b_2^2$

is minimal, without trying every possible fraction?

share|improve this question
    
Is $b_1^2 + b_2^2$ just an example? The exact measure might matter... –  Aryabhata Mar 2 '12 at 9:04
1  
Why not ((a1/a2)+(c1/c2))/2. I guess it depends a lot on the measure as Aryabhata stated. –  utdiscant Mar 2 '12 at 10:08
    
Are $a_1/a_2$ and $c_1/c_2$ necessarily in simplest terms? –  user22805 Mar 2 '12 at 10:37
    
We came to this general question while writing a fraction library in python to play with root finding. We used c=(a+b)/2 to narrow the interval, but this will never find exact roots of natural numbers. $b_1^2+b_2^2$ is just a suggestion. We will need some time to understand the answers. –  toka Mar 2 '12 at 11:44
    
See also this post on continued fraction comparison. –  Bill Dubuque Mar 3 '12 at 23:30
show 1 more comment

3 Answers 3

up vote 6 down vote accepted

I'll suppose both fractions are positive; if their signs differ take $\frac01$ as intermediate fraction and both negative is simlar to both positive. The absolutely simplest fraction in the interval $(a,c)$ (in the sense that both its numerator and its denominator are the smallest possible in the interval, so it doesn't much matter how you weigh each of them) is found in terms of the position of $a$ and $b$ in the Stern-Brocot tree. Let $d$ be the closest common ancestor of $a$ and $c$ (I'll consider $0$ to be the root of the tree, so in case $a=0$ one gets $d=0$). If $d\notin\{a,c\}$ then $d$ is the simplest fraction between $a$ and $c$; it is in fact like all positive fractions the simplest fraction in all the open interval between its left and right "direct ancestors" in the tree; here the parent of a fraction $\alpha$ is one direct ancestor of $\alpha$, and its other direct ancestor is found by going up from the parent to the first ancestor which is in the opposite direction as the parent was from $\alpha$ (for positive integers the right parent is taken to be $\infty$). This interval contains both $a$ (as a left descendant of $d$) and $c$ (a right descendent of $d$).

The situation is somewhat more complicated if $d\in\{a,c\}$, in other words if one of the fractions is an ancestor of the other (since you question forbids taking $b=a$ or $b=c$). Set $\{d,e\}=\{a,c\}$, so $e$ is the one of $a,c$ that is unequal to $d$. If $d$ is not one of the two direct ancestors of $e$, then some fraction on the path from $d$ to $e$ in the tree lies in the interval $(a,c)$, and the first such fraction gives your $b$. It is in fact found by taking one step down from $d$ in the direction of $e$, then zero or more steps in the opposite direction, stopping just before the next step that would again be in the direction from $d$ to $e$.

Finally there remains the case that $d$ is one of the two direct ancestors of $e$. This is the only case where one needs to go below $e$ in the tree; in fact one step down from $e$ in the direction of $d$ (left or right, but not up of course) will give the fraction $b$ sought. In fact $b=\frac{a_1+c_1}{a_2+c_2}$ in this case.

Here are exemples of the three cases:

  • $a=\frac47$, $c=\frac34$, $d=\frac23= b$ the closest common ancestor
  • $a=\frac34$, $c=\frac{58}{75}$, $d=a=\frac34$ is an ancestor of $c=\frac{58}{75}=e$ but not one of its direct ancestors $(\frac{17}{22},\frac{41}{53})$; one finds $b$ by descending $\frac34$ left $\frac45$ right $\frac79$ right $\frac{10}{13}=b$ left ...
  • $a=\frac34$, $c=\frac{10}{13}$, now $d=a$ is a direct ancestor of $c=e$, so one needs to descend from $e$ to the left (since $d\lt e$) giving $b=\frac{13}{17}=\frac{3+10}{4+13}$

Descending in the Stern-Brocot tree is easy if one knows the direct ancestors of the current fraction: add to numerator and denominaotor separately the numerator respectively denominator of the direct ancestor in the direction one is going to. Going up is harder (since in is not reasonable to suppose one knows the direct ancestors in this case), but performing the Euclidean algorithm to the pair (numerator,denominator) using subtractions, keeping track of the side from which the subtraction is performed, will give the successive directions to take from the top at $\frac11$ down to find the given fraction in the tree; this reveals all its ancestors. For instance for $\frac{58}{75}$ the Eucliedan algorithm steps $(58,75)$ left $(58,17)$ right $(41,17)$ right $(24,17)$ right $(7,17)$ left $(7,10)$ left $(7,3)$ right $(4,3)$ right $(1,3)$ left $(2,1)$ left $(1,1)$ tell you that you can find $\frac{58}{75}$ by descending in the tree by $\frac11$ left $\frac12$ right $\frac23$ right $\frac34$ right $\frac45$ left $\frac79$ left $\frac{10}{13}$ right $\frac{17}{22}$ right $\frac{24}{31}$ left $\frac{41}{53}$ left $\frac{58}{75}$.

To find the closest common ancestor between two fractions, apply this Euclidean algorithm in parallel for the two, up to the first point where the two require operations in different directions; descending from $\frac11$ to that point reveals the closest common ancestor. For instance for the first example, the fractions are $\frac47$ and $\frac34$, so one performs in parallel

  • $(4,7)$ left $(4,3)$ right $(1,3)$ left $(1,2)$
  • $(3,4)$ left $(3,1)$ right $(2,1)$ right $(1,1)$

The common path is left,right then they diverge, so one performs $\frac11$ left $\frac12$ right $\frac23=d$ to find the closest common ancestor $d$.

share|improve this answer
    
Do I understand right: we will find b by searching for the first number in the intervall [a,b] which can be reached walking down the Stern-Brocot Tree starting with $1 \over 1$. The distance walked would be "a best fit" for the "simpleness" of a fraction. –  toka Mar 2 '12 at 11:57
    
Yes, walking down the tree in the direction of both $a$ and $c$ the first fraction found inside $(a,c)$ is your common ancestor (and at this points the two paths separate). I don't understand the "best fit" part, it's just the simplest fraction in the interval in any reasonable measure. I'll add some detail for the conputation of the common ancestor. –  Marc van Leeuwen Mar 2 '12 at 13:05
add comment

Just sticking to positive integers and with fractions in lowest terms,

I think you only need to check each possible $b_2$ up to $\max(a_2,c_2)$ whether $\lfloor (b_2 a_1+a_2)/a_2 \rfloor \times c_2 \lt b_2 \times c_1$ and if so $b_1 = \lfloor (b_2 a_1+a_2)/a_2 \rfloor$.

If not then the theory underlying Stern-Brocot trees suggests to me you will need the mediant with $b_1=a_1+c_1$ and $b_2=a_2+c_2$.

share|improve this answer
add comment

A fairly simple procedure is to expand both $a_1/a_2$ and $b_1/b_2$ as continued fractions, and then take the part of the continued fraction expansion that agree between them, and put a terminating denominator that is one more than the smallest of the two first disagreeing elements. (*)

Then convert the resulting continued fraction back to an ordinary fraction. The result ought to be (if I remember correctly) the fraction in $(\frac{a_1}{a_2},\frac{b_1}{b_2})$ that has the smallest denominator.

*) with some special cases if the disagreement comes right at the end of one or both of the continued fractions.

share|improve this answer
    
See also this post on continued fraction comparison. –  Bill Dubuque Mar 3 '12 at 23:30
    
Indeed, see: en.wikipedia.org/wiki/… –  ShreevatsaR Nov 8 '12 at 10:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.