Quan Tong
"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: Programming

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
100	Socket messages received: 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
24	Socket messages received: 0
25	Signals delivered: 0
26	Page size (bytes): 4096
27	Exit status: 0

So, her version:

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
24	Socket messages received: 0
25	Signals delivered: 0
26	Page size (bytes): 4096
27	Exit status: 0

References:

Tags: sicp scheme

Edit on GitHub

Related Posts:

Previous
Next