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 details)

Uploaded Source

Built Distribution

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

Uploaded Python 3

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

Hashes for simplefractions-1.2.1.tar.gz
Algorithm Hash digest
SHA256 2214b1a1fad21eb5fb8dc3a1ca540c5a20cca78d03911319f5371c461db70da8
MD5 5447e9a0f7d5ce3bdc320f10ad63373e
BLAKE2b-256 1b524a7c3247c17d136a7a77c2934bc9b6f4ed1e1d884c243ccdcbdac7c429ed

See more details on using hashes here.

File details

Details for the file simplefractions-1.2.1-py3-none-any.whl.

File metadata

File hashes

Hashes for simplefractions-1.2.1-py3-none-any.whl
Algorithm Hash digest
SHA256 766d4397b0dbd2d3822ac0577a0b1bbeb3d6a263ba611945589fb33d68455a81
MD5 53b960a561024ec771a0eda37abbc074
BLAKE2b-256 c1fe308dffcb5ec0d12c15037eb2173867b675f195933251581185f04046a1f7

See more details on using hashes here.

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