Luo et al wrote in a recent paper [A Fast Algorithm for Computing gcd Based on Binary Multi Precision,this journal,2002,Vol.32,No.5,pp.542 545; MR 2003h:11161 ] that “the classical Euclid’s algorithm for computing t...Luo et al wrote in a recent paper [A Fast Algorithm for Computing gcd Based on Binary Multi Precision,this journal,2002,Vol.32,No.5,pp.542 545; MR 2003h:11161 ] that “the classical Euclid’s algorithm for computing the gcd of two integers takes time O(\%ln\% 3N)”, and “present” an improved algorithm (called “binary gcd” for short) based on binary multi precision with time complexity O(\%ln\% 2N). In this paper,we point out two well known facts: firstly,the binary gcd,without usefull implimentation improvements, is identical in mathematical theory to Stein’s Binary GCD algorithm published in 1967; secondly,both Euclid’s algorithm and Binary GCD have the same time complexity O(\%ln\% 2N).展开更多
基金Supported by the Science and Technology Project Affiliated to the Education Department of Chongqing Municipality(KJ15012004)Scientific Research Innovation Team Project Affiliated to Yangtze Normal University(2016XJTD01)Science and Technology Plan Projects of Fuling Grant(FLKJ2015ABA1031)
文摘Luo et al wrote in a recent paper [A Fast Algorithm for Computing gcd Based on Binary Multi Precision,this journal,2002,Vol.32,No.5,pp.542 545; MR 2003h:11161 ] that “the classical Euclid’s algorithm for computing the gcd of two integers takes time O(\%ln\% 3N)”, and “present” an improved algorithm (called “binary gcd” for short) based on binary multi precision with time complexity O(\%ln\% 2N). In this paper,we point out two well known facts: firstly,the binary gcd,without usefull implimentation improvements, is identical in mathematical theory to Stein’s Binary GCD algorithm published in 1967; secondly,both Euclid’s algorithm and Binary GCD have the same time complexity O(\%ln\% 2N).
