8 ms·

Decimal to fraction

91 points by ingve 3y ago

svat 3y ago
For the continued-fraction convergents, instead of Mathematica, here's a web page of mine that does the same thing: https://shreevatsa.net/fraction/best https://shreevatsa.net/fraction/best (try it with the 3.213432 from the post, and a large limit for the denominator). Also, the mediants approach mentioned in the post is not unrelated to continued fractions; the latter can be seen as an "accelerated" version of the mediants (specifically, counting how many times to take certain mediants, and directly getting there), as explained in this great article "Continued fractions without tears": https://www.maa.org/programs/maa-awards/writing-awards/continued-fractions-without-tears https://www.maa.org/programs/maa-awards/writing-awards/conti...
- jostylr 3y ago
  That article is a truly marvelous article and very worth reading for anyone interested in either continued fractions or rational approximations. For those who are curious, a simple algorithm for generating these good approximations and continued fractions is to take the mediant of a Farey pair that enclose the given number, such as [3/1, 4/1], here 7/2, and then choose the sub-interval that contains the desired number. Repeat as desired. This first step has [3/1, 7/2] as the next interval to look at as 3/1 < 3.213432 < 7/2. When doing this to generate the continued fraction representation, start with the nominal interval [0/1, 1/0]. A few steps: 0/1 : 1/1 : 1/0 R 1/1 : 2/1 : 1/0 R 2/1 : 3/1 : 1/0 R 3/1 : 4/1 : 1/0 L 3/1 : 7/2 : 4/1 L 3/1 : 10/3 : 7/2 L 3/1 : 13/4 : 10/3 L 3/1 : 16/5 : 13/4 R 16/5 : 29/9 : 13/4 L 16/5 : 45/14 :29/9 L 16/5 : 61/19 : 45/14 R 61/19 : 106/33 : 45/14 R ... The number 106/33 is 3.2121... and is generated by easy computation of the mediants. Each time the direction of selection is changed, this results in having an ultra-best approximation. If we count the number of steps in between the switches, we get the continued fraction representation: [3; 4, 1, 2, ...]. This is also related to the Stern-Brocot tree, for those interested. Playing around with these ideas led me to the idea of defining a real number as a number that, given a rational interval, says Yes or No depending on whether it ought to be in that interval. To define the space of such objects, I used properties that the Yes/No answers have to satisfy. The key property is that if you split a Yes interval into two pieces, one of the pieces should be Yes and the other No (unless the splitting point is the real number). If curious for details, my paper repository on this matter is at https://github.com/jostylr/Reals-as-Oracles https://github.com/jostylr/Reals-as-Oracles where I not only prove that it all works out as it should, but also give an example of doing continued fraction arithmetic in section 7.9 of the main paper for those who just love continued fractions.
ineedasername 3y ago
I have a background in linguistics (computational) and part of what was mind blowing when my schooling approached the deep dive on some aspects of it was the sheer extent to which much of what we put into language is artificially constrained by the limits of any given language being unable to fully express an infinite range of concepts/thoughts/etc… that some things are difficult to put into words because there are no words for every single gradation of a a phenomenon (colors, with their inherent connection to gradients, come to mind). Maybe this seems trivial, I kind of had an intuitive “of course” understanding of it before deep dive work in linguistics, but that’s when it really became abundantly clear how limited we are by lexical entries. All of that is a preamble to say that it seems like the same thing is true of mathematics. No single number system can completely encompass all of mathematical expressions. This post sort of touches on it with the varying methods of expressing something in decimal vs fractional notation. 1/3 cannot be fully expressed (well, expanded) in decimal notation but it is trivial in fractional notation. More esoteric examples exist when entering the realm of hyperreal numbers. It is both amazing and daunting to confront these limits, which may be a product of the limitations of the human mind.(or not, really I don’t know) And maybe I’m just rambling… I don’t have a strong background in number theory… it is all just so beautiful and humbling though.
m348e912 3y ago
In the video this guy uses web vpython but doesn't share what website he is using. Google points me to glowscript.org, but it's clear he is using a different web vpython tool (based on the look and icons) Anyone know what tool/website he is using to code python?
- NikkiA 3y ago
  The video description links to his trinket.io account that he's using for it.
  - m348e912 3y ago
    That was it, thank you!
