sicp exercise 1.24

;  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 O(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?


(define (runtime) (gettimeofday))
(define (difftime start end)
      (+
         (*
            (- (car end) (car start))
            100000)
         (- (cdr end) (cdr start))))

(define (square num) (* num num))

(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 (prime? n)
    (define (prime-impl n base)
        (= (expmod base n n) base))
   (prime-impl n (random (- n 1))))

(define (timed-prime-test n)
    (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
    (if (prime? n)
           (report-prime n (difftime start-time (runtime)))
           #f))

(define (report-prime n elapsed-time)
    (display n)
    (display " *** ")
    (display elapsed-time)
    (newline)
    #t)


(define (search-for-primes start end max)
    (define (search-for-primes-impl start count)
        (cond ((> start end) 0)
              ((= count max) 0)
              (else (if (timed-prime-test start)
                             (search-for-primes-impl (+ start 1) (+ count 1))
                             (search-for-primes-impl (+ start 1) count)))))
    (search-for-primes-impl start 0))

(search-for-primes   1000   10000 3)
(search-for-primes  10000  100000 3)
(search-for-primes 100000 1000000 3)

; the time taken to find the 12 primes is lower than the time taken in problems 1.23 and 1.22.
; But i dont find any discrepency, as asked in this problem :(