5 ms·

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

by 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.
    - User23 3y ago
      More here: http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/fun_rationalcm_rationalize.html http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec...
    - jgalt212 3y ago
      > Common Lisp gives you this choice (this being HN, a Lisp mention is obligatory :-) Yes, we should probably implement a rule. If a post has 100+ comments, it cannot remain on front page unless at least one that mentions Lisp. dang?
      - TylerE 3y ago
        Leave this meta shit on reddit please. The SNR of this place isn't what it used to be to start with, let's not go out of our way to ADD EVEN MORE noise.
        jgalt212 3y ago
        nice language
    - jameshart 3y ago
      > assuming the float is completely accurate (i.e. every decimal digit after the last internally-represented one is assumed to be 0) Careful though - the float is probably not actually a set of decimal digits but most likely binary ones, so it would be assuming that every binary digit after the last one is zero. Just because you wrote ‘0.1’ in your source code that doesn’t mean you only have a single significant figure in the float in memory. It’s going to be 0.0001100110011… (repeating 0011 to the extent of your float representation’s precision). Although the Common Lisp language doesn’t actually appear to require that the internal float radix be 2 - a floating point decimal type would be valid implementation.
    - a1369209993 3y ago
      > if the underlying float representation is large enough to capture more bits than you specified when you typed in the number. If you typed in `0.142857` (or however IEEE floats are syntaxed), the correct rational is 142857/1000000. If you want to rationalize relative to number of decimal significant digits, that should be something like `(rationalize "0.142857")` or `(rationalize (radix-mp-float 10 '(1 4 2 8 5 7) -1))`.
- colanderman 3y ago
  You might want a simpler representation (smaller denominator) than that will give you. An example is converting musical pitch ratios to simple fractions (e.g. as used in just intonation). Literally yesterday I was writing code to do this. The mediant method works beautifully for this, and it can be optimized further than what's presented in the article.
  - andai 3y ago
    > can be optimized further than what's presented in the article Fascinating, do you have any links about this? Or more generally about the intersection of music, fractions and programming? I found some code in Audacity that detects the notes in audio, I'll see if I can edit this comment later.
    - colanderman 3y ago
      The basic idea to optimize the algorithm (which I got from this [1] SO answer) is to recognize that you only ever update the numerator and denominator of either bound in a linear fashion. So rather than potentially repeatedly update a given bound, you alternate between the two, and use algebra to determine the multiple by which the bound should be updated. Regarding the intersection of fractions and music, "just intonation" is the term you want to research. [1] https://stackoverflow.com/a/45314258 https://stackoverflow.com/a/45314258
