※ 引述《hijkxyzuw (i,j,k) ×(x,y,z)》之銘言： : 最近在讀 sicp ，在 1-2-4 章， : 有介紹一種將 n 次計算簡化為 log(n) 次的作法。 : 他應用在費氏數列上，但他使用的費氏數列算法我看不懂……。 : 原文： : > *Exercise 1.19:* 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 *note 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 T_(pq), where T_(pq) : > transforms the pair (a,b) according to a <- bq + aq + ap and b <- : > bp + aq. Show that if we apply such a transformation T_(pq) twice, : > the effect is the same as using a single transformation T_(p'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 T^n using successive squaring, as in the 'fast-expt' : > procedure. Put this all together to complete the following : > procedure, which runs in a logarithmic number of steps:(5) 因為矩陣乘法(or 線性變換的合成)符合結合律 他的意思是說, 觀察 a' = a + b b' = a 這個算式, 發現用矩陣來表達的話(發現他是個線性變換): ( F_{n+2} ) = ( 1 1 ) ( F_{n+1} ) ( F_{n+1} ) ( 1 0 ) ( F_n ) 要把 F 前進幾項就是把中間的方陣乘在左邊幾次. 但是因為他有結合律, 可以先把中間的方陣用 A^{2n} = ( A^n )^2 A^{2n+1} = A ( A^n )^2 的方式快速冪, 複雜度變 log n --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.137.5.117 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Programming/M.1504437153.A.839.html