ANALYSIS OF A LEFT-SHIFT BINARY GCD ALGORITHM

Authors
SHALLIT J SORENSON J
Citation
J. Shallit et J. Sorenson, ANALYSIS OF A LEFT-SHIFT BINARY GCD ALGORITHM, Journal of symbolic computation, 17(6), 1994, pp. 473-486
Citations number
19
Categorie Soggetti
Mathematics,"Computer Sciences, Special Topics",Mathematics,"Computer Science Theory & Methods
Journal title
Journal of symbolic computation → ACNP
ISSN journal
07477171
Volume
17
Issue
6
Year of publication
1994
Pages
473 - 486
Database
ISI
SICI code
0747-7171(1994)17:6<473:AOALBG>2.0.ZU;2-1
Abstract
We introduce a new left-shift, binary algorithm, LSBGCD, for computing the greatest common divisor of two integers, and we provide an analys is of the worst-case behavior of this algorithm. The analysis depends on a theorem of Ramharter about the extremal behavior of certain conti nuants.