eesmith 3y ago
I don't think it's that good. At the very least I implemented it and got different answers for the test case of 0.263157894737 = 5/19 depending on the choice of numerical representation. float64 ended up at 87714233939/333314088968 while decimal and fraction ended up at 87719298244/333333333327. Here is the code. import argparse parser = argparse.ArgumentParser() parser.add_argument("Q", nargs="?", default="0.263157894737") parser.add_argument("--method", choices = ("float", "decimal", "fraction"), default="float") args = parser.parse_args() if args.method == "float": print(f"Using float64 for {args.Q!r}") one = 1.0 Q = float(args.Q) int2float = float elif args.method == "decimal": print(f"Using decimal for {args.Q!r}") import decimal one = decimal.Decimal(1) Q = decimal.Decimal(args.Q) int2float = decimal.Decimal elif args.method == "fraction": print(f"Using fractions for {args.Q!r}") import fractions one = fractions.Fraction(1) Q = fractions.Fraction(args.Q) int2float = fractions.Fraction def to_frac(X): Da = 0 Db = 1 Za = X while 1: Zb = one / (Za - int(Za)) Dc = Db * int(Zb) + Da N = round(X * Dc) frac = N / int2float(Dc) print(f" {N}/{Dc} = {frac} (diff: {X-frac})") if float(N) / float(Dc) == float(X): return (N, Dc) Da, Db = Db, Dc Za = Zb print("solution:", to_frac(Q)) Here's the output for 0.263157894737 % python frac.py 0.263157894737 --method float Using float64 for '0.263157894737' 1/3 = 0.3333333333333333 (diff: -0.0701754385963333) 1/4 = 0.25 (diff: 0.01315789473700002) 4/15 = 0.26666666666666666 (diff: -0.003508771929666643) 5/19 = 0.2631578947368421 (diff: 1.5792922525292852e-13) 87714233939/333314088968 = 0.263157894737 (diff: 0.0) solution: (87714233939, 333314088968) % python frac.py 0.263157894737 --method decimal Using decimal for '0.263157894737' 1/3 = 0.3333333333333333333333333333 (diff: -0.0701754385963333333333333333) 1/4 = 0.25 (diff: 0.013157894737) 4/15 = 0.2666666666666666666666666667 (diff: -0.0035087719296666666666666667) 5/19 = 0.2631578947368421052631578947 (diff: 1.578947368421053E-13) 87719298244/333333333327 = 0.2631578947370000000000030000 (diff: -3.0000E-24) solution: (87719298244, 333333333327) % python frac.py 0.263157894737 --method fraction Using fractions for '0.263157894737' 1/3 = 1/3 (diff: -210526315789/3000000000000) 1/4 = 1/4 (diff: 13157894737/1000000000000) 4/15 = 4/15 (diff: -10526315789/3000000000000) 5/19 = 5/19 (diff: 3/19000000000000) 87719298244/333333333327 = 87719298244/333333333327 (diff: -1/333333333327000000000000) solution: (87719298244, 333333333327) For the pi = 3.14159265359 test case the solutions are all 226883371/72219220 . The sequence diverges at the point marked with "<---- here". Using float64 22/7 = 3.142857142857143 (diff: -0.0012644892671427321) 333/106 = 3.141509433962264 (diff: 8.321962773605307e-05) 355/113 = 3.1415929203539825 (diff: -2.667639824593948e-07) 103993/33102 = 3.1415926530119025 (diff: 5.780975698144175e-10) 104348/33215 = 3.141592653921421 (diff: -3.3142111277584263e-10) 208341/66317 = 3.1415926534674368 (diff: 1.2256329284809908e-10) 312689/99532 = 3.1415926536189365 (diff: -2.893640882462023e-11) 833719/265381 = 3.141592653581078 (diff: 8.922196315097608e-12) 1146408/364913 = 3.141592653591404 (diff: -1.403765992336048e-12) 5419351/1725033 = 3.1415926535898153 (diff: 1.8474111129762605e-13) <---- here 6565759/2089946 = 3.141592653590093 (diff: -9.281464485866309e-14) 11985110/3814979 = 3.141592653589967 (diff: 3.2862601528904634e-14) 18550869/5904925 = 3.1415926535900116 (diff: -1.1546319456101628e-14) 30535979/9719904 = 3.1415926535899943 (diff: 5.773159728050814e-15) 49086848/15624829 = 3.141592653590001 (diff: -8.881784197001252e-16) 226883371/72219220 = 3.14159265359 (diff: 0.0) solution: (226883371, 72219220) For 0.10000000000000002 it gives 562949953421313/5629499534213129 (for float64) or 500000000000000/4999999999999999 (using fractions): Using float64 for '0.10000000000000002' 1/9 = 0.1111111111111111 (diff: -0.011111111111111086) 1/10 = 0.1 (diff: 1.3877787807814457e-17) 562949953421313/5629499534213129 = 0.10000000000000002 (diff: 0.0) solution: (562949953421313, 5629499534213129) Using fractions for '0.10000000000000002' 1/9 = 1/9 (diff: -4999999999999991/450000000000000000) 1/10 = 1/10 (diff: 1/50000000000000000) 500000000000000/4999999999999999 = 500000000000000/4999999999999999 (diff: -1/249999999999999950000000000000000) solution: (500000000000000, 4999999999999999) FWIW, the exact solution is: >>> import fractions >>> fractions.Fraction("0.10000000000000002") Fraction(5000000000000001, 50000000000000000)