MikeBattaglia 3y ago
He points out that the YouTube video "uses mediants" to compute rational approximations to real numbers. He then says that the continued fraction expansion is better. However, the mediant-based method is totally identical to the continued fraction expansion method. The two are related via the Stern-Brocot tree (https://en.m.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree https://en.m.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree). The fractions that one gets from iterating the mediant process are exactly the "semiconvergents" one gets from the continued fraction process. Truncating the continued fraction gives the "convergents"; these are special mediants which are right before switching direction as one zig zags on the tree.
adas0693 3y ago
There are a couple of well-known algorithms to find the best rational approximation to a given real number. A good and short book is "Diophantine Approximations" by I. Niven. For code, you can also check out this repo of mine: https://github.com/alidasdan/best-rational-approximation https://github.com/alidasdan/best-rational-approximation . Note that decimal numbers represented as a floating point numbers on a computer are actually rational numbers due to limited precision. So converting decimal numbers to fractions, both stored on a computer, means converting a fraction with potentially large numerator and/or denominator to a simpler fraction, say, one with a far smaller denonimator. For example, an approximation to pi is 3.14159265358979323844, which is the same thing as 314159265358979323844/10^20 (trivial approximation). Using these algorithms we can covert this fraction to a simpler fraction under different approximation criteria such as a bound on the approximation error or a bound on the magnitude of the denominator. For this example, we then get various approximations to pi such as 22/7, 355/113, ...
murkle 3y ago
Here's a good algorithm: https://web.archive.org/web/20111027100847/http://homepage.smc.edu/kennedy_john/DEC2FRAC.PDF https://web.archive.org/web/20111027100847/http://homepage.s... Algorithm To Convert A Decimal To A Fraction by John Kennedy Mathematics Department Santa Monica College 1900 Pico Blvd. Santa Monica, CA 90405 http://homepage.smc.edu/kennedy_john/DEC2FRAC.PDF http://homepage.smc.edu/kennedy_john/DEC2FRAC.PDF
- OskarS 3y ago
  Why would you do this instead of just converting the digits to a fraction over a power of 10 and then reducing the fraction (or power of 2, if it's a floating point datatype)? I was thinking it was faster, but the recursive procedure involves a division step, so I would assume that calculating GCD using the binary algorithm (which is just uses shifts and subtraction) would be faster? I guess this is if your numeric data-type can't fit the size of the denominator?
  - Vvector 3y ago
    How would you get to 355/113 from pi using your method?
  - Someone 3y ago
    If you assume/know the decimal you got is the result of rounding some computation, and are more interested in a short description than in the most accurate one. For example 0.142857 would be 142,857/1,000,000 in your algorithm, but ⅐ in one using best rational approximations (which I assume that paper does, as they’re easy to calculate and, according to a fairly intuitive metric, best)
    - dreamcompiler 3y ago
      Common Lisp gives you this choice (this being HN, a Lisp mention is obligatory :-) The CL function #'rational converts a float to a rational assuming the float is completely accurate (i.e. every decimal digit after the last internally-represented one is assumed to be 0), while #'rationalize assumes the float is only accurate to the limit of float precision (i.e. the decimal digits after the last internally-represented one can be anything that would round to the last one). Both functions preserve the invariant that (float (rational x) x) == x and (float (rationalize x) x) == x ...which is another way of saying they don't lose information. In practice these tend to be not very useful to me because they don't provide the ability to specify which decimal digit should be considered the last one: They take this parameter from the underlying float representation, which sometimes causes unexpected results (the denominator can end up being larger than you expected) because the input number can effectively have zeros added at the end if the underlying float representation is large enough to capture more bits than you specified when you typed in the number. In addition, what I really need much of the time is the ability to limit the size of the resulting denominator, like "give me the best rational equivalent of 0.142857 with at most a 3-digit denominator". That function is not built in to Common Lisp but one can write it using the methods in TFA. It loses information of course so a round trip from float->rational->float won't necessarily produce the same result.
uoaei 3y ago
Pretty good Mathologer video about continued fractions: https://www.youtube.com/watch?v=CaasbfdJdJg https://www.youtube.com/watch?v=CaasbfdJdJg One neat trivium I like to quiz the mathematically-minded on is: what number is the most irrational, i.e., toward which number do rational approximations converge the slowest? The answer can be determined from continued fractions and is discussed in the video near the end.
- bitshiftfaced 3y ago
  Also got me thinking about what fraction is most "pi efficient"? That is, what fraction is closest to pi compared to how many digits you must use to represent the fraction (or perhaps only digits in the numerator or denominator)?
  - uoaei 3y ago
    Seems they answered that question in TFA.
    - bitshiftfaced 3y ago
      Using continued fractions in Mathematica. Maybe there's enough information in the article to say that this is enough to have answered the question. I don't know enough about all of the methods to say, personally. Also, I never outlined what was the best metric to evaluate how well accuracy compares to the number of digits needed.
      - ninepoints 3y ago
        The answer is already there. If you extend the sequence given in the article longer, the ratio of the number of digits in the rational representation to the decimal representation gets worse, not better, so you know you reached the inflection point early.
      - ykonstant 3y ago
        As others have said, the convergents of the simple continued fraction representation give the best rational approximation [1] relative to the size of the fraction, in the strongest relevant metric: that of absolute error bound. Proofs can be found in any book on Diophantine Approximation; the classic (and readable) reference is Khinchin's Continued Fractions book. [1] https://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations https://en.wikipedia.org/wiki/Continued_fraction#Best_ration...
eesmith 3y ago
If you don't want to do this yourself, use Python's built-in fractions module. Fractions have a built-in method to compute the best fraction given a maximum denominator: >>> from fractions import Fraction >>> x = Fraction("3.213432") >>> int(x) 3 >>> (x % 1).limit_denominator(9999) Fraction(375, 1757) The mediant-based implementation is at https://github.com/python/cpython/blob/607f18c89456cdc9064e27f86a7505e011209757/Lib/fractions.py#L340 https://github.com/python/cpython/blob/607f18c89456cdc9064e2...
- CodesInChaos 3y ago
  Often it will be preferable to limit the error instead of the denominator. "Find the fraction with the smallest denominator that's within 0.005 of 0.33." Does python support this as well?
  - eesmith 3y ago
    Not directly that I know of, but that's definitely a straight-forward mediant calculation. I'll do it all in integer ratios and assume the answer is somewhere between 0.0 and +inf, exclusive: from fractions import Fraction mid = Fraction("0.33") delta = mid * Fraction("0.005") lo = (mid - delta) lo_p, lo_q = lo.as_integer_ratio() hi = (mid + delta) hi_p, hi_q = hi.as_integer_ratio() p0, q0, p1, q1 = 0, 1, 1, 0 while True: p = p0 + p1 q = q0 + q1 if p * lo_q < lo_p * q: # p/q < lo_p/lo_q p0, q0 = p, q continue if p * hi_q > q * hi_p: # p/q > hi_p/hi_q p1, q1 = p, q continue break # in range frac = Fraction(p, q) print(f"Found: {p}/{q}") print(f"{lo} <= {frac} <= {hi}? {lo <= frac <= hi}") For your test case: Found: 22/67 6567/20000 <= 22/67 <= 6633/20000? True A grep of the CPython distribution found no use of the word "mediant".
    - jepler 3y ago
      For anyone else who was puzzled at this result (rather than 1/3): The above algorithm is finding something with the relative error of at most .005 times the input value 0.33. 1/3 is the best value for the absolute error of at most .005.
LinuxBender 3y ago
One could use bc for this [1] commonly installed on Linux and may also be on Mac I believe. Unsure if WSL installs it. [1] - https://superuser.com/questions/377492/how-to-do-division-with-bc-bench-calculator-and-obtain-fractional-results https://superuser.com/questions/377492/how-to-do-division-wi...
andai 3y ago
Fascinating. I'm not very good at math, but one of the first things I programmed was bruteforce search for the fraction closest to Pi. It's nice to see the "proper" way of doing things! I might revisit my program and see what the efficiency savings are like! (99.99%?)
NevaehTheHacker 3y ago
how do i become a hacker???
qwerty456127 3y ago
I started studying Lisp recently and it blew my mind it can do rational fractions, also virtually infinite length integers, OOTB. I used and programmed computers since 286s and have never seen this before. Now I don't even understand why do people still use calculators (including calculator apps) when we have Lisp which is easier and more powerful.
- zdimension 3y ago
  There's a nice calculator app bundled with Windows 10, and I even have Mathematica installed, and of course Desmos is useable everywhere, but... when I need to compute anything that's more than simple elementary arithmetic, I just open a Python REPL. It's simple to type, it's readable, and way easier to use than a calculator for persistence (ever tried to use variables on a scientific calculator? It works, but it sucks)
  - qwerty456127 3y ago
    > when I need to compute anything that's more than simple elementary arithmetic, I just open a Python REPL. It's simple to type, it's readable Indeed. It also is fairly hard (to me at least) to enter a long (longer than 2 operands) sequence into a classic calculator without making a typo. Whenever I need even to just add 4 numbers I don't use a calculator to enter 1 + 2 + 3 + 4 nor a spreadsheet to enter the data in separate cells, select them and see the sum (I used this way until recently) - I open IdeOne.com, choose Common Lisp and enter (+ 1 2 3 4). Needless to day I don't only use it for formulae this simple, it is of great help in complex cases.
mikewarot 3y ago
I had a similar problem a few years ago, when I was making gears (and gear shaped objects) in a machine shop on old gear driven machines. We had most, but not all, of the change gears, and when making Worm or Bevel Gears, you'd often have a ratio, and have to work backwards to figure out a set of gears to get as close as possible to that ratio. I wrote the simplest possible pascal/windows GUI application[1] to simply try all the possible gear combinations, and keep the lowest. I was shocked when it returned an answer in less than a second. I thought for sure I was going to be digging into algorithms like this, but nope... cheap compute saved me. I'd quickly get the gears, and the error in parts per million. I do feel myself getting Nerd Sniped though... must resist. [1] https://github.com/mikewarot/GearFinder https://github.com/mikewarot/GearFinder
- I_Byte 3y ago
  The GitHub link you posted appears to 404.
  - mikewarot 3y ago
    Oops... didn't realize it was private, changed to Public, made GPL 3.0 licensed. and added a screen shot with some directions and created my first ever "release" on github

91 points by ingve 3y ago

svat 3y ago

For the continued-fraction convergents, instead of Mathematica, here's a web page of mine that does the same thing: https://shreevatsa.net/fraction/best https://shreevatsa.net/fraction/best (try it with the 3.213432 from the post, and a large limit for the denominator). Also, the mediants approach mentioned in the post is not unrelated to continued fractions; the latter can be seen as an "accelerated" version of the mediants (specifically, counting how many times to take certain mediants, and directly getting there), as explained in this great article "Continued fractions without tears": https://www.maa.org/programs/maa-awards/writing-awards/continued-fractions-without-tears https://www.maa.org/programs/maa-awards/writing-awards/conti...

jostylr 3y ago
That article is a truly marvelous article and very worth reading for anyone interested in either continued fractions or rational approximations. For those who are curious, a simple algorithm for generating these good approximations and continued fractions is to take the mediant of a Farey pair that enclose the given number, such as [3/1, 4/1], here 7/2, and then choose the sub-interval that contains the desired number. Repeat as desired. This first step has [3/1, 7/2] as the next interval to look at as 3/1 < 3.213432 < 7/2. When doing this to generate the continued fraction representation, start with the nominal interval [0/1, 1/0]. A few steps: 0/1 : 1/1 : 1/0 R 1/1 : 2/1 : 1/0 R 2/1 : 3/1 : 1/0 R 3/1 : 4/1 : 1/0 L 3/1 : 7/2 : 4/1 L 3/1 : 10/3 : 7/2 L 3/1 : 13/4 : 10/3 L 3/1 : 16/5 : 13/4 R 16/5 : 29/9 : 13/4 L 16/5 : 45/14 :29/9 L 16/5 : 61/19 : 45/14 R 61/19 : 106/33 : 45/14 R ... The number 106/33 is 3.2121... and is generated by easy computation of the mediants. Each time the direction of selection is changed, this results in having an ultra-best approximation. If we count the number of steps in between the switches, we get the continued fraction representation: [3; 4, 1, 2, ...]. This is also related to the Stern-Brocot tree, for those interested. Playing around with these ideas led me to the idea of defining a real number as a number that, given a rational interval, says Yes or No depending on whether it ought to be in that interval. To define the space of such objects, I used properties that the Yes/No answers have to satisfy. The key property is that if you split a Yes interval into two pieces, one of the pieces should be Yes and the other No (unless the splitting point is the real number). If curious for details, my paper repository on this matter is at https://github.com/jostylr/Reals-as-Oracles https://github.com/jostylr/Reals-as-Oracles where I not only prove that it all works out as it should, but also give an example of doing continued fraction arithmetic in section 7.9 of the main paper for those who just love continued fractions.

ineedasername 3y ago

I have a background in linguistics (computational) and part of what was mind blowing when my schooling approached the deep dive on some aspects of it was the sheer extent to which much of what we put into language is artificially constrained by the limits of any given language being unable to fully express an infinite range of concepts/thoughts/etc… that some things are difficult to put into words because there are no words for every single gradation of a a phenomenon (colors, with their inherent connection to gradients, come to mind). Maybe this seems trivial, I kind of had an intuitive “of course” understanding of it before deep dive work in linguistics, but that’s when it really became abundantly clear how limited we are by lexical entries. All of that is a preamble to say that it seems like the same thing is true of mathematics. No single number system can completely encompass all of mathematical expressions. This post sort of touches on it with the varying methods of expressing something in decimal vs fractional notation. 1/3 cannot be fully expressed (well, expanded) in decimal notation but it is trivial in fractional notation. More esoteric examples exist when entering the realm of hyperreal numbers. It is both amazing and daunting to confront these limits, which may be a product of the limitations of the human mind.(or not, really I don’t know) And maybe I’m just rambling… I don’t have a strong background in number theory… it is all just so beautiful and humbling though.

m348e912 3y ago

In the video this guy uses web vpython but doesn't share what website he is using. Google points me to glowscript.org, but it's clear he is using a different web vpython tool (based on the look and icons) Anyone know what tool/website he is using to code python?

NikkiA 3y ago
The video description links to his trinket.io account that he's using for it.
- m348e912 3y ago
  That was it, thank you!

MikeBattaglia 3y ago

He points out that the YouTube video "uses mediants" to compute rational approximations to real numbers. He then says that the continued fraction expansion is better. However, the mediant-based method is totally identical to the continued fraction expansion method. The two are related via the Stern-Brocot tree (https://en.m.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree https://en.m.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree). The fractions that one gets from iterating the mediant process are exactly the "semiconvergents" one gets from the continued fraction process. Truncating the continued fraction gives the "convergents"; these are special mediants which are right before switching direction as one zig zags on the tree.

adas0693 3y ago

There are a couple of well-known algorithms to find the best rational approximation to a given real number. A good and short book is "Diophantine Approximations" by I. Niven. For code, you can also check out this repo of mine: https://github.com/alidasdan/best-rational-approximation https://github.com/alidasdan/best-rational-approximation . Note that decimal numbers represented as a floating point numbers on a computer are actually rational numbers due to limited precision. So converting decimal numbers to fractions, both stored on a computer, means converting a fraction with potentially large numerator and/or denominator to a simpler fraction, say, one with a far smaller denonimator. For example, an approximation to pi is 3.14159265358979323844, which is the same thing as 314159265358979323844/10^20 (trivial approximation). Using these algorithms we can covert this fraction to a simpler fraction under different approximation criteria such as a bound on the approximation error or a bound on the magnitude of the denominator. For this example, we then get various approximations to pi such as 22/7, 355/113, ...

murkle 3y ago

Here's a good algorithm: https://web.archive.org/web/20111027100847/http://homepage.smc.edu/kennedy_john/DEC2FRAC.PDF https://web.archive.org/web/20111027100847/http://homepage.s... Algorithm To Convert A Decimal To A Fraction by John Kennedy Mathematics Department Santa Monica College 1900 Pico Blvd. Santa Monica, CA 90405 http://homepage.smc.edu/kennedy_john/DEC2FRAC.PDF http://homepage.smc.edu/kennedy_john/DEC2FRAC.PDF

OskarS 3y ago
Why would you do this instead of just converting the digits to a fraction over a power of 10 and then reducing the fraction (or power of 2, if it's a floating point datatype)? I was thinking it was faster, but the recursive procedure involves a division step, so I would assume that calculating GCD using the binary algorithm (which is just uses shifts and subtraction) would be faster? I guess this is if your numeric data-type can't fit the size of the denominator?
- Vvector 3y ago
  How would you get to 355/113 from pi using your method?
- Someone 3y ago
  If you assume/know the decimal you got is the result of rounding some computation, and are more interested in a short description than in the most accurate one. For example 0.142857 would be 142,857/1,000,000 in your algorithm, but ⅐ in one using best rational approximations (which I assume that paper does, as they’re easy to calculate and, according to a fairly intuitive metric, best)
  - dreamcompiler 3y ago
    Common Lisp gives you this choice (this being HN, a Lisp mention is obligatory :-) The CL function #'rational converts a float to a rational assuming the float is completely accurate (i.e. every decimal digit after the last internally-represented one is assumed to be 0), while #'rationalize assumes the float is only accurate to the limit of float precision (i.e. the decimal digits after the last internally-represented one can be anything that would round to the last one). Both functions preserve the invariant that (float (rational x) x) == x and (float (rationalize x) x) == x ...which is another way of saying they don't lose information. In practice these tend to be not very useful to me because they don't provide the ability to specify which decimal digit should be considered the last one: They take this parameter from the underlying float representation, which sometimes causes unexpected results (the denominator can end up being larger than you expected) because the input number can effectively have zeros added at the end if the underlying float representation is large enough to capture more bits than you specified when you typed in the number. In addition, what I really need much of the time is the ability to limit the size of the resulting denominator, like "give me the best rational equivalent of 0.142857 with at most a 3-digit denominator". That function is not built in to Common Lisp but one can write it using the methods in TFA. It loses information of course so a round trip from float->rational->float won't necessarily produce the same result.

uoaei 3y ago

Pretty good Mathologer video about continued fractions: https://www.youtube.com/watch?v=CaasbfdJdJg https://www.youtube.com/watch?v=CaasbfdJdJg One neat trivium I like to quiz the mathematically-minded on is: what number is the most irrational, i.e., toward which number do rational approximations converge the slowest? The answer can be determined from continued fractions and is discussed in the video near the end.

bitshiftfaced 3y ago
Also got me thinking about what fraction is most "pi efficient"? That is, what fraction is closest to pi compared to how many digits you must use to represent the fraction (or perhaps only digits in the numerator or denominator)?
- uoaei 3y ago
  Seems they answered that question in TFA.
  - bitshiftfaced 3y ago
    Using continued fractions in Mathematica. Maybe there's enough information in the article to say that this is enough to have answered the question. I don't know enough about all of the methods to say, personally. Also, I never outlined what was the best metric to evaluate how well accuracy compares to the number of digits needed.
    - ninepoints 3y ago
      The answer is already there. If you extend the sequence given in the article longer, the ratio of the number of digits in the rational representation to the decimal representation gets worse, not better, so you know you reached the inflection point early.
    - ykonstant 3y ago
      As others have said, the convergents of the simple continued fraction representation give the best rational approximation [1] relative to the size of the fraction, in the strongest relevant metric: that of absolute error bound. Proofs can be found in any book on Diophantine Approximation; the classic (and readable) reference is Khinchin's Continued Fractions book. [1] https://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations https://en.wikipedia.org/wiki/Continued_fraction#Best_ration...

eesmith 3y ago

If you don't want to do this yourself, use Python's built-in fractions module. Fractions have a built-in method to compute the best fraction given a maximum denominator: >>> from fractions import Fraction >>> x = Fraction("3.213432") >>> int(x) 3 >>> (x % 1).limit_denominator(9999) Fraction(375, 1757) The mediant-based implementation is at https://github.com/python/cpython/blob/607f18c89456cdc9064e27f86a7505e011209757/Lib/fractions.py#L340 https://github.com/python/cpython/blob/607f18c89456cdc9064e2...

CodesInChaos 3y ago
Often it will be preferable to limit the error instead of the denominator. "Find the fraction with the smallest denominator that's within 0.005 of 0.33." Does python support this as well?
- eesmith 3y ago
  Not directly that I know of, but that's definitely a straight-forward mediant calculation. I'll do it all in integer ratios and assume the answer is somewhere between 0.0 and +inf, exclusive: from fractions import Fraction mid = Fraction("0.33") delta = mid * Fraction("0.005") lo = (mid - delta) lo_p, lo_q = lo.as_integer_ratio() hi = (mid + delta) hi_p, hi_q = hi.as_integer_ratio() p0, q0, p1, q1 = 0, 1, 1, 0 while True: p = p0 + p1 q = q0 + q1 if p * lo_q < lo_p * q: # p/q < lo_p/lo_q p0, q0 = p, q continue if p * hi_q > q * hi_p: # p/q > hi_p/hi_q p1, q1 = p, q continue break # in range frac = Fraction(p, q) print(f"Found: {p}/{q}") print(f"{lo} <= {frac} <= {hi}? {lo <= frac <= hi}") For your test case: Found: 22/67 6567/20000 <= 22/67 <= 6633/20000? True A grep of the CPython distribution found no use of the word "mediant".
  - jepler 3y ago
    For anyone else who was puzzled at this result (rather than 1/3): The above algorithm is finding something with the relative error of at most .005 times the input value 0.33. 1/3 is the best value for the absolute error of at most .005.

LinuxBender 3y ago

One could use bc for this [1] commonly installed on Linux and may also be on Mac I believe. Unsure if WSL installs it. [1] - https://superuser.com/questions/377492/how-to-do-division-with-bc-bench-calculator-and-obtain-fractional-results https://superuser.com/questions/377492/how-to-do-division-wi...

andai 3y ago

Fascinating. I'm not very good at math, but one of the first things I programmed was bruteforce search for the fraction closest to Pi. It's nice to see the "proper" way of doing things! I might revisit my program and see what the efficiency savings are like! (99.99%?)

NevaehTheHacker 3y ago

how do i become a hacker???

qwerty456127 3y ago

I started studying Lisp recently and it blew my mind it can do rational fractions, also virtually infinite length integers, OOTB. I used and programmed computers since 286s and have never seen this before. Now I don't even understand why do people still use calculators (including calculator apps) when we have Lisp which is easier and more powerful.

zdimension 3y ago
There's a nice calculator app bundled with Windows 10, and I even have Mathematica installed, and of course Desmos is useable everywhere, but... when I need to compute anything that's more than simple elementary arithmetic, I just open a Python REPL. It's simple to type, it's readable, and way easier to use than a calculator for persistence (ever tried to use variables on a scientific calculator? It works, but it sucks)
- qwerty456127 3y ago
  > when I need to compute anything that's more than simple elementary arithmetic, I just open a Python REPL. It's simple to type, it's readable Indeed. It also is fairly hard (to me at least) to enter a long (longer than 2 operands) sequence into a classic calculator without making a typo. Whenever I need even to just add 4 numbers I don't use a calculator to enter 1 + 2 + 3 + 4 nor a spreadsheet to enter the data in separate cells, select them and see the sum (I used this way until recently) - I open IdeOne.com, choose Common Lisp and enter (+ 1 2 3 4). Needless to day I don't only use it for formulae this simple, it is of great help in complex cases.

mikewarot 3y ago

I had a similar problem a few years ago, when I was making gears (and gear shaped objects) in a machine shop on old gear driven machines. We had most, but not all, of the change gears, and when making Worm or Bevel Gears, you'd often have a ratio, and have to work backwards to figure out a set of gears to get as close as possible to that ratio. I wrote the simplest possible pascal/windows GUI application[1] to simply try all the possible gear combinations, and keep the lowest. I was shocked when it returned an answer in less than a second. I thought for sure I was going to be digging into algorithms like this, but nope... cheap compute saved me. I'd quickly get the gears, and the error in parts per million. I do feel myself getting Nerd Sniped though... must resist. [1] https://github.com/mikewarot/GearFinder https://github.com/mikewarot/GearFinder

I_Byte 3y ago
The GitHub link you posted appears to 404.
- mikewarot 3y ago
  Oops... didn't realize it was private, changed to Public, made GPL 3.0 licensed. and added a screen shot with some directions and created my first ever "release" on github