| 关于二进制GCD算法的注记 |
| |
| 引用本文： | 孙翠芳.关于二进制GCD算法的注记[J].中国科学技术大学学报,2004,34(1):126-127. |
| |
| 作者姓名： | 孙翠芳 |
| |
| 作者单位： | 安徽师范大学数学系,芜湖,241000 |
| |
| 摘 要： | 求两个正整数a、b的最大公因子 gcd (a ,b)通常使用经典的Euclid算法 .因共需O(lnN)次带余除法 ,每次带余除法耗时O(ln2 N) ,所以Euclid算法耗时O(ln \% 3 N) ,这里N =max(a ,b) ,文献 1 ,Corollary 2 .1 ]和 2 ,例 5]就是这样粗略估算的 .然而 ,如果在实现算法时考虑到每步带余除法被除数的位数在不断下降 ,总运行时间将仅为O(ln2 N) ,文献 3,p .32 8]和文献 4,p .1 3]指出并证明了这一点 ,在文献 5]定理 1的证明中也提到了这个事实 .1 96 1年Stein发明了一种求 gcd的新算法 (见 J .Comp .Phys .1 (1 96 7) ,397- 40 5]) ,简…
|
| 关 键 词： | 最大公因子(gcd) Euclid算法 二进制gcd算法 |
| 文章编号： | 0253-2778(2004)01-0126-02 |
| 修稿时间： | 2002年12月10 |
Notes on the Binary GCD Algorithm |
| |
| SUN Cui,fang.Notes on the Binary GCD Algorithm[J].Journal of University of Science and Technology of China,2004,34(1):126-127. |
| |
| Authors: | SUN Cui fang |
| |
| Abstract: | |
| |
| Keywords: | greatest common divisors (gcd) Euclid's algorithm binary gcd |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
