Approximating irrational number to rational number$lim_ntoinfty f(2^n)$ for some very slowly increasing function $f(n)$Hermite Interpolation of $e^x$. Strange behaviour when increasing the number of derivatives at interpolating points.Newton's Method, and approximating parameters for Bézier curves.Approximating Logs and Antilogs by handApproximating fractionsExistence of Irrational Number that has same $n$ digits of a given Rational Number.Finding Irrational Approximation for a given Rational Number.Atomic weights: rational or irrational?Does there exist infinitely many $mu$ which satisfy this:Approximating functions with rational functions

copy and scale one figure (wheel)

Why is so much work done on numerical verification of the Riemann Hypothesis?

Start making guitar arrangements

Did arcade monitors have same pixel aspect ratio as TV sets?

Is the U.S. Code copyrighted by the Government?

A social experiment. What is the worst that can happen?

Approximating irrational number to rational number

How to indicate a cut out for a product window

What should you do if you miss a job interview (deliberately)?

250 Floor Tower

What was the exact wording from Ivanhoe of this advice on how to free yourself from slavery?

Should I outline or discovery write my stories?

The screen of my macbook suddenly broken down how can I do to recover

What does chmod -u do?

How can "mimic phobia" be cured or prevented?

Creature in Shazam mid-credits scene?

Why did the HMS Bounty go back to a time when whales are already rare?

It grows, but water kills it

Is this toilet slogan correct usage of the English language?

What was this official D&D 3.5e Lovecraft-flavored rulebook?

Has any country ever had 2 former presidents in jail simultaneously?

Calculating Wattage for Resistor in High Frequency Application?

Is it safe to use olive oil to clean the ear wax?

Why should universal income be universal?



Approximating irrational number to rational number


$lim_ntoinfty f(2^n)$ for some very slowly increasing function $f(n)$Hermite Interpolation of $e^x$. Strange behaviour when increasing the number of derivatives at interpolating points.Newton's Method, and approximating parameters for Bézier curves.Approximating Logs and Antilogs by handApproximating fractionsExistence of Irrational Number that has same $n$ digits of a given Rational Number.Finding Irrational Approximation for a given Rational Number.Atomic weights: rational or irrational?Does there exist infinitely many $mu$ which satisfy this:Approximating functions with rational functions













3












$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$, $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.










share|cite|improve this question











$endgroup$











  • $begingroup$
    I don't understand your game, but your number approximately $0.55034$ and thus $tfrac55034100000$ or $tfrac550310000$. What's wrong with that?
    $endgroup$
    – amsmath
    1 hour ago






  • 1




    $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
    1 hour ago






  • 1




    $begingroup$
    You can take truncations of the continued fraction of that number. The first few of its values start like this.
    $endgroup$
    – user647486
    1 hour ago











  • $begingroup$
    try 82/149 ........
    $endgroup$
    – Will Jagy
    1 hour ago










  • $begingroup$
    Cool, a practical application of continued fractions. :)
    $endgroup$
    – Minus One-Twelfth
    1 hour ago















3












$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$, $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.










share|cite|improve this question











$endgroup$











  • $begingroup$
    I don't understand your game, but your number approximately $0.55034$ and thus $tfrac55034100000$ or $tfrac550310000$. What's wrong with that?
    $endgroup$
    – amsmath
    1 hour ago






  • 1




    $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
    1 hour ago






  • 1




    $begingroup$
    You can take truncations of the continued fraction of that number. The first few of its values start like this.
    $endgroup$
    – user647486
    1 hour ago











  • $begingroup$
    try 82/149 ........
    $endgroup$
    – Will Jagy
    1 hour ago










  • $begingroup$
    Cool, a practical application of continued fractions. :)
    $endgroup$
    – Minus One-Twelfth
    1 hour ago













3












3








3





$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$, $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.










share|cite|improve this question











$endgroup$




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.







approximation






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 1 hour ago









Rócherz

2,9863821




2,9863821










asked 1 hour ago









MrTanorusMrTanorus

1928




