"Life is all about sharing. If we are good at something, pass it on." - Mary Berry

### SICP Exercise 1.25: A simpler expmod?

2021-09-30

Categories:

Exercise 1.25: Alyssa P. Hacker complains that we went to a lot of extra work in writing `expmod`. After all, she says, since we already know how to compute exponentials, we could have simply written:

```1(define (expmod base exp m)
2    (remainder (fast-expt base exp) m))
```

Is she correct? Would this procedure serve as well for our fast prime tester? Explain.

First, look at the original algorithm:

``` 1 (define (expmod base exp m)
2     (cond ((= exp 0) 1)
3         ((even? exp)
4             (remainder
5                 (square (expmod base (/ exp 2) m))
6                 m))
7         (else
8             (remainder
9                 (* base (expmod base (- exp 1) m))
10                 m))))
```

Trying to run both:

``` 1\$ racket 1.25-expmod.scm
2>(expmod 2 10 10)
3> (expmod 2 5 10)
4> >(expmod 2 4 10)
5> > (expmod 2 2 10)
6> > >(expmod 2 1 10)
7> > > (expmod 2 0 10)
8< < < 1
9< < <2
10< < 4
11< <6
12< 2
13<4
144
```
```1\$ racket 1.25-expmod-fast-expt.scm
2>(expmod 2 10 10)
3<4
44
```

Looks like she is correct.

But there is a problem: instead of breaking down the problem into smaller numbers, she tries to fully compute `expt` before computing `remainder`.

Let’s see what happens with a large number:

