weirdness in scheme

Question

I was trying to implement Fermat's primality test in Scheme. I wrote a procedure fermat2(initially called fermat1) which returns true when a^p-1 congruent 1(mod p) (please read it correctly guys!!) a

every prime p number should satisfy the procedure (And hence Fermat's little theorem .. ) for any a

But when I tried to count the number of times this procedure yields true for a fixed number of trials ... ( using countt procedure, described in code) I got shocking results ans

So I changed the procedure slightly (I don't see any logical change .. may be I'm blind) and named it fermat1(replacing older fermat1 , now old fermat1 ->fermat2) and it worked .. the prime numbers passed the test all the times ...

why on earth the procedure fermat2 called less number of times ... what is actually wrong?? if it is wrong why don't I get error ... instead that computation is skipped!!(I think so!)

all you have to do , to understand what I'm trying to tell is

(countt fermat2 19 100)
(countt fermat1 19 100)

and see for yourself.

Code:

;;Guys this is really weird
;;I might not be able to explain this
;;just try out
;;(countt fermat2 19 100) 
;;(countt fermat1 19 100)
;;compare both values ...
;;did you get any error using countt with fermat2,if yes please specify why u got error
;;if it was because of reminder procedure .. please tell your scheme version

;;created on 6 mar 2011 by fedvasu
;;using mit-scheme 9.0 (compiled from source/microcode)
;; i cant use a quote it mis idents (unfriendly stack overflow!)
;;fermat-test based on fermat(s) little theorem a^p-1 congruent to 1 (mod p) p is prime
;;see MIT-SICP,or Algorithms by Vazirani or anyother number theory book

;;this is the correct logic of fermat-test (the way it handles 0)
 (define (fermat1 n)
     (define (tryout a x)
;; (display "I've been called\n")
      (= (remainder (fast-exp a (- x 1)) x) 1))
                    ;;this exercises the algorithm
                    ;;1+ to avoid 0
       (define temp (random n))
       (if (= temp 0)
     (tryout (1+ temp) n)
     (tryout temp n)))

;;old fermat-test
;;which is wrong
;;it doesnt produce any error!!
;;the inner procedure is called only selective times.. i dont know when exactly 
;;uncomment the display line to see how many times tryout is called (using countt)
;;i didnt put any condition when it should be called
;;rather it should be every time fermat2 is called
;;how is it so??(is it to avoid error?)
  (define (fermat2 n)
   (define (tryout a x)
     ;; (display "I've been called\n")
      (= (remainder (fast-exp a (- x 1)) x) 1))
                     ;;this exercises the algorithm
                     ;;1+ to avoid 0
                    (tryout (1+ (random n)) n))

;;this is the dependency procedure for fermat1 and fermat2
;;this procedure calculates base^exp (exp=nexp bcoz exp is a keyword,a primitive)
;;And it is correct :)
  (define (fast-exp base nexp)
   ;;this is iterative procedure where a*b^n = base^exp is constant always
   ;;A bit tricky though
    (define (logexp a b n)
      (cond ((= n 0) a);;only at the last stage a*b^n is not same as base^exp
         ((even? n) (logexp a (square b) (/ n 2)))
         (else (logexp (* a b) b (- n 1)))))

        (logexp 1 base nexp))


 ;;utility procedure which takes a procedure and its argument and an extra 
 ;; argument times which tells number of times to call
 ;;returns the number of times result of applying proc on input num yielded true
 ;;counting the number times it yielded true
 ;;procedure yields true for fixed input,
 ;;by calling it fixed times)
 ;;uncommenting display line will help
   (define (countt proc num times)
     (define (pcount p n t c)
             (cond ((= t 0)c)
                ((p n );; (display "I'm passed by fermat1\n")
                (pcount p n (- t 1) (+ c 1)));;increasing the count
                 (else c)))
        (pcount proc num times 0))

I had real pain .. figuring out what it actually does .. please follow the code and tell why this dicrepieancies?

hoha hoha · Accepted Answer · 2011-03-06T15:02:05

Even (countt fermat2 19 100) called twice returns different results.

Let's fix your fermat2 since it's shorter. Definition is: "If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n.". That means f(a, n) = a^n mod n == a mod n. Your code tells f(a, n) = a^(n-1) mod n == 1 which is different. If we rewrite this according to definition:

(define (fermat2 n)
  (define (tryout a x)
    (= (remainder (fast-exp a x) x) 
       (remainder a x)))

  (tryout (1+ (random n)) n))

This is not correct yet. (1+ (random n)) returns numbers from 1 to n inclusive, while we need [1..n):

(define (fermat2 n)
  (define (tryout a x)
    (= (remainder (fast-exp a x) x) 
       (remainder a x)))

  (tryout (+ 1 (random (- n 1))) n))

This is correct version but we can improve it's readability. Since you're using tryout only in scope of fermat2 there is no need in parameter x to pass n - latter is already bound in scope of tryout, so final version is

(define (fermat n)
  (define (tryout a)
    (= (remainder (fast-exp a n) n) 
       (remainder a n)))

  (tryout (+ 1 (random (- n 1)))))

Update:

I said that formula used in fermat2 is incorrect. This is wrong because if a*k = b*k (mod n) then a = b (mod n). Error as Vasu pointed was in generating random number for test.

weirdness in scheme

1 Answers