1928











  • $begingroup$
    I don't understand your game, but your number approximately $0.55034$ and thus $tfrac55034100000$ or $tfrac550310000$. What's wrong with that?
    $endgroup$
    – amsmath
    1 hour ago






  • 1




    $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
    1 hour ago






  • 1




    $begingroup$
    You can take truncations of the continued fraction of that number. The first few of its values start like this.
    $endgroup$
    – user647486
    1 hour ago











  • $begingroup$
    try 82/149 ........
    $endgroup$
    – Will Jagy
    1 hour ago










  • $begingroup$
    Cool, a practical application of continued fractions. :)
    $endgroup$
    – Minus One-Twelfth
    1 hour ago
















  • $begingroup$
    I don't understand your game, but your number approximately $0.55034$ and thus $tfrac55034100000$ or $tfrac550310000$. What's wrong with that?
    $endgroup$
    – amsmath
    1 hour ago






  • 1




    $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
    1 hour ago






  • 1




    $begingroup$
    You can take truncations of the continued fraction of that number. The first few of its values start like this.
    $endgroup$
    – user647486
    1 hour ago











  • $begingroup$
    try 82/149 ........
    $endgroup$
    – Will Jagy
    1 hour ago










  • $begingroup$
    Cool, a practical application of continued fractions. :)
    $endgroup$
    – Minus One-Twelfth
    1 hour ago















$begingroup$
I don't understand your game, but your number approximately $0.55034$ and thus $tfrac55034100000$ or $tfrac550310000$. What's wrong with that?
$endgroup$
– amsmath
1 hour ago




$begingroup$
I don't understand your game, but your number approximately $0.55034$ and thus $tfrac55034100000$ or $tfrac550310000$. What's wrong with that?
$endgroup$
– amsmath
1 hour ago




1




1




$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
1 hour ago




$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
1 hour ago




1




1




$begingroup$
You can take truncations of the continued fraction of that number. The first few of its values start like this.
$endgroup$
– user647486
1 hour ago





$begingroup$
You can take truncations of the continued fraction of that number. The first few of its values start like this.
$endgroup$
– user647486
1 hour ago













$begingroup$
try 82/149 ........
$endgroup$
– Will Jagy
1 hour ago




$begingroup$
try 82/149 ........
$endgroup$
– Will Jagy
1 hour ago












$begingroup$
Cool, a practical application of continued fractions. :)
$endgroup$
– Minus One-Twelfth
1 hour ago




$begingroup$
Cool, a practical application of continued fractions. :)
$endgroup$
– Minus One-Twelfth
1 hour ago










3 Answers
3






active

oldest

votes


















3












$begingroup$

The continued fraction for $fraclogleft(frac54right)logleft(frac32right)$ is
$$
0;1,1,4,2,6,1,color#C0010,143,3,dots
$$

The convergents for this continued fraction are
$$
left0,1,frac12,frac59,frac1120,frac71129,frac82149,color#C00frac8911619,frac127495231666,frac383376696617,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 $frac8911619$ is closer than $frac1143cdot1619^2$ to $fraclogleft(frac54right)logleft(frac32right)$.






share|cite|improve this answer









$endgroup$












  • $begingroup$
    Thank you. A good addition to my answer.
    $endgroup$
    – Ross Millikan
    59 mins ago


















2












$begingroup$

The number you want to approximate is about $0.550339713213$. An excellent approximation is $frac 8911619approx 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.






share|cite|improve this answer









$endgroup$












  • $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 and $c$ is the next term in the conitnued fraction (which I think is called a continuant), then $frac pq$ is closer than $frac1cq^2$ to the value approximated.
    $endgroup$
    – robjohn
    46 mins ago


















1












$begingroup$

Running the extended Euclidean algorithm to find the continued fraction:



$$beginarrayccx&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 & 231666endarray$$

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 fraclog(5/4)log(3/2)approx 0.00679426$. The fraction $left|fraclog(5/4)log(3/2)right|$ is approximated by $frac$, with increasing accuracy.



The formulas for building this table: $q_n = leftlfloor frac x_n-1x_nrightrfloor$, $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 $frac8911619$ 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 $frac1120$ approximation.






share|cite|improve this answer









