<jupyter_start><jupyter_text>1.2.4 指数計算ここでは指数計算(基数$b$と正の整数$n$を引数に取り、$b^{n}$を求める)を考える。  次のように再帰的定義によって定義できる。  $b^{n} = b \cdot b^{n−1}$  $b^{0} = 1$<jupyter_code>(define (expt b n)
  (if (= n 0) 1
      (* b (expt b (- n 1)))
    )
  )
(expt 2 4)
(expt 2 8)<jupyter_output><empty_output><jupyter_text>これは線形再帰プロセスで、  $\Theta(n)$のステップ数と$\Theta(n)$の空間(メモリ)を必要とする。階乗と同じように、等価な線形反復としてすぐに定式化できる。<jupyter_code>(define (expt2 b n)
  (expt-iter b n 1)
  )
(define (expt-iter b counter product)
  (if (= counter 0) product
      (expt-iter b (- counter 1) (* b product))
    )
  ) 
(expt2 2 3)<jupyter_output><empty_output><jupyter_text>この実装では、  $\Theta(n)$のステップ数と$\Theta(1)$の空間(メモリ)を必要とする。指数は、⼆乗を連続して使うことによって、より少ないステップ数で計算できる。  例えば、  $b^{8}$を$b \cdot (b \cdot (b \cdot (b \cdot (b \cdot (b \cdot (b \cdot b))))))$   のようにするのではなく、  $b^{2}=b^{1} \cdot b^{1}$   $b^{4}=b^{2} \cdot b^{2}$   $b^{8}=b^{4} \cdot b^{4}$   とすることで、3回の乗算で求めることができる。   この⽅法は、指数が2の冪乗である場合にうまくできる。  次の規則を使うことで、⼀般的な指数計算をすることができる。     ・$b^n = (b^{\frac{n}{2}})^2$ $n$が偶数の場合     ・ $b^n = b \cdot b^{n−1}$ $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))
(fast-expt 2 11)
(begin
  (define (fast-expt b n)
      (cond ((= n 0) 1)
            ((even? n)(begin
                       (display "(fast-expt(")
                       (display b)
                       (display " ")
                       (display (/ n 2))
                       (display "))^2")
                       (newline)
                       (square (fast-expt b (/ n 2))))
                     )
            (else (begin
                       (display b)
                       (display "*(fast-expt(")
                       (display b)
                       (display " ")
                       (display (- n 1))
                       (display ")")
                       (newline)
                       (* b (fast-expt b (- n 1))))
                  )
        )
      )
    ; 偶数かどうか判定
    (define (even? n)
      (= (remainder n 2) 0)
      )
    (define (square x) (* x x))
    (fast-expt 2 1000)
 )<jupyter_output>(fast-expt(2 500))^2
(fast-expt(2 250))^2
(fast-expt(2 125))^2
2*(fast-expt(2 124)
(fast-expt(2 62))^2
(fast-expt(2 31))^2
2*(fast-expt(2 30)
(fast-expt(2 15))^2
2*(fast-expt(2 14)
(fast-expt(2 7))^2
2*(fast-expt(2 6)
(fast-expt(2 3))^2
2*(fast-expt(2 2)
(fast-expt(2 1))^2
2*(fast-expt(2 0)
{'fraction_non_alphanumeric': 0.19781931464174454, 'fraction_numerical': 0.0455607476635514, 'mean_word_length': 1.9630911188004614, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 12, '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': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '649938', 'license': 'CC0-1.0', 'n_tokens_mistral': 1363, 'n_tokens_neox': 1234, 'n_words': 220, 'path': 'texts/1.2.4.ipynb', 'repo_name': 'tokits/sicp-study', 'size': '2568'}