From: Nikodemus Siivola <nikodemus@ra...>  20110614 08:41:04

On 14 June 2011 02:13, Cheung, Matthew G <mgcheung@...> wrote: > I was wondering if sbcl does any optimisations when performing modular arithmetic. I > have written some code that does elliptic curve operations and I was trying to see if I > could improve performance by implementing any of the algorithms designed to improve > performance of modular operations such as fast reductions for NIST primes. What I have > written appears to be correct since it agrees with the built in mod operator, but it > actually takes longer. Is it worth my effort to try to use algorithms to improve > performances of modular operations? As far as I can tell, that should be the major > bottleneck for elliptic curve operations as I've implemented them. If your you're operating modulo poweroftwo, SBCL should do very well  assuming you can convey your intention to it. Have you read: http://www.sbcl.org/manual/#Modulararithmetic ? Looking at it, it isn't actually quite right about the state of the game since these days (defun foo (x y) (declare (fixnum x y)) (logand mostpositivefixnum (+ x y))) compiles quite nicely, and while (defun foo (x y) (declare (type (unsignedbyte 16) x)) (ldb (byte 16 0) (+ x y))) does get compiled with an AND, it isn't half bad either. Important things: 1. Declare argument types. 2. Use LOGAND or LDB to cut the result to the right width. If you need signed modular arithmetic, you need to use SBC::MASKSIGNEDFIELD to cut the result. > I was also wondering if anybody knows how performance in sbcl of large integer > arithmetic compares to performance in gmp. Thank you. In some cases SBCL is neck to neck, in others gmp beats us by a mile. (Yes, making SBCL use gmp has been considered, and is still in the books. Mostly we're just hesistant about adding a build dependency, and depending on nonPD / BSD / MIT licenced code  so it will probably be a build option at some point.) Cheers,  Nikodemus 