My Math Forum Rational approximation algorithm

 Elementary Math Fractions, Percentages, Word Problems, Equations, Inequations, Factorization, Expansion

 October 2nd, 2011, 12:47 PM #1 Newbie   Joined: Oct 2011 Posts: 1 Thanks: 0 Rational approximation algorithm I'm attempting to write a little program to take a fraction and generate the closest approximate fraction with terms below some limit. Such a tool would come in handy at work for doing arithmetic on small 8-bit processors, but mostly it's a fun exercise. I have a vague recollection from some long forgotten lecture or textbook concerning a theorem about the "midpoint" fraction. E.g. given two irreducible fractions $\frac{a}{b} < \frac{c}{d}$ then $\frac{p}{q}= \frac{a+c}{b+d}$ are the smallest terms where $\frac{a}{b} < \frac{p}{q} < \frac{c}{d}$, or something along those lines. This would then give me a natural method for finding successively better approximations by first normalizing the sought-after number $0 \leq x \leq 1$ and starting with the lower bound $\frac{a}{b}= \frac{0}{1}$ and upper bound $\frac{c}{d}= \frac{1}{1}$. Then proceed through divide-and-conquer to home in on $x$ by successively replacing either the lower bound $\frac{a'}{b'} = \frac{a + c}{b + d}$ if $x > \frac{a + c}{b + d}$ or the upper bound $\frac{c'}{d'} = \frac{a + c}{b + d}$ if $x < \frac{a + c}{b + d}$ until the term limit is reached. My only trouble is that I can't seem to remember what the theorem is called or precisely what it states and (more embarrasingly) I haven't been able to prove it to myself. Am I on the right track here?
 October 12th, 2011, 06:31 PM #2 Newbie   Joined: Oct 2011 Posts: 12 Thanks: 0 Re: Rational approximation algorithm I think you may have posted this in the wrong section.

### rational approximation algorithm

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post kyry Calculus 2 January 31st, 2014 09:47 PM Shamieh Calculus 1 October 9th, 2013 10:09 AM Anton29 Applied Math 5 December 28th, 2011 01:11 PM omegapoint Applied Math 2 December 22nd, 2010 04:57 AM Marcel777 Number Theory 5 September 27th, 2010 11:49 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top