3 [clojure.contrib trace test-is]))
6 (defn expmod [base exp m]
7 (rem (fast-expt base exp) m))
10 In the case of the original expmod implementation, square and remainder
11 calls are interspersed, so square always deals with a small number, whereas
12 with the above way, we do a series of squaring and then in the end take
13 remainder. Squaring of big numbers are very inefficient as the CPU has to
14 do multi-byte arithmetic which consumes many cycles.
16 So the new version is several times slower than the original.