README.md 3.99 KB
Newer Older
bovornsiriampairat committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
# frac

Rational approximation to a floating point number with bounded denominator.

Uses the [Mediant Method](https://en.wikipedia.org/wiki/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 <a href="http://sheetjs.com">SheetJS Libraries</a> to
replicate fraction formats.

## Installation

### JS

With [`npm`](https://www.npmjs.org/package/frac):

```bash
$ npm install frac
```

In the browser:

```html
<script src="frac.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`](https://pypi.python.org/pypi/frac):

```bash
$ 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:

```js
> // 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:

```py
>>> 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 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.

## Badges

[![Build Status](https://saucelabs.com/browser-matrix/frac.svg)](https://saucelabs.com/u/frac)

[![Build Status](https://travis-ci.org/SheetJS/frac.svg?branch=master)](https://travis-ci.org/SheetJS/frac)

[![Coverage Status](http://img.shields.io/coveralls/SheetJS/frac/master.svg)](https://coveralls.io/r/SheetJS/frac?branch=master)

[![NPM Downloads](https://img.shields.io/npm/dt/frac.svg)](https://npmjs.org/package/frac)

[![Dependencies Status](https://david-dm.org/sheetjs/frac/status.svg)](https://david-dm.org/sheetjs/frac)

[![ghit.me](https://ghit.me/badge.svg?repo=sheetjs/js-xlsx)](https://ghit.me/repo/sheetjs/js-xlsx)

[![Analytics](https://ga-beacon.appspot.com/UA-36810333-1/SheetJS/frac?pixel)](https://github.com/SheetJS/frac)