Looking for something related to continued fractions but with a very different "algorithm" I once saw in a book

91 Views Asked by At

Years ago I saw a calculation technique that would with each iteration yield the next best fractional approximation of a decimal number. I was intrigued at the time, and have several times in the years since tried to find what book that was in (I thought it was in a book I owned, but can't find it now,) and I have searched several times on the Internet, and read many sites and watched videos about "continued fractions" but have never seen anything that looked like that technique.

I have certainly learned a lot about continued fractions and find them interesting, but the technique I am looking for looked very different, and did not yield the usual bracketed list of integers, but rather a series of plain looking fractions, each one a closer approximation than the previous. You could stop when the fraction was accurate enough and not to hard to remember.

If I recall correctly, you start with a decimal number and wrote the first fraction approximation, then with a bit of arithmetic (written above and or below it) you would have the next better approximation with of course a bigger denominator (and numerator.) You could continue until you found one that was as close as you wanted, or until the fraction was the exact value of the decimal number.

Now I don't remember if that presentation was called "continued fractions" or was just an arithmetic book from the early 1900's. I'm pretty sure it was an old book. And it seems obvious to me that the underlying principal was the same as "continued fractions."

Has anyone seen it?

1

There are 1 best solutions below

10
On

We're going to build this table: $$ \matrix{&&a_0&a_1&a_2&\dots\cr p_{-2}=0&p_{-1}=1&p_0&p_1&p_2&\dots\cr q_{-2}=1&q_{-1}=0&q_0&q_1&q_2&\dots\cr} $$ Let $x$ be your decimal. We take $a_0=[x]$ (where $[y]$ means the integer part of $y$, the greatest integer not exceeding $y$), $x_1=(x-a_0)^{-1}$ and $a_i=[x_i]$, $x_{i+1}=(x_i-a_i)^{-1}$. Also, $p_i=a_ip_{i-1}+p_{i-2}$ and $q_i=a_iq_{i-1}+q_{i-2}$. Then your increasingly good approximations are $p_0/q_0,p_1/q_1,p_2/q_2,\dots$.

For example, let $x=1.3862$. Then $a_0=1$, $x_1=(.3862)^{-1}=2.5893$ (to four decimals), $a_1=2$, $x_2=(.5893)^{-1}=1.6969$, $a_2=1$, $x_3=(.6969)^{-1}=1.4349$, $a_3=1$ and so on, so our table is $$ \matrix{&&1&2&1&1&\dots\cr 0&1&1&3&4&7&\dots\cr 1&0&1&2&3&5&\dots\cr} $$ and our approximations are $1,1.5,1.3333,1.4,\dots$.

The relation to continued fractions is that the $a_i$ are the partial quotients in the continued fraction for $x$.