Find the simplest fraction for a given float or interval
Project description
The simplefractions package finds the simplest fraction that converts to a given float, or more generally, the simplest fraction that lies within a given interval.
Definition. Given fractions x = a/b and y = c/d (written in lowest terms with positive denominators), say that x is simpler than y if abs(a) <= abs(c), b <= d, and at least one of these two inequalities is strict.
For example, 22/7 is simpler than 23/8, but neither of 3/8 and 4/7 is simpler than the other.
Then it's a theorem that given any subinterval I of the real line that contains at least one fraction, that interval contains a unique simplest fraction. That is, there's a fraction a/b in I such that a/b is simpler (in the above sense) than all other fractions in I. As a consequence, for any given finite Python float x, there's a unique simplest fraction that rounds to that float.
The simplefractions package provides two functions:
simplest_from_float
returns, for a given floatx
, the unique simplest fraction with the property thatfloat(simplest_from_float(x)) == x
.simplest_in_interval
returns the unique simplest fraction in a given (open or closed, bounded or unbounded) nonempty interval.
Example usage
Start by importing the functions from the module:
>>> from simplefractions import *
The simplest_from_float
function takes a single finite float x
and
produces a Fraction
object that recovers that float:
>>> simplest_from_float(0.25)
Fraction(1, 4)
>>> simplest_from_float(0.33)
Fraction(33, 100)
No matter what x
is given, the invariant float(simplest_from_float(x)) == x
will always be true.
>>> x = 0.7429667872099244
>>> simplest_from_float(x)
Fraction(88650459, 119319545)
>>> float(simplest_from_float(x))
0.7429667872099244
>>> float(simplest_from_float(x)) == x
True
If the float x
was constructed by dividing two small integers, then
more often than not, simplest_from_float
will recover those integers:
>>> x = 231 / 199
>>> x
1.1608040201005025
>>> simplest_from_float(x)
Fraction(231, 199)
More precisely, if x
was constructed by dividing two relatively prime
integers smaller than or equal to 67114657
in absolute value,
simplest_from_float
will recover those integers.
>>> simplest_from_float(64841043 / 66055498)
Fraction(64841043, 66055498)
But 67114657
is the best we can do here:
>>> simplest_from_float(67114658 / 67114657)
Fraction(67114657, 67114656)
In larger cases, simplest_from_float
might discover a simpler fraction
that gives the same float:
>>> x = 818421477165 / 1580973145504
>>> simplest_from_float(x)
Fraction(5171, 9989)
>>> 818421477165 / 1580973145504 == 5171 / 9989
True
Note that simplest_from_float
does not magically fix floating-point
inaccuracies. For example:
>>> x = 1.1 + 2.2
>>> simplest_from_float(x)
Fraction(675539944105597, 204709073971393)
You might have expected Fraction(33, 10)
here, but when converted to float,
that gives a value very close to, but not exactly equal to, x
. In contrast,
the return value of simplest_from_float(x)
will always produce exactly x
when converted to float
.
To fix this, you might want to ask for the simplest float that lies within
some small error bound of x
- for example, within 5 ulps (units in the
last place) in either direction. simplest_from_float
can't do that, but
simplest_in_interval
can! For example
>>> from math import ulp
>>> x = 1.1 + 2.2
>>> simplest_in_interval(x - 5*ulp(x), x + 5*ulp(x))
Fraction(33, 10)
Alternatively, you might ask for the simplest fraction approximating x
with a relative error of at most 0.000001:
>>> relerr = 1e-6
>>> simplest_in_interval(x - relerr*x, x + relerr*x)
Fraction(33, 10)
Here are some more examples of simplest_in_interval
at work. The inputs
to simplest_in_interval
can be floats, integers, or Fraction
objects.
>>> simplest_in_interval(3.14, 3.15)
Fraction(22, 7)
By default, simplest_in_interval
assumes that you're specifying an
open interval:
>>> simplest_in_interval(3, 4)
Fraction(7, 2)
Keyword arguments include_left
and include_right
allow you to specify
that one or both endpoints should be included in the interval:
>>> simplest_in_interval(3, 4, include_left=True, include_right=True)
Fraction(3, 1)
The left and right endpoints of the interval are also both optional, alowing a semi-infinite or infinite interval to be specified:
>>> simplest_in_interval(right=4) # simplest in (-inf, 4)
Fraction(0, 1)
>>> simplest_in_interval(left=4, include_left=True) # simplest in [4, inf)
Fraction(4, 1)
>>> simplest_in_interval() # simplest in (-inf, inf)
Fraction(0, 1)
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
File details
Details for the file simplefractions-1.2.1.tar.gz
.
File metadata
- Download URL: simplefractions-1.2.1.tar.gz
- Upload date:
- Size: 288.0 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.1 CPython/3.10.6
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2214b1a1fad21eb5fb8dc3a1ca540c5a20cca78d03911319f5371c461db70da8 |
|
MD5 | 5447e9a0f7d5ce3bdc320f10ad63373e |
|
BLAKE2b-256 | 1b524a7c3247c17d136a7a77c2934bc9b6f4ed1e1d884c243ccdcbdac7c429ed |
File details
Details for the file simplefractions-1.2.1-py3-none-any.whl
.
File metadata
- Download URL: simplefractions-1.2.1-py3-none-any.whl
- Upload date:
- Size: 14.5 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.1 CPython/3.10.6
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 766d4397b0dbd2d3822ac0577a0b1bbeb3d6a263ba611945589fb33d68455a81 |
|
MD5 | 53b960a561024ec771a0eda37abbc074 |
|
BLAKE2b-256 | c1fe308dffcb5ec0d12c15037eb2173867b675f195933251581185f04046a1f7 |