SICP 1.18
(define (fast-mul x n) (define (mul-iter y n) (let ((halv (lambda (n) (/ n 2))) (double (lambda (n) (* n 2)))) (cond ((= n 1) #?=y) ((even? n) #?=(mul-iter (double y) (halv n))) (else #?=(+ x (mul-iter y (- n 1))))))) (mul-iter x n)) (fast-mul 3 4)
これも1.16と同じで間違ってる。本文を読まずにいきなり解いたのが良くなかった。
考え方は同じ。
x * n => 0 + x * n
x * 2n => 0 + 2x * n
x * (n+1) => x + x *n
(define (fast-mul x n) (define (mul-iter k y n) (let ((halv (lambda (n) (/ n 2))) (double (lambda (n) (* n 2)))) (cond ((= n 0) k) ((even? n) (mul-iter k (double y) (halv n))) (else (mul-iter (+ k y) y (- n 1)))))) (mul-iter 0 x n))