Faster Big Ratios!
Thursday, April 5, 2012
Specifically, we defined this estimation function to find
pi as a
:: 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
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
degrading particularly due to the (relatively) expensive calculation of
“mod” for bignum’s.
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.