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’)