The accelerated integer GCD algorithm
Kenneth Weber · ACM Transactions on Mathematical Software · 1995
Since the greatest common divisor (GCD) of two integers is a basic arithmetic operation used in many mathematical software systems, new algorithms for its computation are of widespread interest. The accelerated integer GCD algorithm discussed here is based on a reduction step proposed by Sorenson ( k -ary reduction), coupled with the dmod operation similar to Norton's smod. Some practical limitations of Sorenson's reduction have been eliminated. Worst-case complexity is still O (n 2 ) for n -bit input, but actual implementations given input about 4096 bits long perform over 5.5 times as fast as the binary GCD on one computer architecture having a multiply instruction. Independent research by Jebelean points to the same conclusions.