动机
一个算法仅仅在若干例子上碰巧有效是不够的。它的证明必须说明:每次更新之后什么性质仍然成立,更新为什么最终会停止,以及最终状态为什么回答了最初的问题。整数算法使这些要求变得具体。欧几里得(Euclid)算法保持公因数以及线性组合证书;二进制幂运算则保持一个部分完成的幂的值。
定义
定义 4.1.1
(不变式与成本模型)
循环不变式是关于程序状态的一个命题,它在第一次迭代之前成立,并且被每一次迭代所保持。终止度量是一个非负整数,每当再执行一次迭代时它都严格减小。部分正确性是指:只要计算终止,它就返回正确的答案;完全正确性则还包括终止性。算术运算次数把每一种指定的算术运算都算作一步。比特复杂度则统计对单个二进制位的运算次数,因此对不断增长的整数所做的算术并不自动具有常数成本。
不变式与终止度量的作用不同。仅有不变式,它在一个无限的计算过程中也可能始终成立。仅有递减的度量,可以证明计算会停止,却不能说明其答案的含义。应当同时陈述两者,然后利用停止条件提取所需的结果。
定理/命题
定理 4.1.2
(扩展欧几里得算法返回一个证书)
对于整数 ,初始化 ,以及系数对 ,。当 时,令 ,并同时将各数对替换为
终止时,。共进行 次除法。
定理 4.1.3
(二进制幂运算)
给定 、 以及整数 ,初始化 。当 时,在每次迭代中写 ,其中 ,并同时设
输出为 。当 时,它至多使用 次模乘法,其中一次平方算作一次乘法。
证明思路
证明
(扩展欧几里得算法:证书、最大公因数与终止)
在扩展欧几里得算法中,证书不变式是对 有 。它在初始时成立;在同时更新之下,用一个等式减去 倍的另一个等式,恰好保持该不变式。一个数在更新之前同时整除两个余数,当且仅当它在更新之后同时整除两个余数。因此二者的最大公因数始终保持为 。新的第二个余数介于 与旧的 之间,这就证明了终止性。结束时第一个余数为正而第二个为零,于是该不变式给出了所宣称的证书。
关于除法次数:每连续两次除法,相关的正余数至少缩小为原来的一半。若下一个余数本身已不超过当前余数的一半,这是显然的;否则它们的商为一,而再下一个余数是二者之差,小于一半。经过 次除法之后,不再有正的余数。这是一个除法次数,并不意味着大整数的除法是常数时间。
证明透视
三个事实,三种分工
欧几里得算法的证明结合了三个事实,各自负责一件事。证书等式 得以保持,是因为余数列与两列系数都经历同一个线性更新 ;线性就是全部理由。最大公因数得以保持,是因为 与 有相同的公因数:前一对的公因数整除 ,后一对的公因数整除 。这两点都不依赖 的选取,任何整数都可以。只有终止性用到 ,因为它给出 。退出条件使论证闭合:当 时,当前的 就是上一步为正的 ,而 ,所以被保持的最大公因数就是当前第一个余数,被保持的等式则用 与 把它表示出来。
证明
(二进制幂运算:未完成幂的不变式)
在二进制幂运算中,不变式是 。对于 ,更新后的状态满足
模 约化把这一等式作为同余式保持下来。非负的度量 严格递减直至为零。此时不变式变为 。若 ,则不发生任何迭代,正确的结果是 。否则, 的每一个二进制位对应一次迭代,每次迭代包含一次平方以及至多一次额外的乘法。
例题详解
例题 4.1.4
(作为可验证输出的扩展欧几里得算法)
对于 ,各次的商为 ,余数为 。回代得到 。输出可以独立检验: 整除两个输入,并且是它们的整系数组合。任何公因数都必整除该组合,这就证明了它是最大公因数。
例题 4.1.5
(由证书得到模逆元)
对于 与 ,等式 给出 。确实 。如果最大公因数大于一,同一算法则会证明逆元不可能存在。
例题 4.1.6
(按二进制读取指数)
计算 ,其中 。状态 依次为 、、、、。因此答案是 。每次更新都使用旧的 来同时计算累积器与平方。若在累积器中使用已经平方过的 ,则表示的是另一个指数。
由所求答案设计不变式
不变式最有用之处,在于它把当前状态与原始输入联系起来。仅关于当前余数的断言,也许只能描述它们为正或递减的次序,却不能说明它们代表的是哪一对输入的最大公因数。保持最大公因数的不变式提供了这种联系。系数不变式则进一步加强了它:即使当前的余数可能小得多,它仍保留一个以原始输入表示的显式表达式。
最终的输出同时需要这两类信息。一个正的整数组合并不自动是最大公因数,因为可能的组合有很多。一个公因数也不自动是最大的。欧几里得算法对全部公因数的保持,加上最后的零余数,确定了正确的值,而系数等式则提供了一个简洁的证书。证明之所以行得通,是因为各次更新恰好在停止状态下保持了所需的信息。
对于二进制幂运算,人们容易说累积器始终等于到目前为止所求的答案。这个说法过于含糊,无法证明任何东西。累积器与剩余幂的乘积,给出了一个把状态与原始指数联系起来的精确等式。一旦剩余指数为零,未完成的因子就变为一,该陈述也就成为所要求的结论。不变式的形式正是为了使最后这一代入起决定作用而选定的。
两个证明都遵循同一个四步模式。首先在初始状态下核对不变式。其次证明一次迭代保持该不变式,并在每个更新的右侧都使用旧值。然后把不变式与退出条件结合,确定输出。最后给出一个严格递减的非负度量。前三步建立部分正确性;第四步把它提升为完全正确性。
同时更新与实现顺序
数学上的赋值记号常常掩盖了需要保留旧值这一点。在欧几里得更新中,新的第一个余数是旧的第二个余数,而新的第二个余数同时用到两个旧的余数。如果在计算第二个余数之前就覆盖了第一个余数,该表达式就不再是证明所假定的含义。同样的问题分别适用于两列系数。
直接的实现可以先把所有新值算入临时变量,然后替换旧的状态。另一种实现可以使用元组赋值,只要所用语言先计算右侧再覆盖左侧。只要与数学上的同时更新一致,两者都是正确的。重要的约定在于语义而不在于风格:下一个状态必须是已经证明过其不变式得到保持的那个状态。
符号与零输入也属于输入约定。定理是针对有序的正输入陈述的,这样每一步除法以及余数递减的论证都是显然的。对于一般带符号的输入,先取绝对值,单独处理零输入,必要时交换两个输入。得到绝对值的系数之后,再调整它们的符号与位置,以便用原始输入表示最大公因数。两个输入均为零时,需要在正输入定理之外明确给出一个约定。
为什么二进制位给出正确的分解
把当前指数写成商的两倍加上一个二进制位,就分离出了它的最低位二进制数字。若该位为一,则把当前底数的一个副本移入累积器。剩余的指数是偶数,所以它的贡献通过对底数平方并将指数减半来表示。若该位为零,则不移动任何副本,但平方与减半仍然保持总的幂不变。因此每次迭代恰好消耗一个二进制位。
这一推导比死记一连串奇偶判断与平方更清楚地解释了该算法。它也处理了指数为零的情形,而无须事后临时编造一个数学恒等式:循环什么也不做,未完成的指数已经是零,累积器为一就是正确的空积。这一计算约定与零次幂的代数定义一致。
在每一阶段,累积器与底数都可以约化到标准剩余范围。这就把所存数值的大小限制在模数以内,尽管未约化的幂可能极其巨大。指数并不对作为值的模数取模;它是按其二进制表示不断减半的。这就是该算法对非单位的底数同样适用的原因,包括与模数有公因数的底数。欧拉(Euler)式的指数约化与二进制幂运算是两种不同的方法,其假设也各不相同。
概念视角结构
平方求幂需要结合律
幂的不变式在不改变乘法顺序的前提下重新组织了重复的乘法。只要在相应的环境中解释幂与累积器,同一思想适用于矩阵或任何带单位元的结合乘法。模运算的版本还在每次乘积之后约化代表元。它不需要任何乘法逆元,因此该方法比关于单位阶的定理适用范围更广。
运算次数取决于输入的编码
一个整数的数值与其编码的长度是不同的度量。一个只有几百个二进制位的数,其数值可以极其巨大。因此,一个对不超过该数值的每个整数各执行一次迭代的算法,即使输入串很短,也可能不可行。二进制幂运算的循环就指数的编码长度而言是高效的,因为每次迭代去掉一个二进制位。
模数影响每次迭代的成本。位数更多的剩余需要更多的工作来相乘和约化。算术运算次数把控制结构单独分离出来,而比特界则把它与某种特定的乘法和约化方法结合起来。更快的整数算术可以降低每次运算的成本,而无须改变循环不变式的证明。反过来,使用低效的表示可能使实现的性能变差,却不会改变数学上的正确性。
对欧几里得算法的对数次除法,也应以同样的严谨态度来理解。这些除法涉及大小不断变化的整数,精确的比特分析必须考虑这些大小以及所选用的算术例程。这里证明的结果保证了除法序列很短,而不是每次除法的成本为常数。当比较输入为大整数而非小的机器字长数值的算法时,这一区别尤为重要。
计算之后的验证
模幂的结果,可以在已知某个小循环时与独立推出的循环核对,也可以与例题中指数的第二种分解核对。然而,一般的正确性证明来自不变式,其适用范围超出这些方便的例子。同样,所报告的逆元应当通过将它与原剩余相乘并对模数约化来检验。这最后一步直接验证了答案的定义性质。
对于所报告的最大公因数证书,应检查两个原始输入的整除性以及精确的线性组合等式。这些检查对发现符号错误与更新顺序错误特别有效。它们之所以简短,是因为证明已经说明了它们为什么蕴含所要的结论。好的验证以数学规格为指导,而不是机械地重复实现中的每一行。
常见错误
常见错误
(在旧值被使用前就覆盖它)
这些公式中的赋值是同时进行的。在普通代码中,应使用临时变量或谨慎排序的赋值;若在旧值被使用之前就覆盖了某个系数,就会破坏证书不变式。
常见错误
(对指数线性,对其长度却是指数级)
效率还取决于输入的表示。指数 约有 个二进制位,因此将 自乘 次,就指数的输入长度而言,可能需要指数级数量的运算。二进制幂运算就该长度而言使用线性数量的模乘法。若 有 位,则两个 位剩余的学校乘法与初等约化需要 次比特运算,因此当 时,这一实现的比特成本为 。这个界限针对的是一种特定的算术方法;它并不意味着每个软件库都使用该方法。
反例模式
指数约化需要底数是单位
声称:对所有 与所有 ,都有 。取 、、。则 而 ,于是该说法预言 ;但 。被丢掉的是欧拉定理的假设 ,这里 。有了这个假设,,把 写成 便知约化成立。二进制幂运算不需要这个假设:对 ,其状态 依次为 、、,并正确地返回 。
总结
欧几里得算法保持因数信息以及线性组合证书。二进制幂运算保持一个含有未完成指数的乘积。在每种情形下,递减的整数度量证明终止性,而明确声明的成本模型使复杂度的陈述有意义。
练习
快速检查
(利用整数证书,求 模 的逆元。)
必须检验最后的同余式。
解答 · 答案
,,,。回代得 。因此逆元是 ; 验证了这一点。
快速检查
(用逐次平方计算 ,并说明为什么把指数 对 取模不是一般的规则。)
指数的循环与作为值的模数是不同的对象。
解答 · 答案
模 ,,,。由于 ,所以 。指数约化必须使用诸如 这样的返回指数,而不是模数 。确实,指数 与 模 同余,但 而 。
快速检查
(对 、 执行扩展欧几里得算法。给出最大公因数与一个证书,并判断 模 是否可逆。)
同时数一数除法次数;最后一个非零余数就是答案。
解答 · 答案
,,,,,所以经过五次除法得 。回代得 ;确实 。由于最大公因数是 而不是 , 模 没有逆元:每个组合 都是偶数,不可能等于 。