首页 > 代码库 > Exercise 1.19 Fast Fibonacci

Exercise 1.19 Fast Fibonacci

题目:

There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps.

Recall the transformation of the state variables a and b in the fib-iter process of section 1.2.2: a=a + b and b=a. Call this transformation T, and observe that applying T over and over again n times, starting with 1 and 0, produces the pair Fib(n + 1) and Fib(n). In other words, the Fibonacci numbers are produced by applying T^n. The nth power of the transformation T, starting with the pair (1,0).

Now consider T to be the special case of p = 0 and q = 1 in a family of transformations Tpq, where Tpq transforms the pair (a,b) according to a=bq + aq + ap and b bp + aq. Show that if we apply such a transformation Tpq twice, the effect is the same as using a single transformation Tp‘q‘ of the same form, and compute p‘ and q‘ in terms of p and q. This gives us an explicit way to square these transformations, and thus we can compute Tn using successive squaring, as in the fast-expt procedure. 

 

这里介绍的计算方法非常巧妙。

Exercise 1.16~1.18中,对“数据”进行square;这里则对"变换T"进行square,或者说,对“函数”进行square。

无论是“数据”还是“变换T”,它们的模型都是类似的,即:

1. 一个连续的sequence

2. sequence中的每一步都对上一步的结果进行“相同的操作过程”。

3. 如果变换T1=T.T,那么T2=T.T.T.T=(T.T).(T.T)=T1.T1。(一点思考:符合结合律?)

Exercise 1.19 Fast Fibonacci