SICP学习笔记 1.2.4 求幂

    练习1.16

    根据提示, a*b^n保持不变、使用a来保存结果，观察如下变换过程
    求b^100，(b n a)
    -->(b 100 a)
    -->(b^2 50 a)
    -->(b^4 25 a)
    此时根据fast-expt的过程，应将25执行减1操作，如果保持a*b^n不变，则可有如下变换
    -->(b^4 24 b^4)
    即(b^4)^24*b^4=b^100,当n为奇数时，a=a*b，则a=1
    -->(b^8 12 b^4)
    -->(b^16 6 b^4)
    -->(b^32 3 b^4)
    此时n为奇数，a=a*b，则
    -->(b^32 2 b^36)
    -->(b^64 1 b^36)
    -->(b^64 0 b^100)
    则定义过程如下

 

(define (fast-iter-expt b n)
  (fast-expt-iter b n 1))

(define (fast-expt-iter b counter product)
  (cond ((= counter 0) product)
		((even? counter) (fast-expt-iter (square b) (/ counter 2) product))
		(else (fast-expt-iter b (- counter 1) (* b product)))))
		
(define (square x)
  (* x x))

(define (even? n)
  (= (remainder n 2) 0))

 

    练习1.17

 

(define (* a b)
  (if (= b 0)
	  0
	  (+ a (* a (- b 1)))))
	  
(define (double x)
  (+ x x))
(define (halve x)
  (/ x 2))

(define (fast* a b)
  (cond ((= b 0) 0)
		((even? b) (double (fast* a (halve b))))
		(else (+ a (fast* a (- b 1))))))

 

    练习1.18

 

(define (fast* a b)
  (fast*-iter a b 0))
  
(define (fast*-iter a b v)
  (cond ((= b 0) v)
        ((even? b) (fast*-iter (double a) (halve b) v))
        (else (fast*-iter a (- b 1) (+ a v)))))
        
(define (double x)
  (+ x x))
  
(define (halve x)
  (/ x 2))

(define (even? n)
  (= (remainder n 2) 0))	

 

    练习1.19

 

已知：T变换对于(a, b)、(p, q)，
a = bq + aq + ap
b = bp + aq

则有如下变换过程
   (a, b)
-->(bq + aq + ap, bp + aq) 
-->(bq' + aq' + ap', bp' + aq')
则有
(1)bq' + aq' + ap' = (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
(2)bp' + aq' = (bp + aq)p + (bq + aq + ap)q
将(1)右边展开，得到
  bq' + aq' + ap'
= (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
= bpq + aq^2 + bq^2 + aq^2 + apq + bpq + apq + ap^2
= 2bpq + 2apq + 2aq^2 + bq^2 + ap^2
= b(2pq + q^2) + a(2pq + q^2) + a(p^2 + q^2)
则有
p' = p^2 + q^2
q' = 2pq + q^2
代入(2)，检测正确
  bp' + aq'
= (bp + aq)p + (bq + aq + ap)q
= bp^2 + apq + bq^2 + aq^2 + apq
= b(p^2 + q^2) + a(2pq + q^2)