$endgroup$












    Your Answer





    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "69"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader:
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    ,
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );













    draft saved

    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3160023%2fapproximating-irrational-number-to-rational-number%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown

























    3 Answers
    3






    active

    oldest

    votes








    3 Answers
    3






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    3












    $begingroup$

    The continued fraction for $fraclogleft(frac54right)logleft(frac32right)$ is
    $$
    0;1,1,4,2,6,1,color#C0010,143,3,dots
    $$

    The convergents for this continued fraction are
    $$
    left0,1,frac12,frac59,frac1120,frac71129,frac82149,color#C00frac8911619,frac127495231666,frac383376696617,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 $frac8911619$ is closer than $frac1143cdot1619^2$ to $fraclogleft(frac54right)logleft(frac32right)$.






    share|cite|improve this answer









    $endgroup$












    • $begingroup$
      Thank you. A good addition to my answer.
      $endgroup$
      – Ross Millikan
      59 mins ago















    3












    $begingroup$

    The continued fraction for $fraclogleft(frac54right)logleft(frac32right)$ is
    $$
    0;1,1,4,2,6,1,color#C0010,143,3,dots
    $$

    The convergents for this continued fraction are
    $$
    left0,1,frac12,frac59,frac1120,frac71129,frac82149,color#C00frac8911619,frac127495231666,frac383376696617,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 $frac8911619$ is closer than $frac1143cdot1619^2$ to $fraclogleft(frac54right)logleft(frac32right)$.






    share|cite|improve this answer









    $endgroup$












    • $begingroup$
      Thank you. A good addition to my answer.
      $endgroup$
      – Ross Millikan
      59 mins ago













    3












    3








    3





    $begingroup$

    The continued fraction for $fraclogleft(frac54right)logleft(frac32right)$ is
    $$
    0;1,1,4,2,6,1,color#C0010,143,3,dots
    $$

    The convergents for this continued fraction are
    $$
    left0,1,frac12,frac59,frac1120,frac71129,frac82149,color#C00frac8911619,frac127495231666,frac383376696617,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 $frac8911619$ is closer than $frac1143cdot1619^2$ to $fraclogleft(frac54right)logleft(frac32right)$.






    share|cite|improve this answer









    $endgroup$



    The continued fraction for $fraclogleft(frac54right)logleft(frac32right)$ is
    $$
    0;1,1,4,2,6,1,color#C0010,143,3,dots
    $$

    The convergents for this continued fraction are
    $$
    left0,1,frac12,frac59,frac1120,frac71129,frac82149,color#C00frac8911619,frac127495231666,frac383376696617,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 $frac8911619$ is closer than $frac1143cdot1619^2$ to $fraclogleft(frac54right)logleft(frac32right)$.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered 1 hour ago









    robjohnrobjohn

    269k27311638




    269k27311638











    • $begingroup$
      Thank you. A good addition to my answer.
      $endgroup$
      – Ross Millikan
      59 mins ago
















    • $begingroup$
      Thank you. A good addition to my answer.
      $endgroup$
      – Ross Millikan
      59 mins ago















    $begingroup$
    Thank you. A good addition to my answer.
    $endgroup$
    – Ross Millikan
    59 mins ago




    $begingroup$
    Thank you. A good addition to my answer.
    $endgroup$
    – Ross Millikan
    59 mins ago











    2












    $begingroup$

    The number you want to approximate is about $0.550339713213$. An excellent approximation is $frac 8911619approx 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.






    share|cite|improve this answer









    $endgroup$












    • $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 and $c$ is the next term in the conitnued fraction (which I think is called a continuant), then $frac pq$ is closer than $frac1cq^2$ to the value approximated.
      $endgroup$
      – robjohn
      46 mins ago















    2












    $begingroup$

    The number you want to approximate is about $0.550339713213$. An excellent approximation is $frac 8911619approx 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.






    share|cite|improve this answer









    $endgroup$












    • $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 and $c$ is the next term in the conitnued fraction (which I think is called a continuant), then $frac pq$ is closer than $frac1cq^2$ to the value approximated.
      $endgroup$
      – robjohn
      46 mins ago













    2












    2








    2





    $begingroup$

    The number you want to approximate is about $0.550339713213$. An excellent approximation is $frac 8911619approx 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.






    share|cite|improve this answer









    $endgroup$



    The number you want to approximate is about $0.550339713213$. An excellent approximation is $frac 8911619approx 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.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered 1 hour ago









    Ross MillikanRoss Millikan

    300k24200374




    300k24200374











    • $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 and $c$ is the next term in the conitnued fraction (which I think is called a continuant), then $frac pq$ is closer than $frac1cq^2$ to the value approximated.
      $endgroup$
      – robjohn
      46 mins ago
















    • $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 and $c$ is the next term in the conitnued fraction (which I think is called a continuant), then $frac pq$ is closer than $frac1cq^2$ to the value approximated.
      $endgroup$
      – robjohn
      46 mins ago















    $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 and $c$ is the next term in the conitnued fraction (which I think is called a continuant), then $frac pq$ is closer than $frac1cq^2$ to the value approximated.
    $endgroup$
    – robjohn
    46 mins ago




    $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 and $c$ is the next term in the conitnued fraction (which I think is called a continuant), then $frac pq$ is closer than $frac1cq^2$ to the value approximated.
    $endgroup$
    – robjohn
    46 mins ago











    1












    $begingroup$

    Running the extended Euclidean algorithm to find the continued fraction:



    $$beginarrayccx&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 & 231666endarray$$

    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 fraclog(5/4)log(3/2)approx 0.00679426$. The fraction $left|fraclog(5/4)log(3/2)right|$ is approximated by $frac$, with increasing accuracy.



    The formulas for building this table: $q_n = leftlfloor frac x_n-1x_nrightrfloor$, $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 $frac8911619$ 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 $frac1120$ approximation.






    share|cite|improve this answer









    $endgroup$

















      1












      $begingroup$

      Running the extended Euclidean algorithm to find the continued fraction:



      $$beginarrayccx&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 & 231666endarray$$

      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 fraclog(5/4)log(3/2)approx 0.00679426$. The fraction $left|fraclog(5/4)log(3/2)right|$ is approximated by $frac$, with increasing accuracy.



      The formulas for building this table: $q_n = leftlfloor frac x_n-1x_nrightrfloor$, $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 $frac8911619$ 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 $frac1120$ approximation.






      share|cite|improve this answer









      $endgroup$















        1












        1








        1





        $begingroup$

        Running the extended Euclidean algorithm to find the continued fraction:



        $$beginarrayccx&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 & 231666endarray$$

        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 fraclog(5/4)log(3/2)approx 0.00679426$. The fraction $left|fraclog(5/4)log(3/2)right|$ is approximated by $frac$, with increasing accuracy.



        The formulas for building this table: $q_n = leftlfloor frac x_n-1x_nrightrfloor$, $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 $frac8911619$ 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 $frac1120$ approximation.






        share|cite|improve this answer









        $endgroup$



        Running the extended Euclidean algorithm to find the continued fraction:



        $$beginarrayccx&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 & 231666endarray$$

        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 fraclog(5/4)log(3/2)approx 0.00679426$. The fraction $left|fraclog(5/4)log(3/2)right|$ is approximated by $frac$, with increasing accuracy.



        The formulas for building this table: $q_n = leftlfloor frac x_n-1x_nrightrfloor$, $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 $frac8911619$ 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 $frac1120$ approximation.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 1 hour ago









        jmerryjmerry

        15.8k1632




        15.8k1632



























            draft saved

            draft discarded
















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid


            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.

            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3160023%2fapproximating-irrational-number-to-rational-number%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Reverse int within the 32-bit signed integer range: [−2^31, 2^31 − 1]Combining two 32-bit integers into one 64-bit integerDetermine if an int is within rangeLossy packing 32 bit integer to 16 bitComputing the square root of a 64-bit integerKeeping integer addition within boundsSafe multiplication of two 64-bit signed integersLeetcode 10: Regular Expression MatchingSigned integer-to-ascii x86_64 assembler macroReverse the digits of an Integer“Add two numbers given in reverse order from a linked list”

            Category:Fedor von Bock Media in category "Fedor von Bock"Navigation menuUpload mediaISNI: 0000 0000 5511 3417VIAF ID: 24712551GND ID: 119294796Library of Congress authority ID: n96068363BnF ID: 12534305fSUDOC authorities ID: 034604189Open Library ID: OL338253ANKCR AUT ID: jn19990000869National Library of Israel ID: 000514068National Thesaurus for Author Names ID: 341574317ReasonatorScholiaStatistics

            Kiel Indholdsfortegnelse Historie | Transport og færgeforbindelser | Sejlsport og anden sport | Kultur | Kendte personer fra Kiel | Noter | Litteratur | Eksterne henvisninger | Navigationsmenuwww.kiel.de54°19′31″N 10°8′26″Ø / 54.32528°N 10.14056°Ø / 54.32528; 10.14056Oberbürgermeister Dr. Ulf Kämpferwww.statistik-nord.deDen danske Stats StatistikKiels hjemmesiderrrWorldCat312794080n790547494030481-4