странность в схеме

Question

Я пытался реализовать тест примитивности Ферма в Схеме.Я написал процедуру fermat2 (изначально называемую fermat1), которая возвращает true, когда конгруэнт ^ p-1 1 (mod p) (пожалуйста, правильно прочитайте, ребята !!) a

каждое простое число p должно удовлетворять процедуре (и, следовательно,маленькая теорема ..) для любого a

Но когда я попытался посчитать, сколько раз эта процедура дает истину для фиксированного числа испытаний ... (используя процедуру подсчета, описанную в коде), я получил шокирующие результаты и

Таким образом, я немного изменил процедуру (я не вижу никаких логических изменений .. может быть, я слепой) и назвал его fermat1 (заменяя старый fermat1, теперь старый fermat1 -> fermat2), и это сработало .. переданные простые числатест все время ...

почему на земле процедура fermat2 вызывается меньшее количество раз ... что на самом деле не так ??если это неправильно, почему я не получаю ошибку ... вместо этого вычисления пропускаются !! (я так думаю!)

все, что вам нужно сделать, чтобы понять, что я пытаюсь сказать, это

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

и убедитесь сами.

Код:

;;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))

У меня была настоящая боль ... выясняю, что это на самом деле делает ... пожалуйста, следуйте коду и скажитепочему это противоречие?

Answer 1

Четное (countt fermat2 19 100), вызываемое дважды, возвращает разные результаты.

Давайте исправим ваш fermat2, так как он короче.Определение таково: «Если n - простое число, а a - любое положительное целое число, меньшее n, то возведение в n-ую степень соответствует модулю n».Это значит f(a, n) = a^n mod n == a mod n.Ваш код сообщает f(a, n) = a^(n-1) mod n == 1, что отличается.Если мы переписываем это согласно определению:

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

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

Это еще не правильно.(1+ (random n)) возвращает числа от 1 до n включительно, в то время как нам нужно [1..n):

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

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

Это правильная версия, но мы можем улучшить ее читабельность.Поскольку вы используете tryout только в области действия fermat2, в параметре x нет необходимости передавать n - последний уже связан в области действия tryout, поэтому окончательная версия -

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

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

Обновление:

Я сказал, что формула, используемая в fermat2, неверна.Это неправильно, потому что если a*k = b*k (mod n), то a = b (mod n).Ошибка, как указал Васу, заключалась в генерации случайного числа для теста.