rational approximation with bounded denominator
Go to file
2024-04-23 16:12:51 -04:00
ctest version bump 1.1.3 2024-04-23 16:12:51 -04:00
dist version bump 1.1.3 2024-04-23 16:12:51 -04:00
misc version bump 1.0.5: adjusting tolerance 2016-09-23 01:43:23 -04:00
test_files version bump 1.0.5: adjusting tolerance 2016-09-23 01:43:23 -04:00
types update dev deps and tooling 2020-05-13 17:16:25 -04:00
.eslintrc update dev deps and tooling 2020-05-13 17:16:25 -04:00
.flowconfig version bump 1.0.6: module cleanup 2017-04-29 13:32:07 -04:00
.gitignore update dev deps and tooling 2020-05-13 17:16:25 -04:00
.jscs.json version bump 1.0.1: cleanup and python 2015-04-21 21:14:03 -07:00
.jshintrc version bump 1.0.1: cleanup and python 2015-04-21 21:14:03 -07:00
.npmignore version bump 1.1.2: node module cleanup [ci skip] 2018-02-20 15:57:28 -05:00
.spelling version bump 1.1.1: infrastructure 2018-01-19 00:03:42 -05:00
.travis.yml version bump 1.0.6: module cleanup 2017-04-29 13:32:07 -04:00
frac.flow.js version bump 1.1.3 2024-04-23 16:12:51 -04:00
frac.js version bump 1.1.3 2024-04-23 16:12:51 -04:00
frac.md version bump 1.1.3 2024-04-23 16:12:51 -04:00
frac.py version bump 1.1.2: node module cleanup [ci skip] 2018-02-20 15:57:28 -05:00
index.html version bump 1.1.1: infrastructure 2018-01-19 00:03:42 -05:00
LICENSE License text 2019-10-10 18:33:06 -04:00
Makefile version bump 1.1.3 2024-04-23 16:12:51 -04:00
package.json version bump 1.1.3 2024-04-23 16:12:51 -04:00
README.md version bump 1.1.3 2024-04-23 16:12:51 -04:00
setup.py version bump 1.1.2: node module cleanup [ci skip] 2018-02-20 15:57:28 -05:00
test_all.py version bump 1.0.2: cleanup 2015-05-04 23:19:23 -07:00
test.js version bump 1.1.3 2024-04-23 16:12:51 -04:00

frac

Rational approximation to a floating point number with bounded denominator.

Uses the Mediant Method.

This module also provides an implementation of the continued fraction method as described by Aberth in "A method for exact computation with rational numbers". The algorithm is used in SheetJS Libraries to replicate fraction formats.

Installation

JS

For NodeJS:

$ npm i --save https://cdn.sheetjs.com/frac-1.1.3/frac-1.1.3.tgz

In the browser:

<script src="https://cdn.sheetjs.com/frac-1.1.3/package/dist/frac.min.js"></script>

The script will manipulate module.exports if available . This is not always desirable. To prevent the behavior, define DO_NOT_EXPORT_FRAC

Python

From PyPI:

$ pip install frac

Usage

In all cases, the relevant function takes 3 arguments:

  • x the number we wish to approximate
  • D the maximum denominator
  • mixed if true, return a mixed fraction; if false, improper

The return value is an array of the form [quot, num, den] where quot==0 for improper fractions. quot <= x for mixed fractions, which may lead to some unexpected results when rendering negative numbers.

JS

The exported frac function implements the Mediant method.

frac.cont implements the Aberth algorithm

For example:

> // var frac = require('frac'); // uncomment this line if in node
> frac(1.3, 9);              // [  0,  9, 7 ] //  1.3 ~       9/7
> frac(1.3, 9, true);        // [  1,  2, 7 ] //  1.3 ~  1 +  2/7
> frac(-1.3, 9);             // [  0, -9, 7 ] // -1.3 ~      -9/7
> frac(-1.3, 9, true);       // [ -2,  5, 7 ] // -1.3 ~ -2 +  5/7

> frac.cont(1.3, 9);         // [  0,  4, 3 ] //  1.3 ~       4/3
> frac.cont(1.3, 9, true);   // [  1,  1, 3 ] //  1.3 ~  1 +  1/3
> frac.cont(-1.3, 9);        // [  0, -4, 3 ] // -1.3 ~      -4/3
> frac.cont(-1.3, 9, true);  // [ -2,  2, 3 ] // -1.3 ~ -2 +  2/3

Python

frac.med implements Mediant method.

frac.cont implements Aberth algorithm.

For example:

>>> import frac
>>> frac.med(1.3, 9)         ## [  0,  9, 7 ] ##  1.3 ~       9/7
>>> frac.med(1.3, 9, True)   ## [  1,  2, 7 ] ##  1.3 ~  1 +  2/7
>>> frac.med(-1.3, 9)        ## [  0, -9, 7 ] ## -1.3 ~      -9/7
>>> frac.med(-1.3, 9, True)  ## [ -2,  5, 7 ] ## -1.3 ~ -2 +  5/7

>>> frac.cont(1.3, 9)        ## [  0,  4, 3 ] ##  1.3 ~       4/3
>>> frac.cont(1.3, 9, True)  ## [  1,  1, 3 ] ##  1.3 ~  1 +  1/3
>>> frac.cont(-1.3, 9)       ## [  0, -4, 3 ] ## -1.3 ~      -4/3
>>> frac.cont(-1.3, 9, True) ## [ -2,  2, 3 ] ## -1.3 ~ -2 +  2/3

Testing

The test TSV baselines in the test_files directory have four columns:

  • Column A contains the raw values
  • Column B format "Up to one digit (1/4)" (denominator = 9)
  • Column C format "Up to two digits (21/25)" (denominator = 99)
  • Column D format "Up to three digits (312/943)" (denominator = 999)

make test will run the node-based tests.

make ctest will use browserify to build a standalone script that can be run in the web browser. The transform brfs must be installed locally. Browser test script built against browserify@16.5.1 and brfs@2.0.2.

make pytest will run the python tests against the system Python version.

make pypytest will run the python tests against pypy if installed

License

Please consult the attached LICENSE file for details. All rights not explicitly granted by the Apache 2.0 License are reserved by the Original Author.