by murkle 3y ago

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.
  - User23 3y ago
    More here: http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/fun_rationalcm_rationalize.html http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec...
  - jgalt212 3y ago
    > Common Lisp gives you this choice (this being HN, a Lisp mention is obligatory :-) Yes, we should probably implement a rule. If a post has 100+ comments, it cannot remain on front page unless at least one that mentions Lisp. dang?
    - TylerE 3y ago
      Leave this meta shit on reddit please. The SNR of this place isn't what it used to be to start with, let's not go out of our way to ADD EVEN MORE noise.
      - jgalt212 3y ago
        nice language
  - jameshart 3y ago
    > assuming the float is completely accurate (i.e. every decimal digit after the last internally-represented one is assumed to be 0) Careful though - the float is probably not actually a set of decimal digits but most likely binary ones, so it would be assuming that every binary digit after the last one is zero. Just because you wrote ‘0.1’ in your source code that doesn’t mean you only have a single significant figure in the float in memory. It’s going to be 0.0001100110011… (repeating 0011 to the extent of your float representation’s precision). Although the Common Lisp language doesn’t actually appear to require that the internal float radix be 2 - a floating point decimal type would be valid implementation.
  - a1369209993 3y ago
    > if the underlying float representation is large enough to capture more bits than you specified when you typed in the number. If you typed in `0.142857` (or however IEEE floats are syntaxed), the correct rational is 142857/1000000. If you want to rationalize relative to number of decimal significant digits, that should be something like `(rationalize "0.142857")` or `(rationalize (radix-mp-float 10 '(1 4 2 8 5 7) -1))`.
colanderman 3y ago
You might want a simpler representation (smaller denominator) than that will give you. An example is converting musical pitch ratios to simple fractions (e.g. as used in just intonation). Literally yesterday I was writing code to do this. The mediant method works beautifully for this, and it can be optimized further than what's presented in the article.
- andai 3y ago
  > can be optimized further than what's presented in the article Fascinating, do you have any links about this? Or more generally about the intersection of music, fractions and programming? I found some code in Audacity that detects the notes in audio, I'll see if I can edit this comment later.
  - colanderman 3y ago
    The basic idea to optimize the algorithm (which I got from this [1] SO answer) is to recognize that you only ever update the numerator and denominator of either bound in a linear fashion. So rather than potentially repeatedly update a given bound, you alternate between the two, and use algebra to determine the multiple by which the bound should be updated. Regarding the intersection of fractions and music, "just intonation" is the term you want to research. [1] https://stackoverflow.com/a/45314258 https://stackoverflow.com/a/45314258

eesmith 3y ago

