SICP 1.2 exercises cont. 10

1.22

(define (search-for-primes current largest)
  (cond ((< current largest)
         (if (not ( even? current))
             (timed-prime-test current))
         (search-for-primes (+ 1 current) largest)))
)

for greater than 1,000,000,000 …

1000000001
1000000003
1000000005
1000000007 *** 7
1000000009 *** 6
1000000011
1000000013
1000000015
1000000017
1000000019
1000000021 *** 7

and for greater than 10,000,000,000…

10000000001
10000000003
10000000005
10000000007
10000000009
10000000011
10000000013
10000000015
10000000017
10000000019 *** 21
10000000021
10000000023
10000000025
10000000027
10000000029
10000000031
10000000033 *** 21
10000000035
10000000037
10000000039
10000000041
10000000043
10000000045
10000000047
10000000049
10000000051
10000000053
10000000055
10000000057
10000000059
10000000061 *** 21

So 10 billion takes about 3, which is around root of 10, times as long as 1 billion, so it works as expected.

Comments: The main benefit from this exercise was scheme practice. I also needed to use larger numbers than the question asks for – probably because computers are just faster these days. I also had to find an implementation of runtime for guile, which I found here.

1.23

Implementing next is trivial.

(define (next input)
  (if (= 2 input) 3 (+ input 2)))

The times I get for the first 3 primes greater than 1 billion are

1000000007 *** 4
1000000009 *** 5
1000000021 *** 5

And for the first 3 prime numbers greater than 10 billion

10000000019 *** 13
10000000033 *** 14
10000000061 *** 13

We can see that it takes about 2/3 of the time instead of about 1/2 of the time. I think this is because the next procedure is more expensive than a simple + procedure.

1.24

I would expect 1,000,000 to take around twice as long as 1,000.

1000000007 *** 1
1000000009 *** 1
1000000021 *** 1

and then doubling the number of zeroes…

1000000000000000003 *** 3
1000000000000000009 *** 2
1000000000000000031 *** 2

It seems about right, although likely anything could have gone wrong.
Comments: Caught up a little bit although still slow. A better time function would have been nice, but I am being lazy.

Advertisements


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