## Faster Big Ratios!

Thursday, April 5, 2012

While working on a post about approximating pi, I noticed that the performance of Factor’s large rational numbers was less than stellar.

Specifically, we defined this estimation function to find `pi`

as a
rational
number:

```
:: find-pi-to ( accuracy -- n approx )
1 4 [
over [ 2 * 1 + ] [ odd? [ neg ] when ] bi
4 swap / [ + ] keep
abs accuracy >= [ 1 + ] 2dip
] loop ;
```

Using this for an accuracy of `0.001`

was incredibly slow:

```
IN: scratchpad [ 0.001 find-pi-to ] time
Running time: 1.692090043 seconds
```

### Bignum

In Factor, large integers are stored as arbitrary-precision “bignums”. Similar to other languages such as Python and Scheme, Factor stores these numbers as a sequence of large (either 30-bit or 62-bit) digits, and then performs math on this sequence of digits.

It turns out that most of the ratios has both a bignum numerator and bignum denominator. For most basic math operation on ratios, Factor would compute the greatest common divisor to produce a normalized fraction (e.g., 6/4 would become 3/2).

For an accuracy of `0.001`

in this example, the denominator had more
than 1,700 digits in base 10. As these numbers grew, the performance of
Euclid’s GCD
algorithm began
degrading particularly due to the (relatively) expensive calculation of
“mod” for bignum’s.

### Lehmer GCD

I noticed a Python bug report that
suggested addressing a similar performance problem for their rational
number implementation (in `fractions.py`

) by implementing Lehmer’s GCD
algorithm.

After implementing a bignum-gcd primitive that used Lehmer’s GCD, I created a fast-gcd word that used this for bignum’s and the current gcd word for other real numbers.

Performance improvement was impressive! After recompiling with these patches, our original test case takes less than 10% of the time!

```
IN: scratchpad [ 0.001 find-pi-to ] time
Running time: 0.156713844 seconds
```

You can find this in the latest development version of Factor.