3

私はSchemeが初めてです。PLTスキームを使用して、ラビンミラーアルゴリズムの確率的バリアントを試して実装しました。私はそれが確率的であることを知っていますが、ほとんどの場合、間違った結果を得ています。私は C を使用して同じことを実装しましたが、うまくいきました (試行に失敗したことはありません)。デバッグ中に期待どおりの出力が得られますが、実行すると、ほとんどの場合、間違った結果が返されます。Wikipediaのアルゴリズムを使用しました。

(define expmod( lambda(b e m)
                 ;(define result 1)
                 (define r 1)
                 (let loop()
                   (if (bitwise-and e 1)
                       (set! r (remainder (* r b) m)))
                   (set! e (arithmetic-shift e -1))
                   (set! b (remainder (* b b) m))
                   (if (> e 0)
                       (loop)))r))

(define rab_mil( lambda(n k)
                  (call/cc (lambda(breakout)
                  (define s 0)
                  (define d 0)
                  (define a 0)
                  (define n1 (- n 1))
                  (define x 0)          
                  (let loop((count 0))
                    (if (=(remainder n1 2) 0)
                        (begin
                          (set! count (+ count 1))
                          (set! s count)
                          (set! n1 (/ n1 2))
                          (loop count))
                        (set! d n1)))
                  (let loop((count k))
                    (set! a (random (- n 3)))
                    (set! a (+ a 2))
                    (set! x (expmod a d n))
                    (set! count (- count 1))

                    (if (or (= x 1) (= x (- n 1)))
                        (begin
                          (if (> count 0)(loop count))))
                    (let innerloop((r 0))
                      (set! r (+ r 1))
                      (if (< r (- s 1)) (innerloop  r))
                      (set! x (expmod x 2 n))
                      (if (= x 1)
                          (begin
                          (breakout #f)))
                      (if (= x (- n 1)) 
                          (if (> count 0)(loop count)))
                      )
                    (if (= x (- s 1)) 
                        (breakout #f))(if (> count 0) (loop count)))#t))))

また、Scheme で正しい方法でプログラミングしていますか? （私が使用するループ部分の抜け出しについてはよくわかりませんcall/cc。あるサイトで見つけて以来、それを使用しています。）

前もって感謝します。

4

1 に答える 1

6

一般に、あまりにも「命令的」な方法でプログラミングしています。よりエレガントな expmod は次のようになります

(define (expmod b e m)
  (define (emod b e)
    (case ((= e 1) (remainder b m))
          ((= (remainder e 2) 1)
           (remainder (* b (emod b (- e 1))) m)
          (else (emod (remainder (* b b) m) (/ e 2)))))))
  (emod b e))

set の使用を回避します! ルールを再帰的に実装するだけです

b^1 == b (mod m)     
b^k == b b^(k-1) (mod m) [k odd]
b^(2k) == (b^2)^k (mod m)

同様に、rab_mil は非常に非スキームな方法でプログラムされています。別の実装を次に示します。ループの「中断」や call/cc がないことに注意してください。代わりに、Scheme の 'goto' に実際に対応する末尾再帰呼び出しとして分割が実装されます。

(define (rab_mil n k)
  ;; calculate the number 2 appears as factor of 'n'
  (define (twos-powers n)
     (if (= (remainder n 2) 0)
         (+ 1 (twos-powers (/ n 2)))
         0))
  ;; factor n to 2^s * d where d is odd:
  (let* ((s (twos-powers n 0))
         (d (/ n (expt 2 s))))
    ;; outer loop
    (define (loop k)
      (define (next) (loop (- k 1)))
      (if (= k 0) 'probably-prime
          (let* ((a (+ 2 (random (- n 2))))
                 (x (expmod a d n)))
            (if (or (= x 1) (= x (- n 1)))
                (next)
                (inner x next))))))
    ;; inner loop
    (define (inner x next)
      (define (i r x)
        (if (= r s) (next)
            (let ((x (expmod x 2 n)))
              (case ((= x 1) 'composite)
                    ((= x (- n 1)) (next))
                    (else (i (+ 1 r) x))))
      (i 1 x))
    ;; run the algorithm
    (loop k)))
于 2010-02-10T19:09:59.027 に答える