rational approximation with bounded denominator
2024-04-23 16:12:51 -04:00
2024-04-23 16:12:51 -04:00
2024-04-23 16:12:51 -04:00
2016-09-23 01:43:23 -04:00
2016-09-23 01:43:23 -04:00
2020-05-13 17:16:25 -04:00
2020-05-13 17:16:25 -04:00
2017-04-29 13:32:07 -04:00
2020-05-13 17:16:25 -04:00
2015-04-21 21:14:03 -07:00
2015-04-21 21:14:03 -07:00
2018-02-20 15:57:28 -05:00
2018-01-19 00:03:42 -05:00
2017-04-29 13:32:07 -04:00
2024-04-23 16:12:51 -04:00
2024-04-23 16:12:51 -04:00
2024-04-23 16:12:51 -04:00
2018-02-20 15:57:28 -05:00
2018-01-19 00:03:42 -05:00
2019-10-10 18:33:06 -04:00
2024-04-23 16:12:51 -04:00
2024-04-23 16:12:51 -04:00
2024-04-23 16:12:51 -04:00
2018-02-20 15:57:28 -05:00
2015-05-04 23:19:23 -07:00
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