指数减半,必须保留所计算的含义
求 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) 全部展开