1 
(inpackage :clutilities)

2 

3 
;; This is portable Common Lisp, but implementationspecific code may

4 
;; improve performance considerably.

5 
(defun exptmod (n exponent modulus)

6 
"As (mod (expt n exponent) modulus), but more efficient."

7 
(declare (optimize (speed 3) (safety 0) (space 0) (debug 1)))

8 
;; It's much faster on SBCL and ACL to use the simple method, and

9 
;; trust the compiler to optimize it. This may be the case on other

10 
;; Lisp implementations as well.

11 
#+(or sbcl allegro) (mod (expt n exponent) modulus)

12 
#(or sbcl allegro)

13 
(if (some (complement #'integerp) (list n exponent modulus))

14 
(mod (expt n exponent) modulus)

15 
(loop with result = 1

16 
for i oftype fixnum from 0 below (integerlength exponent)

17 
for sqr = n then (mod (* sqr sqr) modulus)

18 
when (logbitp i exponent) do

19 
(setf result (mod (* result sqr) modulus))

20 
finally (return result))))

21 

22 
;; If the compiler is going to expand compiler macros, we should

23 
;; directly inline the simple expansion; this lets the compiler do all

24 
;; sorts of fancy optimizations based on type information that

25 
;; wouldn't be used to optimize the normal EXPTMOD function.

26 
#+(or sbcl allegro)

27 
(definecompilermacro exptmod (n exponent modulus)

28 
`(mod (expt ,n ,exponent) ,modulus))

29 

30 

31 
;; Here's some benchmarking code that may be useful. I probably

32 
;; completely wasted my time declaring ITERATIONS to be a fixnum.

33 
#+nil

34 
(defun test (&optional (iterations 50000000))

35 
(declare (optimize (speed 3) (safety 0) (space 0) (debug 1))

36 
(fixnum iterations))

37 
(time (loop repeat iterations do (mod (expt 12 34) 235)))

38 
(time (loop repeat iterations do (exptmod 12 34 235))))
