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)
??? 则定义过程如下
?
已知：T变换对于(a, b)、(p, q)，a = bq + aq + apb = 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^2q' = 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)?
