<jupyter_start><jupyter_text>練習問題1.25<NAME> は、expmod を書くのにだいぶ余計な⼿間がかかったと愚痴をこぼした。どうせ指数の計算のやり⽅はわかっているんだから、単純にこんなふうに書いたらよかったんじゃないの、と。    (define (expmod base exp m)      (remainder (fast-expt base exp) m))彼⼥は正しいだろうか。⾼速素数判定にこの⼿続きを使っても同じようにうまく⾏くだろうか。 動作イメージ  (remainder手続きをmod()で表記)  例:base=3 exp=5 m=5(n=5,a=3としてnが素数であるかのテスト)$mod(3,5)=3$  $mod(3^5,5)=mod(243,5)=3$  $expmod(3,5,5)$  $=mod(fastexpt(3,5),5)$  $=mod(3\cdot fastexpt(3,4),5)$  $=mod(3\cdot fastexpt(3,2)^2,5)$  $=mod(3\cdot (fastexpt(3,1)^2)^2,5)$  $=mod(3\cdot (3\cdot fastexpt(3,0)^2)^2,5)$  $=mod(3\cdot (3\cdot 1)^2)^2,5)$  $=mod(3\cdot (3^2)^2,5)$  $=mod(3\cdot 9^2,5)$  $=mod(3\cdot 81,5)$  $=mod(243,5)$  $=3$  正しく動作する。  だが、素数かどうかをテストする数が大きい場合、$a^n$の指数が大きくなってしまい、巨大な数を計算することになり、ステップ数が膨大になる。<jupyter_code>(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n)(square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))
    )
  )
; 偶数かどうか判定
(define (even? n)
  (= (remainder n 2) 0)
  )
(define (square x) (* x x))

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))
(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1))))
  )
(define (fast-prime? n times)
  (cond ((= times 0) True)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else False)
         )
  )
(display (fast-prime? 1039 10))
(define (odd? n)(= (remainder n 2) 1))
(define (search-for-primes n m)
  ;(display n)
  (if (<= n m)
      (if (odd? n)
          (if (fast-prime? n 10)
              (begin
               (display n)
               (display " *** ")
               (newline)
              (search-for-primes (+ n 2) m)
              )
              (search-for-primes (+ n 2) m)
            )
      (search-for-primes (+ n 1) m)
      )
        ()
      )
  )
(search-for-primes 2 30)
%%time
(search-for-primes 1009 1009)
(search-for-primes 1013 1013)
(search-for-primes 1019 1019)
%%time
(search-for-primes 10007 10007)
(search-for-primes 10009 10009)
(search-for-primes 10037 10037)
%%time
(search-for-primes 100003 100003)
(search-for-primes 100019 100019)
(search-for-primes 100043 100043)
%%time
(search-for-primes 1000003 1000003)
(search-for-primes 1000033 1000033)
(search-for-primes 1000037 1000037)<jupyter_output>1000003 *** 
1000033 *** 
1000037 *** 
Time: 261.2980422973633 seconds.
{'fraction_non_alphanumeric': 0.1930650684931507, 'fraction_numerical': 0.11386986301369863, 'mean_word_length': 3.128975265017668, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '641028', 'license': 'CC0-1.0', 'n_tokens_mistral': 1361, 'n_tokens_neox': 1160, 'n_words': 209, 'path': 'exercises/1.25.ipynb', 'repo_name': 'tokits/sicp-study', 'size': '2346'}