9
$\begingroup$

I'm making a phone game, and I need to approximate $\frac {\log(5/4)}{\log(3/2)}$ to a rational number $p/q$.
I wish $p$ and $q$ small enough. For example, I don't want $p$, $q\approx 10^7$; it's way too much for my code.

In the game, there's two way to upgrade ability. Type A gives an additional $50\%$ increase at once. and type B gives $25\%$.
What I want to know is how many times of upgrade $(x,y)$ provides the same additional increase. So what I've done is solve $(3/2)^x = (5/4)^y$ respect to $\frac xy$.

Can you provide me a way to construct sequence $p_n$, $q_n$ which approximate the real number?
Thank you in advance.

$\endgroup$
  • $\begingroup$ I don't understand your game, but your number approximately $0.55034$ and thus $\tfrac{55034}{100000}$ or $\tfrac{5503}{10000}$. What's wrong with that? $\endgroup$ – amsmath Mar 24 at 2:19
  • 7
    $\begingroup$ The continued fraction expansion of your irrational number will produce the best rational approximation subject to a limit on size of the denominator. $\endgroup$ – hardmath Mar 24 at 2:21
  • 2
    $\begingroup$ You can take truncations of the continued fraction of that number. The first few of its values start like this. $\endgroup$ – user647486 Mar 24 at 2:21
  • $\begingroup$ try 82/149 ........ $\endgroup$ – Will Jagy Mar 24 at 2:23
  • 2
    $\begingroup$ Cool, a practical application of continued fractions. :) $\endgroup$ – Minus One-Twelfth Mar 24 at 2:32
14
$\begingroup$

Running the extended Euclidean algorithm to find the continued fraction:

$$\begin{array}{cc|cc}x&q&a&b\\ \hline 0.55033971 & & 0 & 1\\ 1 & 0 & 1 & 0\\ 0.55033971 & 1 & 0 & 1\\ 0.44966029 & 1 & 1 & -1 \\ 0.10067943 & 4 & -1 & 2\\ 0.04694258 & 2 & 5 & -9\\ 0.00679426 & 6 & -11 & 20 \\ 0.00617700 & 1 & 71 & -129 \\ 0.00061727 & 10 & -82 & 149\\ 4.31\cdot 10^{-6} & 143 & 891 & -1619 \\ 1.25\cdot 10^{-6} & 3 & -127495 & 231666\end{array}$$ The $q$ column are the quotients, that go into the continued fraction. The $a$ and $b$ columns track a linear combination of the original two that's equal to $x_n$; for example, $-11\cdot 1 + 20\cdot \frac{\log(5/4)}{\log(3/2)}\approx 0.00679426$. The fraction $\left|\frac{\log(5/4)}{\log(3/2)}\right|$ is approximated by $\frac{|a_n|}{|b_n|}$, with increasing accuracy.

The formulas for building this table: $q_n = \left\lfloor \frac {x_{n-1}}{x_n}\right\rfloor$, $x_{n+1}=x_{n-1}-q_nx_n$, $a_{n+1}=a_{n-1}-q_na_n$, $b_{n+1}=b_{n-1}-q_nb_n$. Initialize with $x_0=1$, $x_{-1}$ the quantity we're trying to estimate, $a_{-1}=b_0=0$, $a_0=b_{-1}=1$.
If you run the table much large than this, watch for floating-point accuracy issues; once the $x_n$ get down close to the accuracy limit for floating point numbers near zero, you can't trust the quotients anymore.

Now, how that accuracy increases is irregular. Large quotients go with particularly good approximations - see how that quotient of $143$ means that we have to go to six-digit numerator and denominator to do better than that $\frac{891}{1619}$ approximation.

It is of course a tradeoff between accuracy and how deep you go. For your purposes in costing the two upgrades, I'd probably go with that $\frac{11}{20}$ approximation.

$\endgroup$
13
$\begingroup$

The continued fraction for $\frac{\log\left(\frac54\right)}{\log\left(\frac32\right)}$ is $$ {0;1,1,4,2,6,1,\color{#C00}{10},143,3,\dots} $$ The convergents for this continued fraction are $$ \left\{0,1,\frac12,\frac59,\frac{11}{20},\frac{71}{129},\frac{82}{149},\color{#C00}{\frac{891}{1619}},\frac{127495}{231666},\frac{383376}{696617},\dots\right\} $$ As Ross Millikan mentions, stopping just before a large continuant like $143$ gives a particularly good approximation for the size of the denominator; in this case, the approximation $\frac{891}{1619}$ is closer than $\frac1{143\cdot1619^2}$ to $\frac{\log\left(\frac54\right)}{\log\left(\frac32\right)}$.

$\endgroup$
  • $\begingroup$ Thank you. A good addition to my answer. $\endgroup$ – Ross Millikan Mar 24 at 2:54
12
$\begingroup$

The number you want to approximate is about $0.550339713213$. An excellent approximation is $\frac {891}{1619}\approx 0.550339715873$. I got that by using the continued fraction. When you see a large value like $143$, truncating before it yields a very good approximation.

$\endgroup$
  • 2
    $\begingroup$ (+1) I wondered where you got $143$ until I actually computed the continued fraction. I'd hoped it was okay to expand upon your answer to show where that number came from. Also to mention that if $\frac pq$ is a continued fraction approximation and $c$ is the next term in the conitnued fraction (which I think is called a continuant), then $\frac pq$ is closer than $\frac1{cq^2}$ to the value approximated. $\endgroup$ – robjohn Mar 24 at 3:07
2
$\begingroup$

Use the following equation $$\log(1+\frac{1}{x})\approx\frac{3+6x}{6x^2+6x+1}$$ so $$\log(\frac{5}{4})=\log(1+\frac{1}{4})$$ $$\log(\frac{3}{2})=\log(1+\frac{1}{2})$$ the approximated value will be $$\frac {\log(5/4)}{\log(3/2)}\approx \frac{333}{605}=0.55041322$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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