南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）数论算法

计算机问题求解一论题4-5 数论算法 2021年3月29日

计算机问题求解 – 论题4-5 - 数论算法 2021年3月29日

这个乘法能“粗心” 地记为一次操作吗？ 问题1： 56789*98765= 讨论数论算法 511101 的复杂性有什 454312 么特殊之处？为 397523 什么？ 340734 283945 输入规模在增长时，算法时间开销的渐进增长性 5608765585 想想看，什么是输入规模？

输入规模在增长时，算法时间开销的渐进增长性 想想看，什么是输入规模？ 56789*98765= 511101 454312 397523 340734 283945 5608765585 这个乘法能“粗心” 地记为一次操作吗？

56789*98765= 511101 问题2： 454312 397523 你能解释以下 340734 下面的论断吗？ 283945 5608765585 In this model,multiplying two B-bit integers by the ordinary method uses (B2)bit operations

56789*98765= 511101 454312 397523 340734 283945 5608765585

可能是世界上最古老的算法 EUCLID(a,b) 1 ifb==0 2 return a 3 else return EUCLID(b,a mod b) 间题3：如何观察这个算法的复杂度？

可能是世界上最古老的算法

Le1ma31.10 If a >b 1 and the call EUCLID(a,b)performs k 1 recursive calls,then a≥Fk+2andb≥F+i 这个定理的直观含义是什么？

这个定理的直观含义是什么？

Lemma 31.10 If a >b 1 and the call EUCLID(a,b)performs k 1 recursive calls,then a≥Fk+2andb≥Fk+l 定理11可以由引理10直接得到。Why? Theorem 31.11 (Lame's theorem) For any integer k 1,if a >b 1 and b Fk+1,then the call EUCLID(a,b) makes fewer than k recursive calls

定理11可以由引理10直接得到。Why？

问题4： 定理中的界k是紧致的吗？ We can show that the upper bound of Theorem 31.11 is the best possible by showing that the call EUCLID(F+1,F)makes exactly k -1 recursive calls when k≥2. gcd(Fk+1,Fk)=gcd(Fk,Fk+1 mod Fk) gcd(Fk,Fk-1). GCD算法和斐波那契数列冥冥中是关联的

问题4： 定理中的界k是紧致的吗？ GCD算法和斐波那契数列冥冥中是关联的

GCD时间复杂度： Since Fk is approximatelyΦ/√5，where中is the golden ratio(I+√⑤)/2de fined by equation (3.24),the number of recursive calls in EUCLID is O(Ig b). 如果从两个B位数a,b角度看： Therefore,if we call EUCLID on two B-bit numbers,then it performs O(B)arithmetic operations and O(B3)bit operations

如果从两个β位数a，b角度看： GCD时间复杂度：

EXTENDED-EUCLID(a,b) 1 if b==0 2 return (a,1,0) 3 else (d',x',y')=EXTENDED-EUCLID(b,a mod b) 4 (d,x,y)=(d',y',x'-a/by) 5 return (d,x,y) 问题5： “扩充”的Euclid算法，扩充了什么？怎么实现 的？这个扩充的结果用处是什么？

EXTENDED-EUCLID(a,b) 1 ifb==0 2 return (a,1,0) 3 else (d',x',y')=EXTENDED-EUCLID(b,a mod b) 4 (d,x,y)=(d',y',x'-La/b]y') 5 return (d,x,y) d =d' =bx'+(a mod b)y' =bx'+(a-b[a/b])y =ay'+b(x'-[a/bly')

d =d’ =bx’+(a mod b)y’ =bx’+(a-b[a/b])y’ =ay’+b(x’-[a/b]y’)