(import chicken.time)  ; for current-milliseconds
(import chicken.random)  ; for pseudo-random-integer

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
	((divides? test-divisor n) test-divisor)
	(else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)
  (= (remainder b a) 0))

;(define (prime? n)
  ;(= n (smallest-divisor n)))

(define (square x) (* x x))


(define (timed-prime-test n)
  ;(newline)
  ;(display n)
  (start-prime-test n (current-milliseconds)))

(define (start-prime-test n start-time)
  (if (prime? n)
    (report-prime n (- (current-milliseconds) start-time))))

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


(define (search-for-primes min max)
  (if (<= min max)
      (cond ((odd? min) (timed-prime-test min)
		        (search-for-primes (+ min 2) max))
	    (else       (search-for-primes (+ min 1) max)))))


; (search-for-primes 100000 100100): First 3 take 1 ms each
; (search-for-primes 1000000 1000100): First 3 take 4, 3, 5 ms each
; (search-for-primes 10000000 10000200): First 3 take 14, 12, 13 ms each

; (sqrt 10) is 3.1622, so time increase is around sqrt(n), as expected.


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


;(define (find-divisor n test-divisor)
  ;(cond ((> (square test-divisor) n) n)
	;((divides? test-divisor n) test-divisor)
	;(else (find-divisor n (next test-divisor)))))

; Now (search-for-primes 10000000 10000200): takes 7, 7, 10 ms each.  So approximately
; half for the first two but a bit more for the third.  This will be quicker, if the
; procedure has to search through lots of candidate divisors.  Each call to next is
; more expensive that adding 1, which may account for the difference.

; Increase the size of the integers (to reduce noisy measurements):
; (search-for-primes 10000000000 10000000200)
; This takes ~141ms for the +1 case and ~87ms for the next case: A speedup of around
; 1.6.  This must be accounted for by the extra comparison.


; 1.24

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (pseudo-random-integer (- n 1)))))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
	((even? exp)
	 (remainder (square (expmod base (/ exp 2) m))
		    m))
	(else
	  (remainder (* (expmod base (- exp 1) m) base)
		     m))))

(define (fast-prime? n times)
  (cond ((= times 0) #t)
	((fermat-test n) (fast-prime? n (- times 1)))
	(else #f)))

(define (prime? n)
  (fast-prime? n 10))

; Now prime test as above takes 2-3 ms for the first three answers
;  (search-for-primes (square 10000000000) (+ 500 (square 10000000000)))
; This should be about double, given the the algorithm is logarithmic in time.
; We get 6, 8, 8 ms (more like 3 times as long).  Maybe this is from the higher 
; overhead of the random number generator?  Or more likely, because we are running
; the Fermat test 10 times.

; 1.25: The answer should be the same if we take remainders after exponentiating,
; but exponentiating first keeps the numbers smaller, thus enabling testing of 
; larger primes with less memory.

; 1.26: Writing out the multiplication instead of using square means that the
; argument is computed twice (once for each argument to * rather than once for 
; square.  So we are no longer halving the number of steps needed.  Hence, this is
; no longer a log n algorithm.

; 1.27

; Test if a^n is congruent to a mod n for all a<n

(define (fermat n)
  (define (fermat-rec a n)
    (if (= a 1) 
	#t
	(and (= (expmod a n n) a)
	     (fermat-rec (- a 1) n))))
  (fermat-rec (- n 1) n))