-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathex1.26-why-should-square-instead-of-multiply.scm
53 lines (47 loc) · 2.55 KB
/
ex1.26-why-should-square-instead-of-multiply.scm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
;(remainder (square (expmod base (/ exp 2) m)) m)
;(remainder (* base (expmod base (- exp 1) m)) m)
(expmod 2 7 3)
(remainder (* 2 (expmod 2 6 3)) 3)
(remainder (* 2 (remainder (square (expmod 2 3 3)) 3)) 3)
(remainder (* 2 (remainder (square (remainder (* 2 (expmod 2 2 3)) 3)) 3)) 3)
(remainder (* 2 (remainder (square (remainder (* 2 (remainder (square (expmod 2 1 3)) 3)) 3)) 3)) 3)
(remainder (* 2 (remainder (square (remainder (* 2 (remainder (square (remainder (* 2 (expmod 2 0 3)) 3)) 3)) 3)) 3)) 3)
(remainder (* 2 (remainder (square (remainder (* 2 (remainder (square (remainder (* 2 1) 3)) 3)) 3)) 3)) 3)
(remainder (* 2 (remainder (square (remainder (* 2 (remainder (square (remainder 2 3)) 3)) 3)) 3)) 3)
(remainder (* 2 (remainder (square (remainder (* 2 (remainder (square 1) 3)) 3)) 3)) 3)
(remainder (* 2 (remainder (square (remainder (* 2 (remainder 1 3)) 3)) 3)) 3)
(remainder (* 2 (remainder (square (remainder (* 2 1) 3)) 3)) 3)
(remainder (* 2 (remainder (square (remainder 2 3)) 3)) 3)
(remainder (* 2 (remainder (square 1) 3)) 3)
(remainder (* 2 (remainder 1 3)) 3)
(remainder (* 2 1) 3)
(remainder 2 3)
2
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (* (expmod base (/ exp 2) m)
(expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
;(remainder (square (expmod base (/ exp 2) m)) m)
;(remainder (* base (expmod base (- exp 1) m)) m)
(expmod 2 7 3)
(remainder (* 2 (expmod 2 6 3)) 3)
(remainder (* 2 (remainder (* (expmod 2 3 3) (expmod 2 3 3)) 3)) 3)
(remainder (* 2 (remainder (* (remainder (* 2 (* (remainder (* 2 (expmod 2 0 3)) 3) (remainder (* 2 (expmod 2 0 3)) 3))) 3) (remainder (* 2 (* (remainder (* 2 (expmod 2 0 3)) 3) (remainder (* 2 (expmod 2 0 3)) 3))) 3)) 3)) 3)
(remainder (* 2 (remainder (* (remainder (* 2 (* (remainder (* 2 1) 3) (remainder (* 2 1) 3))) 3) (remainder (* 2 (* (remainder (* 2 1) 3) (remainder (* 2 1) 3))) 3)) 3)) 3)
(remainder (* 2 (remainder (* (remainder (* 2 (* (remainder 2 3) (remainder 2 3))) 3) (remainder (* 2 (* (remainder 2 3) (remainder 2 3))) 3)) 3)) 3)
;(remainder (* 2 (remainder (square (remainder (* 2 (remainder (square (remainder (* 2 (expmod 2 0 3)) 3)) 3)) 3)) 3)) 3)
; Explaination: with square, we'd only calc a branch of calcuations once, then double once
; However with (* ? ?), we'd calc twice, then double once, no calcuation got reduced