<jupyter_start><jupyter_text>練習問題1.16fast-exptと同じように⼆乗の連続を使って、  指数計算を対数的ステップ数で実⾏する反復的プロセスを⽣成する⼿続きを設計せよ。  (ヒント：$(b^{\frac{n}{2}})^2 = (b^2)^{\frac{n}{2}}$を使い、 指数n、基数$b$のほかに追加の状態変数$a$を持ち、積$a \cdot b^n$が各状態を通して⼀定であるような状態変換を定義せよ。  プロセスの最初では$a$は$1$ とし、答えはプロセス終了時のaの値として得られる。  ⼀般的に、各状態を通して⼀定であるような不変量(invariant quantity)を  定義するというテクニックは、  反復アルゴリズムを設計するうえで 強⼒な⽅法である。)<jupyter_code>(define (fast-expt b n)
  (expt-iter b n 1)
  )
(define (expt-iter b counter product)
  (cond ((= counter 0) product)
        ((even? counter)(expt-iter (square b) (/ counter 2) product))
        (else (expt-iter b (- counter 1) (* product b)))
    )
  )
; 偶数かどうか判定
(define (even? n)
  (= (remainder n 2) 0)
  )
(define (square x) (* x x))
(fast-expt 2 17)
(fast-expt 2 1000)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1822849807445443, 'fraction_numerical': 0.028241335044929396, 'mean_word_length': 5.141732283464567, 'pattern_counts': {'":': 0, '<': 5, '<?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': '27463', 'license': 'CC0-1.0', 'n_tokens_mistral': 514, 'n_tokens_neox': 500, 'n_words': 63, 'path': 'exercises/1.16.ipynb', 'repo_name': 'tokits/sicp-study', 'size': '779'}