For the past week I’ve been working my way through SICP. I’m using DrRacket to test my code and after suffering for a little bit to find the right implementation of Scheme, I found out that it has a SICP mode, all I needed to do was start my file with the line:

#lang planet neil/sicp

And everything just worked! There are even special error messages, like:

random: You called “(random 0)”. If you’re doing SICP section 1.2.6, don’t use 1 for the first argument of “fast-prime?”.

I just finished implementing Miller-Rabin primality test for Exercise 1.28. The idea is to check several numbers to see if they are witness for the compositeness of n. The really cool part is that, for small numbers, is enough to check some specific witness. From Wikipedia:

• if n < 2,047, it is enough to test a = 2;
• if n < 1,373,653, it is enough to test a = 2 and 3;
• if n < 9,080,191, it is enough to test a = 31 and 73;
• if n < 25,326,001, it is enough to test a = 2, 3, and 5;
• if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;
• if n < 1,122,004,669,633, it is enough to test a = 2, 13, 23, and 1662803;
• if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11;
• if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13;
• if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17;
• if n < 3,825,123,056,546,413,051, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, and 23.

So I implemented the test to check for a = 2, 7 and 61 and that is enough for n < 4,759,123,141 (an unsigned 32 bits integers is smaller than 4,294,967,295 so testing with this 3 values is sufficient for all 32 bits integers). My code is here.

tags