slavapestov/factor — pull request #487 by mrjbq7 (2012-04-03 01:17:54+00:00)
Title: Bignum GCD

This speeds up issue #158 (https://github.com/slavapestov/factor/issues/158) a lot.

For this test case:

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

Running `[ 0.001 find-pi-to ] time` goes from 2.5 seconds to 0.215 seconds.

Here is a table showing the speedups for computing GCD of various lengths of bignums (from 1 to 20 times faster):

```
a_digits b_digits g_digits n_trials bignum-gcd math-gcd factor
-------- -------- -------- -------- ---------- -------- ------
1 1 0 100000 0.038270 0.024972 0.652512
2 2 0 100000 0.029419 0.057863 1.966896
4 4 0 100000 0.036373 0.089657 2.464946
7 7 0 100000 0.043515 0.137342 3.156182
10 10 0 10000 0.004157 0.017680 4.252964
20 20 0 10000 0.010288 0.058567 5.692786
50 50 0 10000 0.028973 0.196914 6.796366
100 100 0 1000 0.006556 0.047692 7.274785
1000 1000 0 1000 0.111792 1.366981 12.227924
10000 10000 0 100 0.432002 9.201324 21.299281

Lopsided gcds
-------------
20 100 0 100 0.000187 0.000612 3.272561
100 20 0 100 0.000167 0.000602 3.597419
1000 3 0 100 0.000222 0.000265 1.190539
3 1000 0 100 0.000226 0.000256 1.136800
10000 1 0 100 0.001457 0.001418 0.973076
1 10000 0 100 0.001618 0.001579 0.975484
500 400 0 100 0.005192 0.032162 6.194007
400 500 0 100 0.005039 0.035240 6.992855

Large gcd
---------
10 10 10 1000 0.000968 0.003875 4.001718
20 20 20 1000 0.001710 0.010469 6.123179
100 100 100 1000 0.008357 0.075967 9.090596
```

Only real downside seems to be that Lehmer GCD doesn't preserve the "a" value that our current GCD supports (calculated such that `a * y + b * x = d`). That means it can't replace the current `gcd` word, so I made a `fast-gcd` that is used for ratio math and `lcm`.

Thoughts?