Vrftsjtryk

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$, $qapprox 10^7$; it's way too much for my code.

In the game, there's two way to upgrade ability. Type A gives additional $50%$ increase at once. and type B gives $25%$.

What I want to know is how many times of upgrade $(x,y)$ provides same additional increase. So what I've done is solve $(3/2)^x = (5/4)^y$ respect to $frac xy$.

Can you provide me way to construct sequence $p_n$, $q_n$ which approximate the real number?

Thank you in advance.

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.

The continued fraction for $frac{logleft(frac54right)}{logleft(frac32right)}$ 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},dotsright}
$$
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{143cdot1619^2}$ to $frac{logleft(frac54right)}{logleft(frac32right)}$.

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.31cdot 10^{-6} & 143 & 891 & -1619 \
1.25cdot 10^{-6} & 3 & -127495 & 231666end{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, $-11cdot 1 + 20cdot 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 = leftlfloor frac {x_{n-1}}{x_n}rightrfloor$, $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.