I don't think it's that good. At the very least I implemented it and got different answers for the test case of 0.263157894737 = 5/19 depending on the choice of numerical representation. float64 ended up at 87714233939/333314088968 while decimal and fraction ended up at 87719298244/333333333327. Here is the code. import argparse parser = argparse.ArgumentParser() parser.add_argument("Q", nargs="?", default="0.263157894737") parser.add_argument("--method", choices = ("float", "decimal", "fraction"), default="float") args = parser.parse_args() if args.method == "float": print(f"Using float64 for {args.Q!r}") one = 1.0 Q = float(args.Q) int2float = float elif args.method == "decimal": print(f"Using decimal for {args.Q!r}") import decimal one = decimal.Decimal(1) Q = decimal.Decimal(args.Q) int2float = decimal.Decimal elif args.method == "fraction": print(f"Using fractions for {args.Q!r}") import fractions one = fractions.Fraction(1) Q = fractions.Fraction(args.Q) int2float = fractions.Fraction def to_frac(X): Da = 0 Db = 1 Za = X while 1: Zb = one / (Za - int(Za)) Dc = Db * int(Zb) + Da N = round(X * Dc) frac = N / int2float(Dc) print(f" {N}/{Dc} = {frac} (diff: {X-frac})") if float(N) / float(Dc) == float(X): return (N, Dc) Da, Db = Db, Dc Za = Zb print("solution:", to_frac(Q)) Here's the output for 0.263157894737 % python frac.py 0.263157894737 --method float Using float64 for '0.263157894737' 1/3 = 0.3333333333333333 (diff: -0.0701754385963333) 1/4 = 0.25 (diff: 0.01315789473700002) 4/15 = 0.26666666666666666 (diff: -0.003508771929666643) 5/19 = 0.2631578947368421 (diff: 1.5792922525292852e-13) 87714233939/333314088968 = 0.263157894737 (diff: 0.0) solution: (87714233939, 333314088968) % python frac.py 0.263157894737 --method decimal Using decimal for '0.263157894737' 1/3 = 0.3333333333333333333333333333 (diff: -0.0701754385963333333333333333) 1/4 = 0.25 (diff: 0.013157894737) 4/15 = 0.2666666666666666666666666667 (diff: -0.0035087719296666666666666667) 5/19 = 0.2631578947368421052631578947 (diff: 1.578947368421053E-13) 87719298244/333333333327 = 0.2631578947370000000000030000 (diff: -3.0000E-24) solution: (87719298244, 333333333327) % python frac.py 0.263157894737 --method fraction Using fractions for '0.263157894737' 1/3 = 1/3 (diff: -210526315789/3000000000000) 1/4 = 1/4 (diff: 13157894737/1000000000000) 4/15 = 4/15 (diff: -10526315789/3000000000000) 5/19 = 5/19 (diff: 3/19000000000000) 87719298244/333333333327 = 87719298244/333333333327 (diff: -1/333333333327000000000000) solution: (87719298244, 333333333327) For the pi = 3.14159265359 test case the solutions are all 226883371/72219220 . The sequence diverges at the point marked with "<---- here". Using float64 22/7 = 3.142857142857143 (diff: -0.0012644892671427321) 333/106 = 3.141509433962264 (diff: 8.321962773605307e-05) 355/113 = 3.1415929203539825 (diff: -2.667639824593948e-07) 103993/33102 = 3.1415926530119025 (diff: 5.780975698144175e-10) 104348/33215 = 3.141592653921421 (diff: -3.3142111277584263e-10) 208341/66317 = 3.1415926534674368 (diff: 1.2256329284809908e-10) 312689/99532 = 3.1415926536189365 (diff: -2.893640882462023e-11) 833719/265381 = 3.141592653581078 (diff: 8.922196315097608e-12) 1146408/364913 = 3.141592653591404 (diff: -1.403765992336048e-12) 5419351/1725033 = 3.1415926535898153 (diff: 1.8474111129762605e-13) <---- here 6565759/2089946 = 3.141592653590093 (diff: -9.281464485866309e-14) 11985110/3814979 = 3.141592653589967 (diff: 3.2862601528904634e-14) 18550869/5904925 = 3.1415926535900116 (diff: -1.1546319456101628e-14) 30535979/9719904 = 3.1415926535899943 (diff: 5.773159728050814e-15) 49086848/15624829 = 3.141592653590001 (diff: -8.881784197001252e-16) 226883371/72219220 = 3.14159265359 (diff: 0.0) solution: (226883371, 72219220) For 0.10000000000000002 it gives 562949953421313/5629499534213129 (for float64) or 500000000000000/4999999999999999 (using fractions): Using float64 for '0.10000000000000002' 1/9 = 0.1111111111111111 (diff: -0.011111111111111086) 1/10 = 0.1 (diff: 1.3877787807814457e-17) 562949953421313/5629499534213129 = 0.10000000000000002 (diff: 0.0) solution: (562949953421313, 5629499534213129) Using fractions for '0.10000000000000002' 1/9 = 1/9 (diff: -4999999999999991/450000000000000000) 1/10 = 1/10 (diff: 1/50000000000000000) 500000000000000/4999999999999999 = 500000000000000/4999999999999999 (diff: -1/249999999999999950000000000000000) solution: (500000000000000, 4999999999999999) FWIW, the exact solution is: >>> import fractions >>> fractions.Fraction("0.10000000000000002") Fraction(5000000000000001, 50000000000000000)