SICP Exercises 1.22-24 are Somewhat Out of Date

(This is the point where I broke down and finally started using Scheme.  Going without my Emacs shortcuts in DrScheme is painful, but the IDE-like environment is probably a lot more friendly to the raw recruits.  I’m as of yet too lazy to russle up SLIME48/Scheme48 for now and just want for finish some problems….)

Starting with exercise 1.22 in SICP, we are given code with a reference to “runtime.” This does not exist in the MzScheme language I was using under DrScheme…. Thanks to a quick tip from Sridhar Ratnakumar, I didn’t have to bang my head against the wall figuring this out. By defining runtime thusly, (define (runtime) (current-milliseconds)), the code from SICP will run as-is.

One of the first things we have to do here is to write a procedure search-for-primes that “checks the primality of consecutive odd integers in a specified range.” If you think in Basic, you’ll probably want a FOR-NEXT loop for this. Or if you’re really hip, you might want a DO-UNTIL loop. I looked at some options for doing that, but I have to admit that a recursively defined iterative function is much simpler. Much simpler than trying to keep track of yet-another-language’s control construct syntax….

Exercise 1.22 asks us to compare the runtimes of our prime checker for the ranges of 1000 to 1,000,000. On my machine, these came back as taking 0 milleseconds– apparently my box is a little faster than the ones running back in the eighties. I started my comparison at 100,000,000… and did a quick munge to make the code only give output when we actually hit a prime. We can see the output of my code below. Each time my range goes up by a factor of 10, we expect the time it takes to find the prime to increase by about SQRT(10) or 3.1622. Is that what’s happening here?  (Here’s my code file if you want to try this at home.)

> (search-for-primes 100000000 100)

100000007 *** 0
100000037 *** 0
100000039 *** 15
100000049 *** 0
100000073 *** 16
100000081 *** 0
> (search-for-primes 1000000000 100)

1000000007 *** 16
1000000009 *** 16
1000000021 *** 31
1000000033 *** 16
1000000087 *** 16
1000000093 *** 15
1000000097 *** 32
> (search-for-primes 10000000000 100)

10000000019 *** 141
10000000033 *** 313
10000000061 *** 140
10000000069 *** 156
10000000097 *** 312
> (search-for-primes 100000000000 100)

100000000003 *** 656
100000000019 *** 641
100000000057 *** 656
100000000063 *** 656
100000000069 *** 656
100000000073 *** 656
100000000091 *** 672
> (search-for-primes 1000000000000 100)

1000000000039 *** 2656
1000000000061 *** 2281
1000000000063 *** 2124
1000000000091 *** 2124
> (sqrt 10)
3.1622776601683795
> (* 16 (sqrt 10))
50.59644256269407
> (* 32 (sqrt 10))
101.19288512538814
> (* 140 (sqrt 10))
442.71887242357315
> (* 313 (sqrt 10))
989.7929076327027
> (* 656 (sqrt 10))
2074.454145070457

Just eyeballing it here, it appears that as we get further down the list, the closer the time factor gets to SQRT(10).

Let’s try that last one a few more times to see if there’s any variation:

> (search-for-primes 1000000000000 100)

1000000000039 *** 1968
1000000000061 *** 1937
1000000000063 *** 1969
1000000000091 *** 1922
> (search-for-primes 1000000000000 100)

1000000000039 *** 1937
1000000000061 *** 1968
1000000000063 *** 1937
1000000000091 *** 1984

> (search-for-primes 1000000000000 100)

1000000000039 *** 1953
1000000000061 *** 1999
1000000000063 *** 1968
1000000000091 *** 1999

Okay… so we’re pushing 2000 now for these primes. Go up another order of magnitude and we should get around 6000 or so.
> (search-for-primes 10000000000000 100)

10000000000037 *** 6280
10000000000051 *** 6217
10000000000099 *** 6311
> (search-for-primes 10000000000000 100)

10000000000037 *** 6326
10000000000051 *** 6670
10000000000099 *** 6295

Allright! Spot on. Now let’s try it with the changes suggested in Excercise 1-23.

> (search-for-primes 10000000000000 100)

10000000000037 *** 3374
10000000000051 *** 3546
10000000000099 *** 3389
> (search-for-primes 10000000000000 100)

10000000000037 *** 3375
10000000000051 *** 3358
10000000000099 *** 3531

And it looks like we’re not quite halving the time it takes to solve the problems now…. Nice.

Moving on to Exercise 1-24… we end up with problems. The random number generator expects numbers just within a certain range– and because our machine is running so fast, we’ve bumped things up to some *really* large numbers….

random: expects argument of type <exact integer in [1, 2147483647]>; given 9999999999999

Another problem we have is that the compiler doesn’t grok our true and false constants. We need to change the code in start-prime-test to use fast-prime? to use #t and #f instead.

Let’s run our code without fast-prime? for the upper bound of our random number generator.

> (search-for-primes 2147483547 100)

2147483549 *** 32
2147483563 *** 31
2147483579 *** 31
2147483587 *** 31
2147483629 *** 32
2147483647 *** 31

And now let’s try it with fast-prime? with the number of Fermat tests being run 100 times for each prime.

> (search-for-primes 2147483547 100)

2147483549 *** 0
2147483563 *** 16
2147483579 *** 15
2147483587 *** 0
2147483629 *** 16
2147483647 *** 16

Even with that insane amount of tests, we can identify the primes in either half the time or instantaneously. Let’s shift the number of Fermat tests down to 10 and see if there’s much difference.

> (search-for-primes 2147483547 100)

2147483549 *** 0
2147483563 *** 0
2147483579 *** 0
2147483587 *** 0
2147483629 *** 0
2147483647 *** 0

We get the same results… but all are practically instantaneous now.

I don’t think I have enough information to give a really good answer to Exercise 1.24, but it’s clear that log(n) growth is the way to go if you can manage it. The fact that you have to choose the number of Fermat tests to run adds some additional complexity to the question… and the combination of a fast computer with a limited random number generator makes it difficult to determine what’s going on here experimentally.

Advertisements

5 Responses to “SICP Exercises 1.22-24 are Somewhat Out of Date”

  1. Eli Says:

    Yep, had this problem too – so I ran the tests in a loop, which gave a pretty good picture of what’s going on:

    http://eli.thegreenplace.net/2007/07/09/sicp-section-126/

  2. Stairmaster Says:

    By the way, instead of
    (define (runtime) (current-milliseconds))
    you can use
    (define runtime current-milliseconds)

    The subtle difference is that this creates an alias for current-milliseconds (taking advantage of the fact that functions are first class objects in Scheme), instead of creating a new function which calls current-milliseconds and returns its value unchanged.

    Which doesn’t change anything really (except possibly execution speed) but you can’t do it the second way in C++ 😉

  3. Prahlad Kamal Joshi Says:

    i got these results
    (search-for-primes-odd 100000000000000 100000000000110) ;;;around 11thousands using exercise 1.23 and around 67thousand milliseconds using program of exercise 1.22

  4. Michael M Says:

    Nice work! I was just running into the same problems myself, and it was great to find this well-reasoned response to a slightly flawed question-set. By the way, I’ve heard that MIT has updated their course to use python instead of lisp now…

  5. lispy Says:

    Thanks. It’s been a while since I looked at this; I’m glad if this saved you some grief.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: