/[cl-utilities]/cl-utilities/expt-mod.lisp
ViewVC logotype

Contents of /cl-utilities/expt-mod.lisp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.3 - (show annotations)
Mon Nov 28 21:45:49 2005 UTC (8 years, 4 months ago) by pscott
Branch: MAIN
CVS Tags: HEAD
Changes since 1.2: +18 -17 lines
Fixed a bug in extremum and added new EXTREMA and N-MOST-EXTREME functions
based on feedback from Tobias Rittweiller. Improved docstrings.
Added more tests. Added ACL optimization to EXPT-MOD.
1 (in-package :cl-utilities)
2
3 ;; This is portable Common Lisp, but implementation-specific code may
4 ;; improve performance considerably.
5 (defun expt-mod (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 of-type fixnum from 0 below (integer-length 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 EXPT-MOD function.
26 #+(or sbcl allegro)
27 (define-compiler-macro expt-mod (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 (expt-mod 12 34 235))))

  ViewVC Help
Powered by ViewVC 1.1.5