14 Jun 18:17 2011

## Re: modular arithmetic

Waldek Hebisch <hebisch <at> math.uni.wroc.pl>

2011-06-14 16:17:00 GMT

2011-06-14 16:17:00 GMT

Cheung Matthew G wrote: > I was also wondering if anybody knows how performance in sbcl of > large integer arithmetic compares to performance in gmp. It depends on how large is "large". Multiplying small bignums (about 20 machine words, that is few hundred digits) sbcl is comparable to gmp. On large bignums gmp is much faster. Also, in gmp ratio of time to do division, gcd or integer sqrt to multiplication time is much smaller than in sbcl. In particular at time when I tested it integer sqrt in gmp was faster than sbcl for all sizes (in fact, gmp could compute integer sqrt of small bignum faster than sbcl computed integer sqrt of a fixnum). Recenctly, there was an improvement to integer sqrt in sbcl so result could change, but probably not much. It is possible to use gmp from sbcl, replacing sbcl routines by gmp ones. I did this for FriCAS computer algebra system (in computer algebra speed on large bignums is important). I also created a version of interface to gmp which is independent from FriCAS: http://www.math.uni.wroc.pl/~hebisch/prog/cl-gmp-0.0.tar.bz2 This version has a bug causing wrong results when used with gmp 4.3, but should work fine with gmp-4.2 and gmp-5.0. I have a bugfix, but given apparent lack of interst I did not bother creating new release. However, if you are interested I will create a new version with bugfix included. -- --(Continue reading)