为什么要计算除法次数
欧几里得(Euclid)算法通过反复带余除法计算最大公约数。证明结果正确只是分析的一半:我们还想知道,对于给定输入,算法要做多少次除法。答案具有精确的极值形式:若 且算法做了 次除法,则 和 至少分别是两个特定的相邻斐波那契(Fibonacci)数;这对斐波那契数恰好达到下界。
原因在于余数链的结构:每一步中,一个余数至少是后面两个余数之和。斐波那契递推则对应每一步都取等号的情况。建立这一点后,斐波那契数的增长就给出除法次数的对数上界。
还要区分两种成本:除法次数是对数级,不意味着位运算次数也是对数级。一次大整数除法本身可能很昂贵。以下始终把这两种度量分开。
定义
定义 1.2.1
(任意整数的最大公约数)
对于不全为零的整数 , 是同时整除两者的最大正整数。每个整数都整除 ,因此 没有最大的公约数。我们约定 。在此约定下,对任意整数 都有 ,并且 。
定义 1.2.2
(算法与除法次数)
给定整数 ,先取绝对值;若此时 ,就交换两者,使 。取绝对值和交换都不算除法。
若 ,返回 ,除法次数为零。特别地, 返回 ,算法绝不会除以零。
若 ,令 、。对 ,只要 就进行一次除法:
设首次出现零余数的下标为 ,即 。除法次数是 ,其中包括最后一次余数为零的除法;算法输出 。
定义 1.2.3
(斐波那契数)
定义 、,且对 ,。序列开始为
下面要注意重复的值 。序列从 起非递减,从 起严格递增。
正确性、终止性与贝祖系数
定理 1.2.4
(欧几里得不变量)
若 ,则 。
证明
(相邻数对的公约数)
若 同时整除 和 ,它就整除 。
反过来,若 整除 和 ,它也整除 。
因此两对数的公约数集合完全相同,从而最大公约数相同;若两数均为零,也依约定同为 。
余数满足 。非负整数不可能无限严格下降,所以至多经过 次除法就出现零余数,算法必定终止。沿余数链应用不变量,得到
定理 1.2.5
(扩展欧几里得不变量)
令 、、、,并定义
则每个 都满足 。特别地,。
证明
(对下标归纳)
和 时由初值直接成立。
假设等式对 和 成立,则
对于带符号的输入,先对 应用结论,若开始时交换过输入,先把系数交换回来,再将每个系数乘以对应原输入的符号;零输入的贡献为零。
斐波那契下界
定理 1.2.6
(除法次数的下界)
设 ,算法进行 次除法,则
证明
(从最后一个非零余数向前推)
我们证明对 ,有 。其中 和 分别给出两项结论。
情形 。 须证明 和 。首先 ;其次由 得 。这里直接用到了 。
情形 :初始步骤 。 最后一个非零余数为正,因此 。
情形 :初始步骤 。 最后一次除法为 。由于 , 是更早的除法以 为除数所得的余数,故 ,从而 。于是 。
情形 :归纳步骤。 取 ,令 ,则 。在除法 中,: 时这是假设 , 时来自余数严格递减。因此 ,而
证明透视
下界为何由下往上推,以及 $a$ 大于 $b$ 在哪里用到
证明从余数链的底部读起。除法 只要 ,便给出 ,这就是不等式形式的斐波那契递推;所以两个相邻余数的下界给出它们上方那个余数的下界。这也是归纳需要两个初始情形的原因:最后一个非零余数至少为 ,而它上方的余数至少为 ,因为 迫使 。
假设 只在最顶端的除法用到:它给出 ( 时则直接给出 )。较低位置的商自动至少为 ,因为余数严格递减。用同一条链分析等号:所有不等式同时取等号,恰好当 、 且其余的商都等于 ,此时这条链重现相邻的斐波那契数。
不能去掉 。若 ,算法只做一次除法 ,故 。下界 仍成立,但在 上 失败。证明中失效的正是 。
定理 1.2.7
(相邻斐波那契输入达到极值)
对每个 ,输入 恰好需要 次除法。除最后一次的商为 外,其余商均为 。
证明
(注意序列底部)
商为 1 的除法。 对 ,有
严格不等式成立是因为 ,所以这确是合法的带余除法。
余数链。 从 开始,数对依次变为 。这里对 各做一次除法,共 次。
最后一次除法。 虽然 ,余数 并不小于除数 ,所以它不是带余除法。正确的一步是 。
合计。 共 次除法。
令 ,输入 需要 次除法。因此定理中的下界对每个 都能达到; 时由 达到。向前推的证明中,每个不等式同时取等号,当且仅当 、 且此前各商均为 。
概念视角代数
把余数链写成矩阵乘积
每次除法可以写成 ,其中 的两行是 和 。把 次除法连起来,得到
各元素都是 的非负系数多项式,所以当 、 且其余商都等于 时, 与 最小;这时两行为 、 的矩阵的幂给出相邻的斐波那契数。由于 ,把乘积求逆便得到贝祖(Bézout)系数。
除法次数的对数上界
定理 1.2.8
(增长界)
当 时,。令 ,则当 时,。
证明
(利用 归纳)
第一个界在下文关于 的练习中证明。对于第二个界,注意 是 的正根。初始情形是 和 。当 时,归纳得到
应用增长界。 若 且做了 次除法,则 。 时这是上述定理; 时 ,且 。因此
推导 形式。 因为 ,所以 ,从而
时 ,因此对每个 都有 。使用 使表达式在 时也有意义。 时恰有一次除法 ,与两个上界均一致。
除法次数与位复杂度
假设两个输入各至多有 位。
除法次数。 ,故 。
一次除法的成本。 每次除法涉及的数至多有 位。普通竖式除法每次需 次位运算。
总成本。 因而 是有效的简单上界。这只是上界,更仔细的分析可以改进;这里不追求改进,也不声称它是最优位复杂度。
输入大小不只是 。 只计算除法次数,且只依赖较小输入。若 固定而 有 位,除法次数虽少,第一次除法仍须读取并除一个 位整数。位成本不能仅用 的函数来界定。
例题
例题 1.2.9
( 与贝祖系数)
除法。
故 ,。
回代。 第二式给出 ;第一式给出 。代入得
核对。 ,,两者之差为 。
扩展不变量。 商依次为 ,系数表给出 、、。 与回代一致;最后一对满足 ,符合不变量。
斐波那契界。 时,定理要求 和 ,两者都远大于下界。
例题 1.2.10
(相邻斐波那契输入 )
,故 ,预测有 次除法:
共七次除法,最大公约数为 。六个商为 ,最后一个商为 。
时,定理要求 、,两者都取等号。因此,没有满足 且 的数对需要七次除法。
例题 1.2.11
(相等输入与初始交换)
相等。 对 ,唯一一次除法 给出 ,最大公约数为 。
交换。 对 ,规范化将输入交换为 ,它需要 次除法,最大公约数为 。
另一种约定。 若不先交换,而立即执行 ,这一步以商 完成交换并额外计作一次除法,次数就是 。按本节约定,交换不计入除法,因此次数为 。
例题 1.2.12
(第一个商很大)
对 ,
故 。需要三次除法且满足 的最小 是 ,由 达到。 离最坏情形很远:第一个商 一步就消去了 的大部分。
较大的商使余数下降较快;如相邻斐波那契输入的例题,商为 时下降最慢。
常见错误
反例模式
除法次数为对数级不代表位成本为对数级
错误说法。 “算法做 次除法,因此运行时间是 。”
反驳。 取 ,令 是任意 位整数。
除法次数少。 第一个余数属于 ,因此最多做三次除法; 增长时次数仍有界。
每一位都有影响。 翻转 的第 位会使它改变 。这个变化不能被 整除,故会改变 。正确执行第一次除法因而必须依赖 的每一位。
结论。 位成本至少与 成正比,而 。计数除法衡量的是算术步骤,不是位运算量。
还有以下常见错误:
- 除以零。 的数对,包括 ,按约定立即返回。
- 断言位运算始终对输入位数呈线性增长。 这里在普通竖式除法下证明的是 位运算上界,并未声称更强结果。
常见错误
(漏掉最后一次除法)
有些作者不计最后一次零余数除法,次数比这里少一,斐波那契下标也会相应变化。必须先说明约定。
常见错误
(在 时套用 )
表明这一界需要 。
常见错误
(在斐波那契链末尾写 )
余数必须严格小于除数;正确的是 。
练习
快速检查
(对 运行算法,计算除法次数,并求整数 使 。)
解答
除法。
故 ,最大公约数为 。
回代。 从 开始,由 得
再由 ,
核对。 ,故 、。
系数表核对。 为 , 为 ,最后一对 与回代一致。
定理核对。 时要求 和 ,两者均成立。
快速检查
(计算 的除法次数,并与下界定理比较。)
解答
除法。
因此 。
比较。 输入是 ,故 ,极值定理预测 ,与计算一致。下界 和 均取等号。
快速检查
(按本节约定,求 时 、 以及 的输出和除法次数。)
解答
。 规范化将其交换为 。算法不做除法,返回 ;确有 。
。 算法不做除法,返回 。
。 算法返回 ,符合 的约定;不做除法,也不会尝试除以零。
每种情形的贝祖等式都可直接写出,例如 ,以及 。
快速检查
(证明 总需一次除法。准确说明 的证明在哪里失效,以及哪个界仍成立。)
解答
一次除法。 带余除法为 ,且 ,故 。
证明失效之处。 时,证明由 推出 ;当 时这一步不能使用,且 。对于相等的正输入,、,因此 仍成立;真正失效的是上述 时推出 的步骤。
仍成立的界。 仍成立。当 时, 恰好成立,但这并非由该定理推出。
快速检查
(对 ,其中 是 位整数,给出除法次数的上界。解释为何第一个商很大,以及为何位成本不可能与 无关。)
解答
次数上界。 写成 ,其中 。
- :共一次除法。
- :下一步是 ,共两次。
- :后续是 和 ,共三次。
故 ,与 的界一致。
第一个商。 ;由于 ,这个商约有 位。
位成本。 如反例所示,余数 依赖每一位;输出 本身也须写出约 位。因此第一次除法至少需要与 成正比的位运算。除法次数有界,位成本仍随 增长。
快速检查
(证明 时 ,再对 推出 。)
解答
初始情形。 ,。
归纳步骤。 对 ,序列从下标 起非递减,故 。应用 的归纳假设,得到
推论。 若 且做了 次除法,下界定理给出
取 得 ,即 。