```  1\$ gtime -v racket 1.25-expmod.scm
2>(expmod 2 100000000 100000000)
3> (expmod 2 50000000 100000000)
4> >(expmod 2 25000000 100000000)
5> > (expmod 2 12500000 100000000)
6> > >(expmod 2 6250000 100000000)
7> > > (expmod 2 3125000 100000000)
8> > > >(expmod 2 1562500 100000000)
9> > > > (expmod 2 781250 100000000)
10> > > > >(expmod 2 390625 100000000)
11> > > > > (expmod 2 390624 100000000)
12> > > >[10] (expmod 2 195312 100000000)
13> > > >[11] (expmod 2 97656 100000000)
14> > > >[12] (expmod 2 48828 100000000)
15> > > >[13] (expmod 2 24414 100000000)
16> > > >[14] (expmod 2 12207 100000000)
17> > > >[15] (expmod 2 12206 100000000)
18> > > >[16] (expmod 2 6103 100000000)
19> > > >[17] (expmod 2 6102 100000000)
20> > > >[18] (expmod 2 3051 100000000)
21> > > >[19] (expmod 2 3050 100000000)
22> > > >[20] (expmod 2 1525 100000000)
23> > > >[21] (expmod 2 1524 100000000)
24> > > >[22] (expmod 2 762 100000000)
25> > > >[23] (expmod 2 381 100000000)
26> > > >[24] (expmod 2 380 100000000)
27> > > >[25] (expmod 2 190 100000000)
28> > > >[26] (expmod 2 95 100000000)
29> > > >[27] (expmod 2 94 100000000)
30> > > >[28] (expmod 2 47 100000000)
31> > > >[29] (expmod 2 46 100000000)
32> > > >[30] (expmod 2 23 100000000)
33> > > >[31] (expmod 2 22 100000000)
34> > > >[32] (expmod 2 11 100000000)
35> > > >[33] (expmod 2 10 100000000)
36> > > >[34] (expmod 2 5 100000000)
37> > > >[35] (expmod 2 4 100000000)
38> > > >[36] (expmod 2 2 100000000)
39> > > >[37] (expmod 2 1 100000000)
40> > > >[38] (expmod 2 0 100000000)
41< < < <[38] 1
42< < < <[37] 2
43< < < <[36] 4
44< < < <[35] 16
45< < < <[34] 32
46< < < <[33] 1024
47< < < <[32] 2048
48< < < <[31] 4194304
49< < < <[30] 8388608
50< < < <[29] 44177664
51< < < <[28] 88355328
52< < < <[27] 85987584
53< < < <[26] 71975168
54< < < <[25] 8628224
55< < < <[24] 49394176
56< < < <[23] 98788352
57< < < <[22] 90875904
58< < < <[21] 27817216
59< < < <[20] 55634432
60< < < <[19] 23962624
61< < < <[18] 47925248
62< < < <[17] 95861504
63< < < <[16] 91723008
64< < < <[15] 96568064
65< < < <[14] 93136128
66< < < <[13] 38832384
67< < < <[12] 47123456
68< < < <[11] 5383936
69< < < <[10] 66852096
70< < < < < 39593216
71< < < < <79186432
72< < < < 12890624
73< < < <87109376
74< < < 87109376
75< < <87109376
76< < 87109376
77< <87109376
78< 87109376
79<87109376
8087109376
81	Command being timed: "racket 1.25-expmod.scm"
82	User time (seconds): 0.26
83	System time (seconds): 0.07
84	Percent of CPU this job got: 95%
85	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.35
86	Average shared text size (kbytes): 0
87	Average unshared data size (kbytes): 0
88	Average stack size (kbytes): 0
89	Average total size (kbytes): 0
90	Maximum resident set size (kbytes): 87988
91	Average resident set size (kbytes): 0
92	Major (requiring I/O) page faults: 0
93	Minor (reclaiming a frame) page faults: 27796
94	Voluntary context switches: 0
95	Involuntary context switches: 385
96	Swaps: 0
97	File system inputs: 0
98	File system outputs: 0
99	Socket messages sent: 0
101	Signals delivered: 0
102	Page size (bytes): 4096
103	Exit status: 0
```
``` 1\$ gtime -v racket 1.25-expmod-fast-expt.scm
2>(expmod 2 100000000 100000000)
3<87109376
487109376
5	Command being timed: "racket 1.25-expmod-fast-expt.scm"
6	User time (seconds): 0.37
7	System time (seconds): 0.12
8	Percent of CPU this job got: 96%
9	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.51
10	Average shared text size (kbytes): 0
11	Average unshared data size (kbytes): 0
12	Average stack size (kbytes): 0
13	Average total size (kbytes): 0
14	Maximum resident set size (kbytes): 151672
15	Average resident set size (kbytes): 0
16	Major (requiring I/O) page faults: 0
17	Minor (reclaiming a frame) page faults: 56633
18	Voluntary context switches: 0
19	Involuntary context switches: 439
20	Swaps: 0
21	File system inputs: 0
22	File system outputs: 0
23	Socket messages sent: 0
25	Signals delivered: 0
26	Page size (bytes): 4096
27	Exit status: 0
```

So, her version:

• requires more memory
• slower

Trying with a larger number, it took… > 2 minutes and 10 GB to run:

``` 1\$ gtime -v racket 1.25-expmod-fast-expt.scm
2>(expmod 2 100000000000 100000000000)
3<81787109376
481787109376
5	Command being timed: "racket 1.25-expmod-fast-expt.scm"
6	User time (seconds): 122.83
7	System time (seconds): 99.90
8	Percent of CPU this job got: 86%
9	Elapsed (wall clock) time (h:mm:ss or m:ss): 4:17.10
10	Average shared text size (kbytes): 0
11	Average unshared data size (kbytes): 0
12	Average stack size (kbytes): 0
13	Average total size (kbytes): 0
14	Maximum resident set size (kbytes): 10491416
15	Average resident set size (kbytes): 0
16	Major (requiring I/O) page faults: 0
17	Minor (reclaiming a frame) page faults: 60640485
18	Voluntary context switches: 45
19	Involuntary context switches: 598751
20	Swaps: 0
21	File system inputs: 0
22	File system outputs: 0
23	Socket messages sent: 0