{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T05:46:42Z","timestamp":1648964802186},"reference-count":3,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[1998,10]]},"abstract":"<jats:p> Algorithms of computation of the Greatest Common Divisor (GCD) of two integers play a principal role in all computational systems dealing with rational arithmetic. The simplest one (Euclidean) is not the best for large numbers (see D. E. Knuth's book \"The Art of Computer Programming\" for details). <\/jats:p><jats:p> One improvement was suggested by D. H. Lehmer in 1938 who noticed that it is possible to run the Euclidean algorithm with a few leading digits of large numbers and, with some care, still obtain the correct answer. <\/jats:p><jats:p> In the 70's G. E. Collins pointed out that Lehmer's algorithm simultaneously analyzed two similar sequences of numbers and hence did twice as much work as necessary. Collins found a way to work with only one sequence of numbers together with a verification of a certain inequality. The proof of the validity of this inequality is, perhaps, too complicated. <\/jats:p><jats:p> We present a similar but softer inequality and give a short and simple proof thereof. <\/jats:p>","DOI":"10.1142\/s0218196798000296","type":"journal-article","created":{"date-parts":[[2003,7,31]],"date-time":"2003-07-31T10:08:41Z","timestamp":1059646121000},"page":"617-623","source":"Crossref","is-referenced-by-count":1,"title":["A Greatest Common Divisor Algorithm"],"prefix":"10.1142","volume":"08","author":[{"given":"Ari","family":"Belenkiy","sequence":"first","affiliation":[{"name":"Mathematics and Computer Science Department, Bar-Ilan University, Ramat-Gan, Israel"}]},{"given":"Raimundas","family":"Vidunas","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Groningen, P.O. Box 800, 9700 AV Groningen, The Netherlands"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.2307\/2302607"},{"key":"p_2","first-page":"189","author":"Collins G. E.","year":"1982","journal-title":"New York"},{"key":"p_5","first-page":"269","volume":"3","author":"Knuth D. E.","year":"1970","journal-title":"Congres. Int. Math."}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196798000296","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T21:54:33Z","timestamp":1565128473000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196798000296"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,10]]},"references-count":3,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1998,10]]}},"alternative-id":["10.1142\/S0218196798000296"],"URL":"https:\/\/doi.org\/10.1142\/s0218196798000296","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,10]]}}}