Skip to main content

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 float x, the unique simplest fraction with the property that float(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

simplefractions-1.2.1.tar.gz (288.0 kB view hashes)

Uploaded Source

Built Distribution

simplefractions-1.2.1-py3-none-any.whl (14.5 kB view hashes)

Uploaded Python 3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page