# SICP - Solution: Exercise 1.24

##### October 17, 2018

**Exercise 1.24:** Modify the `timed-prime-test`

procedure of Exercise 1.22 to use `fast-prime?`

(the Fermat method), and test each of the 12 primes you found in that exercise. Since the Fermat test has ${\mathrm\Theta(\log;n)}$ growth, how would you expect the time to test primes near 1,000,000 to compare with the time needed to test primes near 1000? Do your data bear this out? Can you explain any discrepancy you find?

**Solution**

```
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder
(square (expmod base (/ exp 2) m))
m))
(else
(remainder
(* base (expmod base (- exp 1) m))
m))))
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
(define (fast-prime? n times)
(cond ((= times 0) #t)
((fermat-test n)
(fast-prime? n (- times 1)))
(else #f)))
```

I choosed to run each test on 100 random numbers, but this is somewhat a guessed value:

```
(define (start-prime-test n start-time)
(if (fast-prime? n 100)
(report-prime (- (runtime) start-time))
"nothing"))
```

Here too, in order to increase precision of the execution time measurement, all computation are run 1000 times on each prime number for each of the algorithm.

I ran in a few issue with the random number generator for the largest prime in my table. I just removed them as it don’t change the conclusion.

### DrRacket #

log(prime) | prime | time prime? (µs) | time fast-prime? (µs) |
---|---|---|---|

3 | 1,009 | 2.8029 | 175.80 |

3 | 1,013 | 2.3579 | 160.85 |

3 | 1,019 | 2.2888 | 179.21 |

4 | 10,007 | 8.1271 | 218.31 |

4 | 10,009 | 7.7409 | 193.58 |

4 | 10,037 | 7.6669 | 241.30 |

5 | 100,003 | 25.369 | 238.16 |

5 | 100,019 | 24.364 | 279.69 |

5 | 100,043 | 24.239 | 240.71 |

6 | 1,000,003 | 76.642 | 388.47 |

6 | 1,000,033 | 91.104 | 277.81 |

6 | 1,000,037 | 83.062 | 304.60 |

7 | 10,000,019 | 245.59 | 364.91 |

7 | 10,000,079 | 253.24 | 372.02 |

7 | 10,000,103 | 264.88 | 358.31 |

8 | 100,000,007 | 855.93 | 386.96 |

8 | 100,000,037 | 974.68 | 392.14 |

8 | 100,000,039 | 829.26 | 401.62 |

9 | 1,000,000,007 | 2588.9 | 438.92 |

9 | 1,000,000,009 | 2728.9 | 425.29 |

9 | 1,000,000,021 | 2848.4 | 455.42 |

Which can be summarized:

log(prime) | average time `prime?` (µs) |
delta for 10x (µs) | average time `fast-prime?` (µs) |
delta for 10x (µs) |
---|---|---|---|---|

3 | 2,4832 | 171,95 | ||

4 | 7,8450 | 5,3618 | 217,73 | 45,7 |

5 | 24,658 | 16,813 | 252,85 | 35,1 |

6 | 83,603 | 58,945 | 323,63 | 70,7 |

7 | 254,57 | 170,97 | 365,08 | 41,4 |

8 | 886,62 | 632,04 | 393,57 | 28,4 |

9 | 2722,1 | 1835,5 | 439,88 | 46,3 |

### Chicken Scheme (compiled) #

log(prime) | prime | time prime? (µs) | time fast-prime? (µs) |
---|---|---|---|

3 | 1,009 | 4.0 | 172.0 |

3 | 1,013 | 3.0 | 180.0 |

3 | 1,019 | 4.0 | 193.0 |

4 | 10,007 | 11.0 | 221.0 |

4 | 10,009 | 13.0 | 218.0 |

4 | 10,037 | 10.0 | 224.0 |

5 | 100,003 | 35.0 | 256.0 |

5 | 100,019 | 35.0 | 261.0 |

5 | 100,043 | 38.0 | 276.0 |

6 | 1,000,003 | 113.0 | 297.0 |

6 | 1,000,033 | 111.0 | 296.0 |

6 | 1,000,037 | 114.0 | 311.0 |

7 | 10,000,019 | 353.0 | 355.0 |

7 | 10,000,079 | 355.0 | 381.0 |

7 | 10,000,103 | 362.0 | 384.0 |

8 | 100,000,007 | 1157.0 | 435.0 |

8 | 100,000,037 | 1126.0 | 444.0 |

8 | 100,000,039 | 1126.0 | 450.0 |

9 | 1,000,000,007 | 3516.0 | 462.0 |

9 | 1,000,000,009 | 3744.0 | 477.0 |

9 | 1,000,000,021 | 3641.0 | 499.0 |

Which can be summarized:

log(prime) | average time `prime?` (µs) |
time multiplication for 10x | average time `fast-prime?` (µs) |
time increase for 10x (µs) |
---|---|---|---|---|

3 | 3,67 | 181,67 | ||

4 | 11,33 | 3,09 | 221 | 39,3 |

5 | 36 | 3,18 | 264,33 | 43,3 |

6 | 112,67 | 3,13 | 301,33 | 37,0 |

7 | 356,67 | 3,17 | 373,33 | 72,0 |

8 | 1136,33 | 3,19 | 443 | 69,7 |

9 | 3633,67 | 3,20 | 479,33 | 36,3 |

### Conclusion #

When the size of `prime`

is 10 times larger, `prime?`

require 3 times more computation.

When the size of `prime`

is 10 times larger, `fast-prime?`

require a constant increase of 50µs. ${\mathrm\Theta(\log;n)}$ growth means that when the prime are ten times larger, the time will increase by a constant amount ${\log(100)-\log(10)=1}$. This is quite clear here.

Although that for smaller number `prime?`

is faster, `fast-prime?`

become much faster with larger and larger prime.