Bignums?

I am seriously impressed with the speed of the LW Bignum operations. 

I have a bunch of prime number field operators defined on some very big Bignums. For comparison, I coded two versions of a left-to-right modular exponentiation function with squaring and multiplying modulo the prime; one version using NAF (non-adjacent-form) and the other just scanning every bit of the exponent. 

What I found is that my NAF version, which should have 30% fewer multiply operations, on average, is actually marginally slower than just scanning every bit of the exponent and doing modular multiplies and squaring. There is some overhead to produce a NAF encoding. But the speedup from fewer multiplies is outweighed by this overhead. 

In other words, Lisp is doing a better job on its own that with my attempts to help it along.

It would be really interesting to learn more about the quality and capabilities of the Bignum package. Is it, for instance, using Montgomery trees? Is it already using NAF internally for multiplication? There really isn’t much documentation in the ways of Bignum, other than that it just works as expected.

- DM

_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html