Date: Wed, 18 Nov 2009 13:05:41 -0500 From: Bradley Lucier lucier@math.purdue.edu
By the way this slowdown is due to the 16-bit algorithms which are used to perform the computations without overflowing the fixnums. The C version probably does 32-bit operations, which is at least a factor of 2 faster, and probably more when shifts are involved.
Common Lisp systems are capable of open-coding modular arithmetic up to the machine word width; all you need to do is insert the occasional (LOGAND #xFFFF...) into your usual generic arithmetic expressions. It's unfortunate that no Scheme system -- to my knowledge -- does this. Instead the extent of any abstraction for `fast integers' provided by Scheme systems is fixnums -- to the ridiculous point that they have been formalized in the R6RS.