指數減半,必須保留所計算的意思
求 a 13 a^{13} a 13 時,不必逐個乘上十三份,因平方結果可以重用。但累積值與底數不斷改變,程式未必易讀:為何遇到 1 位元就乘入答案,再平方底數、丟掉該位?迴圈不變量可以把關係說清楚。
這個論證不只適用於普通數,也適用於矩陣等結合運算,包括一般不能交換輸入的運算。因此同一個小算法,在競賽編程中有多種實際用途。
寫迴圈前,先指定運算
設集合 S S S 配有封閉且具結合律的運算 ∘ \circ ∘ ,以及雙邊單位元 I I I ,即 x ∘ y ∈ S x\circ y\in S x ∘ y ∈ S 、( x ∘ y ) ∘ z = x ∘ ( y ∘ z ) (x\circ y)\circ z=x\circ(y\circ z) ( x ∘ y ) ∘ z = x ∘ ( y ∘ z ) 、I ∘ x = x ∘ I = x I\circ x=x\circ I=x I ∘ x = x ∘ I = x 。這樣的結構稱為幺半群。
對 a ∈ S a\in S a ∈ S ,定義 a 0 = I a^0=I a 0 = I ,並對整數 n ≥ 0 n\ge0 n ≥ 0 定義 a n + 1 = a n ∘ a a^{n+1}=a^n\circ a a n + 1 = a n ∘ a 。結合律推出
a r + s = a r ∘ a s , ( a r ) s = a r s ( r , s ≥ 0 ) . a^{r+s}=a^r\circ a^s,\qquad
(a^r)^s=a^{rs}\qquad(r,s\ge0). a r + s = a r ∘ a s , ( a r ) s = a r s ( r , s ≥ 0 ) . 這些等式由同一元素的重複項分組得到,不要求 S 的任意元素都可交換。
例子包括整數乘法、單位元 1;正整數模數下的餘數乘法;固定維度的方陣乘法、單位矩陣。以下運算是精確的。浮點乘法只近似具結合律,故精確代數證明不會消除實際計算的捨入問題。
指數條件是非負整數。負冪需要底數有逆元,而幺半群中未必存在;它不屬於此算法輸入範圍,不可把負指數直接交給減半迴圈。
從右至左讀二進位位元
非負整數 e 的最低位是 e % 2,e // 2 則移除它。所需底數依次是 a , a 2 , a 4 , a 8 , … a,a^2,a^4,a^8,\ldots a , a 2 , a 4 , a 8 , … ,可用平方產生。某位為 1,便把當前冪乘入累積值。
BINARY_POWER(a, n, combine, I):
require n is a nonnegative integer
result = I
power = a
e = n
while e > 0:
if e % 2 == 1:
result = combine(result, power)
e = e // 2
if e > 0:
power = combine(power, power)
return result
最後一次平方被省略,因已無餘下位元。combine 實作 ∘ \circ ∘ ,輸入及輸出都是指定幺半群中的值。對矩陣,它是矩陣乘法,不是把對應位置的元素各自相乘。
對每個容許的 a , n a,n a , n ,BINARY_POWER 終止並回傳 a n a^n a n 。每次進入迴圈的核心不變量是
result ∘ power e = a n . \texttt{result}\circ\texttt{power}^{\texttt{e}}=a^n. result ∘ power e = a n .
初始化為 I ∘ a n = a n I\circ a^n=a^n I ∘ a n = a n 。若當前 e = 2 k e=2k e = 2 k ,累積值不變;減半及平方後所表示的值為 result ∘ ( power 2 ) k = result ∘ power 2 k \texttt{result}\circ(\texttt{power}^2)^k=\texttt{result}\circ\texttt{power}^{2k} result ∘ ( power 2 ) k = result ∘ power 2 k 。
若 e = 2 k + 1 e=2k+1 e = 2 k + 1 ,先把累積值改為 result ∘ power \texttt{result}\circ\texttt{power} result ∘ power ,減半及平方後表示 ( result ∘ power ) ∘ ( power 2 ) k = result ∘ power 2 k + 1 (\texttt{result}\circ\texttt{power})\circ(\texttt{power}^2)^k=\texttt{result}\circ\texttt{power}^{2k+1} ( result ∘ power ) ∘ ( power 2 ) k = result ∘ power 2 k + 1 。只用了結合律與同一元素的冪法則。
正指數經整數減半後嚴格變小。最後一輪指數為 1,累積值吸收最後一個冪,指數便成 0。此時省略平方無害,因任何候選下一底數的零次冪都是 I,所以終止時不變量給出答案 a n a^n a n 。n = 0 n=0 n = 0 時根本不進迴圈,直接回傳 I。
證明透視
結合律在哪裏起作用,以及次序為何安全 關鍵一步是不變量的選擇:不只追蹤累積值,而是追蹤累積值與剩餘冪這一對,使得把 ( power , e ) (\texttt{power},\texttt{e}) ( power , e ) 中的一個因子移進 result 時,乘積保持不變。結合律用了兩次:把 ( result ∘ power ) ∘ ( power 2 ) k (\texttt{result}\circ\texttt{power})\circ(\texttt{power}^2)^k ( result ∘ power ) ∘ ( power 2 ) k 重新分組為 result ∘ power 2 k + 1 \texttt{result}\circ\texttt{power}^{2k+1} result ∘ power 2 k + 1 ,以及證明 ( power 2 ) k = power 2 k (\texttt{power}^2)^k=\texttt{power}^{2k} ( power 2 ) k = power 2 k 。交換律從未用到,因為每次乘法都把 result 放在左邊、同一元素的冪放在右邊,而同一元素的各個冪彼此可交換。論證能夠完結,是因為 e e e 是嚴格遞減的非負整數,而 e = 0 e=0 e = 0 時剩餘因子是 power 0 = I \texttt{power}^0=I power 0 = I 。
無法省去的假設是結合律。
反例模式
沒有結合律,不變量便失效 設 S = { I , p , q } S=\{I,p,q\} S = { I , p , q } ,I I I 為單位元,其餘乘積為 p ∘ p = I p\circ p=I p ∘ p = I 、p ∘ q = I p\circ q=I p ∘ q = I 、q ∘ p = q q\circ p=q q ∘ p = q 、q ∘ q = p q\circ q=p q ∘ q = p 。此運算不具結合律:( q ∘ q ) ∘ q = p ∘ q = I (q\circ q)\circ q=p\circ q=I ( q ∘ q ) ∘ q = p ∘ q = I ,但 q ∘ ( q ∘ q ) = q ∘ p = q q\circ(q\circ q)=q\circ p=q q ∘ ( q ∘ q ) = q ∘ p = q 。定義 q 3 = ( q ∘ q ) ∘ q q^3=(q\circ q)\circ q q 3 = ( q ∘ q ) ∘ q ,其值為 I I I 。對 a = q a=q a = q 、n = 3 n=3 n = 3 執行算法:result = I ∘ q = q =I\circ q=q = I ∘ q = q ,平方得 power = q ∘ q = p =q\circ q=p = q ∘ q = p ,然後 result = q ∘ p = q =q\circ p=q = q ∘ p = q 。它返回 q q q 而不是 I I I 。修正方法正是定義中的假設:運算必須具結合律,所以此算法適用於矩陣和餘數,卻不適用於任意運算。
計算程式實際做的運算次數
若 n > 0 n>0 n > 0 ,設位元長度為 L = ⌊ log 2 n ⌋ + 1 L=\lfloor\log_2n\rfloor+1 L = ⌊ log 2 n ⌋ + 1 ,而 popcount ( n ) \operatorname{popcount}(n) popcount ( n ) 是其中 1 的數目。迴圈恰執行 L 次,每個 1 位元做一次累積乘法,除最後一輪外每輪平方一次,所以 combine 調用次數恰為
popcount ( n ) + L − 1 ( n > 0 ) . \operatorname{popcount}(n)+L-1\qquad(n>0). popcount ( n ) + L − 1 ( n > 0 ) .
n = 0 n=0 n = 0 時零次調用。若另一版本每輪結尾無條件平方,就多做一次無用運算;答案一樣,精確次數卻不同。
可選 二進位方法用的乘法次數最少嗎? 不一定:對指數 15,存在更短的乘積序列。
自然延伸的下一個問題
二進位方法用的乘法次數最少嗎? 不一定:對指數 15,存在更短的乘積序列。
此方法計算 a 15 a^{15} a 15 要用 popcount ( 15 ) + 4 − 1 = 7 \operatorname{popcount}(15)+4-1=7 popcount ( 15 ) + 4 − 1 = 7 次乘法。但 a 2 , a 3 , a 6 , a 12 , a 15 a^2,\ a^3,\ a^6,\ a^{12},\ a^{15} a 2 , a 3 , a 6 , a 12 , a 15 只需五次,每次都是兩個較早的冪相乘:a ⋅ a a\cdot a a ⋅ a 、a 2 ⋅ a a^2\cdot a a 2 ⋅ a 、a 3 ⋅ a 3 a^3\cdot a^3 a 3 ⋅ a 3 、a 6 ⋅ a 6 a^6\cdot a^6 a 6 ⋅ a 6 、a 12 ⋅ a 3 a^{12}\cdot a^3 a 12 ⋅ a 3 。對給定指數找出最短的這類序列是另一個問題,本單元並未解決。
關閉
這是算術運算次數,不是通用位元時間界。combine 成本取決於運算元。普通 d 階矩陣乘法使用 O ( d 3 ) O(d^3) O ( d 3 ) 次純量運算,所以正指數時共 O ( d 3 log n ) O(d^3\log n) O ( d 3 log n ) 次純量運算。精確整數元素可能增長,不能一律當每次純量運算的位元成本是常數。
模冪要化簡運算,也要化簡單位元
模數 m 為正時,用餘數 { 0 , … , m − 1 } \{0,\ldots,m-1\} { 0 , … , m − 1 } 、combine(x,y) = (x*y) mod m、底數 a mod m,以及單位元 1 mod m。每次乘法後取模有效,因同餘在乘法下保持。
m = 1 m=1 m = 1 時唯一餘數為 0。因此即使指數為零,也須回傳 1 mod 1 = 0,不能回傳未正規化整數 1。模數零不在運算定義內。普通整數乘法下,本算法把 0 0 0^0 0 0 定為空乘積 1;這是明確的離散約定,不是對未定式極限作結論。
取模會限制儲存值,但中間乘積仍可能接近 m 2 m^2 m 2 。要用精確大整數,或正確位寬/安全的模乘法,才符合數學運算。固定寬度乘積若已溢位,事後取模不能修好已損壞的值。
例題 11.1.3
(計算 3 的 13 次冪模 17)
13 = ( 1101 ) 2 13=(1101)_2 13 = ( 1101 ) 2 ,從右讀位元為 1、0、1、1。表中記錄各輪入口值,以及處理該位後的累積值:
三次平方是 3 2 ≡ 9 3^2\equiv9 3 2 ≡ 9 、9 2 ≡ 13 9^2\equiv13 9 2 ≡ 13 、13 2 ≡ 16 ( m o d 17 ) 13^2\equiv16\pmod{17} 1 3 2 ≡ 16 ( mod 17 ) 。累積乘法為 1 ⋅ 3 ≡ 3 1\cdot3\equiv3 1 ⋅ 3 ≡ 3 、3 ⋅ 13 ≡ 5 3\cdot13\equiv5 3 ⋅ 13 ≡ 5 、5 ⋅ 16 ≡ 12 5\cdot16\equiv12 5 ⋅ 16 ≡ 12 。故 3 13 ≡ 12 ( m o d 17 ) 3^{13}\equiv12\pmod{17} 3 13 ≡ 12 ( mod 17 ) 。三次平方加三次累積乘法,吻合 popcount ( 13 ) + 4 − 1 = 6 \operatorname{popcount}(13)+4-1=6 popcount ( 13 ) + 4 − 1 = 6 。
n = 0 n=0 n = 0 時迴圈不會進入,直接返回 result = I =I = I ,調用次數為零;n = 1 n=1 n = 1 時迴圈執行一次,result = I ∘ a = a =I\circ a=a = I ∘ a = a ,不做平方,所以有一次調用,與 popcount ( 1 ) + 1 − 1 = 1 \operatorname{popcount}(1)+1-1=1 popcount ( 1 ) + 1 − 1 = 1 一致。模 1 1 1 時所有餘數都是 0 0 0 ,故 I = 1 m o d 1 = 0 I=1\bmod1=0 I = 1 mod 1 = 0 :調用 3 0 m o d 1 3^{0}\bmod1 3 0 mod 1 返回 0 0 0 ,各個乘積也全是 0 0 0 。若例程對指數零返回字面整數 1 1 1 ,在這裏便是錯的。
把遞推編成固定線性轉移
定義斐波那契(Fibonacci)數 F 0 = 0 F_0=0 F 0 = 0 、F 1 = 1 F_1=1 F 1 = 1 、F n + 2 = F n + 1 + F n F_{n+2}=F_{n+1}+F_n F n + 2 = F n + 1 + F n 。設
M = ( 1 1 1 0 ) , ( F n + 2 F n + 1 ) = M ( F n + 1 F n ) . M=\begin{pmatrix}1&1\\1&0\end{pmatrix},\qquad
\begin{pmatrix}F_{n+2}\\F_{n+1}\end{pmatrix}
=M\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}. M = ( 1 1 1 0 ) , ( F n + 2 F n + 1 ) = M ( F n + 1 F n ) .
一次矩陣作用把列狀態推進一步。歸納可得
( F n + 1 F n ) = M n ( 1 0 ) . \begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}
=M^n\begin{pmatrix}1\\0\end{pmatrix}. ( F n + 1 F n ) = M n ( 1 0 ) .
起始向量很重要:若使用另一種狀態約定,卻沿用同一輸出索引,可能差一步。指數零用單位矩陣,還原 ( F 1 , F 0 ) = ( 1 , 0 ) (F_1,F_0)=(1,0) ( F 1 , F 0 ) = ( 1 , 0 ) 。
例如 M 5 = ( 8 5 5 3 ) M^5=\begin{pmatrix}8&5\\5&3\end{pmatrix} M 5 = ( 8 5 5 3 ) ,第一列為 ( F 6 , F 5 ) = ( 8 , 5 ) (F_6,F_5)=(8,5) ( F 6 , F 5 ) = ( 8 , 5 ) 。二進冪只需對數次矩陣乘法。但精確斐波那契數的整數成本持續增長,F n F_n F n 有 Θ ( n ) \Theta(n) Θ ( n ) 位元,光是輸出就不容許把矩陣運算界當成 O ( log n ) O(\log n) O ( log n ) 位元時間。若只求餘數,可把矩陣運算全放在模 m 下。
例題 11.1.5
(以二進位步驟計算斐波那契矩陣冪)
以 5 = ( 101 ) 2 5=(101)_2 5 = ( 101 ) 2 計算 M 5 M^5 M 5 :e = 5 e=5 e = 5 時位元為 1,故 result = I ∘ M = M =I\circ M=M = I ∘ M = M ;指數變為 2 2 2 ,power = M 2 = ( 2 1 1 1 ) =M^2=\begin{pmatrix}2&1\\1&1\end{pmatrix} = M 2 = ( 2 1 1 1 ) 。e = 2 e=2 e = 2 時位元為 0,result 不變;指數變為 1 1 1 ,power = M 4 = ( 5 3 3 2 ) =M^4=\begin{pmatrix}5&3\\3&2\end{pmatrix} = M 4 = ( 5 3 3 2 ) 。e = 1 e=1 e = 1 時位元為 1,故 result = M ∘ M 4 = ( 8 5 5 3 ) =M\circ M^4=\begin{pmatrix}8&5\\5&3\end{pmatrix} = M ∘ M 4 = ( 8 5 5 3 ) ,指數變為 0 0 0 ,不再做最後的平方。兩次累積乘積與兩次平方共 4 = 2 + 3 − 1 4=2+3-1 4 = 2 + 3 − 1 次矩陣乘法。第一列 ( 8 , 5 ) = ( F 6 , F 5 ) (8,5)=(F_6,F_5) ( 8 , 5 ) = ( F 6 , F 5 ) 給出 F 5 = 5 F_5=5 F 5 = 5 。
計算矩陣冪時,result 必須由單位矩陣開始,而不是零矩陣。若用零矩陣,combine(result, power) 對任何指數都保持為零,連 M 1 M^1 M 1 也會被報告為零矩陣。指數為零時答案必須是單位矩陣,與 M 0 = I M^0=I M 0 = I 一致。
狀態是 ( F n + 1 , F n ) T = M n ( 1 , 0 ) T (F_{n+1},F_n)^{\mathsf T}=M^n(1,0)^{\mathsf T} ( F n + 1 , F n ) T = M n ( 1 , 0 ) T ,它的第一個分量是 F n + 1 F_{n+1} F n + 1 。對 n = 10 n=10 n = 10 ,( 89 , 55 ) (89,55) ( 89 , 55 ) 的第一個分量是 F 11 = 89 F_{11}=89 F 11 = 89 ,而不是 F 10 = 55 F_{10}=55 F 10 = 55 。
鄰接矩陣冪計數的是恰好指定長度的遊走
設 A 是有限有向圖的鄰接矩陣,A u v A_{uv} A uv 為 u 到 v 的邊數;行表示起點,列表示終點。容許自環與平行邊,不同邊選擇算不同遊走。
對每個整數 k ≥ 0 k\ge0 k ≥ 0 ,( A k ) u v (A^k)_{uv} ( A k ) uv 是 u 到 v 恰用 k 條邊的遊走數。遊走容許重複頂點與邊。
k = 0 k=0 k = 0 時,單位矩陣記錄每頂點到自身的一個空遊走,不同頂點間則沒有。假設 k 的結論成立。每個 u 到 v 的長度 k + 1 k+1 k + 1 遊走都有唯一倒數第二頂點 w;先選 u 到 w 的長度 k 遊走,再選 w 到 v 的一條邊,共 ( A k ) u w A w v (A^k)_{uw}A_{wv} ( A k ) u w A w v 種。對 w 求和不重不漏,正是矩陣乘法 ( A k + 1 ) u v = ∑ w ( A k ) u w A w v (A^{k+1})_{uv}=\sum\limits_w(A^k)_{uw}A_{wv} ( A k + 1 ) uv = w ∑ ( A k ) u w A w v 。
頂點為 0、1、2,邊是 0 → 0 0\to0 0 → 0 、0 → 1 0\to1 0 → 1 、1 → 2 1\to2 1 → 2 、2 → 0 2\to0 2 → 0 。因此
A = ( 1 1 0 0 0 1 1 0 0 ) , A 2 = ( 1 1 1 1 0 0 1 1 0 ) , A 3 = ( 2 1 1 1 1 0 1 1 1 ) . A=\begin{pmatrix}1&1&0\\0&0&1\\1&0&0\end{pmatrix},\quad
A^2=\begin{pmatrix}1&1&1\\1&0&0\\1&1&0\end{pmatrix},\quad
A^3=\begin{pmatrix}2&1&1\\1&1&0\\1&1&1\end{pmatrix}. A = 1 0 1 1 0 0 0 1 0 , A 2 = 1 1 1 1 0 1 1 0 0 , A 3 = 2 1 1 1 1 1 1 0 1 . ( A 3 ) 00 = 2 (A^3)_{00}=2 ( A 3 ) 00 = 2 計入 0 → 0 → 0 → 0 0\to0\to0\to0 0 → 0 → 0 → 0 與 0 → 1 → 2 → 0 0\to1\to2\to0 0 → 1 → 2 → 0 。它不是最短路徑距離;矩陣固定長度,計算所有選擇,包括重複。
反例模式
模計數為零不能證明不存在 有向菱形圖有邊 s → a s\to a s → a 、s → b s\to b s → b 、a → t a\to t a → t 、b → t b\to t b → t 。s 到 t 有兩個長度二遊走;模 2 計數為 0,遊走卻存在。對數量取模保留餘數,沒有保留以零/非零判可達的資訊。
精確長度 k 的計數也不描述所有較短遊走。若只有一邊 u → v u\to v u → v ,沒有其他邊,u 到 v 長度二計數為 0,長度一卻有遊走。選矩陣公式前,須先分清問題問恰好 k 邊、至多 k 邊,還是最短路徑。
附解答練習
練習 11.1.8
(用二進冪計算 5 11 m o d 13 5^{11}\bmod13 5 11 mod 13 ,並計算所給算法對 combine 的調用次數。說明指數為零時,模 13 和模 1 各返回甚麼,以及負指數是否為允許的輸入。)
核心
解答 (4) 1 列出重複平方的結果
由於 11 = ( 1011 ) 2 11=(1011)_2 11 = ( 1011 ) 2 ,需要的冪是 5 1 , 5 2 , 5 4 , 5 8 5^1,5^2,5^4,5^8 5 1 , 5 2 , 5 4 , 5 8 。模 13 時它們分別是 5 5 5 、5 2 = 25 ≡ 12 5^2=25\equiv12 5 2 = 25 ≡ 12 、12 2 = 144 ≡ 1 12^2=144\equiv1 1 2 2 = 144 ≡ 1 和 1 2 = 1 1^2=1 1 2 = 1 。
2 把 1 位元對應的冪相乘
5 ⋅ 12 ⋅ 1 = 60 ≡ 8 ( m o d 13 ) . 5\cdot12\cdot1=60\equiv8\pmod{13}. 5 ⋅ 12 ⋅ 1 = 60 ≡ 8 ( mod 13 ) . 依據: 11 中值為 1 的位元對應指數 1、2 和 8。
3 計算 combine 的調用次數
關鍵一步
有三個 1 位元,總共四個位元,所以次數是 3 + 4 − 1 = 6 3+4-1=6 3 + 4 − 1 = 6 :三次累積乘積和三次平方。
4 說明邊界情況
5 11 ≡ 8 ( m o d 13 ) 5^{11}\equiv8\pmod{13} 5 11 ≡ 8 ( mod 13 ) 。指數為零時返回幺半群的單位元,即模 13 的 1 1 1 與模 1 的 0 0 0 。負指數不屬於所述契約;它們需要可逆的底數及另外處理。
看下一步 (2/4) 全部展開
練習 11.1.9
(對下面的矩陣 P P P 和 Q Q Q ,計算 P Q PQ P Q 與 Q P QP QP ,求 P 5 P^5 P 5 ,並解釋為何 P Q ≠ Q P PQ\ne QP P Q = QP 不會令二進冪失效。)
核心
P = ( 1 1 0 1 ) , Q = ( 1 0 1 1 ) . P=\begin{pmatrix}1&1\\0&1\end{pmatrix},\qquad
Q=\begin{pmatrix}1&0\\1&1\end{pmatrix}. P = ( 1 0 1 1 ) , Q = ( 1 1 0 1 ) . 解答 (3) 1 計算兩個乘積
P Q = ( 2 1 1 1 ) , Q P = ( 1 1 1 2 ) . PQ=\begin{pmatrix}2&1\\1&1\end{pmatrix},\qquad
QP=\begin{pmatrix}1&1\\1&2\end{pmatrix}. P Q = ( 2 1 1 1 ) , QP = ( 1 1 1 2 ) . 2 找出 P 的冪的規律
因此對 n ≥ 0 n\ge0 n ≥ 0 有 P n = ( 1 n 0 1 ) P^n=\begin{pmatrix}1&n\\0&1\end{pmatrix} P n = ( 1 0 n 1 ) ,故 P 5 = ( 1 5 0 1 ) P^5=\begin{pmatrix}1&5\\0&1\end{pmatrix} P 5 = ( 1 0 5 1 ) 。
依據: P n + 1 = P n P P^{n+1}=P^nP P n + 1 = P n P 把左上角的 1 1 1 加到右上角,而 P 0 = I P^0=I P 0 = I 是歸納的起點。
3 解釋為何不可交換無妨
冪的證明只用結合律把同一個 P P P 的各份分組,從不交換兩個任意的輸入矩陣。因此不可交換性並不違反其不變量。
看下一步 (2/3) 全部展開
練習 11.1.10
(對所述的斐波那契轉移,利用下面的矩陣冪 M 10 M^{10} M 10 求 F 10 F_{10} F 10 。這個冪從 ( 1 , 0 ) (1,0) ( 1 , 0 ) 產生哪個列狀態向量?計算指數 10 時算法使用的矩陣乘法次數。)
核心
M 10 = ( 89 55 55 34 ) . M^{10}=\begin{pmatrix}89&55\\55&34\end{pmatrix}. M 10 = ( 89 55 55 34 ) . 解答 (3) 1 把冪作用於起始列向量
M 10 ( 1 0 ) = ( 89 55 ) = ( F 11 F 10 ) . M^{10}\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}89\\55\end{pmatrix}=\begin{pmatrix}F_{11}\\F_{10}\end{pmatrix}. M 10 ( 1 0 ) = ( 89 55 ) = ( F 11 F 10 ) . 2 讀取正確的分量
關鍵一步
第二個分量是 F 10 = 55 F_{10}=55 F 10 = 55 ;若返回第一個分量,得到的是下一個斐波那契數。
3 計算乘法次數
10 = ( 1010 ) 2 10=(1010)_2 10 = ( 1010 ) 2 有兩個 1 位元、共四個位元,所以算法使用 2 + 4 − 1 = 5 2+4-1=5 2 + 4 − 1 = 5 次矩陣乘法。
看下一步 (2/3) 全部展開
練習 11.1.11
(對三頂點的例圖,解釋 ( A 0 ) 00 (A^0)_{00} ( A 0 ) 00 與 ( A 0 ) 01 (A^0)_{01} ( A 0 ) 01 。列出 ( A 3 ) 00 (A^3)_{00} ( A 3 ) 00 所計的長度三遊走。若此元素以 2 為模計算並成為零,能否斷定不存在這樣的遊走?)
核心
解答 (3) 1 解釋單位矩陣的元素
A 0 A^0 A 0 是單位矩陣,所以 ( A 0 ) 00 = 1 (A^0)_{00}=1 ( A 0 ) 00 = 1 、( A 0 ) 01 = 0 (A^0)_{01}=0 ( A 0 ) 01 = 0 :由 0 到自身有一條空遊走,由 0 到 1 則沒有。
2 列出由 0 到 0 的長度三遊走
這兩條遊走是 0 → 0 → 0 → 0 0\to0\to0\to0 0 → 0 → 0 → 0 和 0 → 1 → 2 → 0 0\to1\to2\to0 0 → 1 → 2 → 0 ,所以 ( A 3 ) 00 = 2 (A^3)_{00}=2 ( A 3 ) 00 = 2 。
3 解釋模 2 的零
計數 2 2 2 在模 2 下成為 0 0 0 。這個零是正計數的餘數,不能作為不存在的證明。算法正確地回答了模計數的問題;所提出的可達性結論,要求它提供已被取模丟棄的資訊。
看下一步 (2/3) 全部展開