rational approximation with bounded denominator
Go to file
SheetJS 9a9ed4d1fa version bump 1.0.2: cleanup
- cont: more direct reverse iteration
- README cleanup
- python linting and tests
2015-05-04 23:19:23 -07:00
dist version bump 1.0.2: cleanup 2015-05-04 23:19:23 -07:00
misc version bump 1.0.1: cleanup and python 2015-04-21 21:14:03 -07:00
test_files version bump 0.3.1: handling numbers >= 2**32 2014-01-12 01:44:07 -05:00
.flowconfig version bump 1.0.1: cleanup and python 2015-04-21 21:14:03 -07: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.0.1: cleanup and python 2015-04-21 21:14:03 -07:00
.travis.yml version bump 1.0.1: cleanup and python 2015-04-21 21:14:03 -07:00
frac.flow.js version bump 1.0.2: cleanup 2015-05-04 23:19:23 -07:00
frac.js version bump 1.0.2: cleanup 2015-05-04 23:19:23 -07:00
frac.md version bump 1.0.2: cleanup 2015-05-04 23:19:23 -07:00
frac.py version bump 1.0.2: cleanup 2015-05-04 23:19:23 -07:00
index.html version bump 1.0.1: cleanup and python 2015-04-21 21:14:03 -07:00
LICENSE version bump 1.0.1: cleanup and python 2015-04-21 21:14:03 -07:00
Makefile version bump 1.0.2: cleanup 2015-05-04 23:19:23 -07:00
package.json version bump 1.0.2: cleanup 2015-05-04 23:19:23 -07:00
README version bump 1.0.1: cleanup and python 2015-04-21 21:14:03 -07:00
README.md version bump 1.0.2: cleanup 2015-05-04 23:19:23 -07:00
setup.py version bump 1.0.2: cleanup 2015-05-04 23:19:23 -07:00
test_all.py version bump 1.0.2: cleanup 2015-05-04 23:19:23 -07:00
test.js version bump 1.0.2: cleanup 2015-05-04 23:19:23 -07: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".

Installation

JS

With npm:

$ npm install frac

In the browser:

<script src="frac.js"></script>

The script will manipulate module.exports if available (e.g. in a CommonJS require context). 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 ]
>>> frac.med(1.3, 9, True)   # [  1,  2, 7 ]
>>> frac.med(-1.3, 9)        # [  0, -9, 7 ]
>>> frac.med(-1.3, 9, True)  # [ -2,  5, 7 ]

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

Testing

make test will run the node-based tests.

Tests generated from Excel have 4 columns. To produce a similar test:

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

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.

Badges

Build Status

Coverage Status

Analytics