I have been doing some research and I have found some algorithms that have greater than 0(N)
runtime. I am curious if anybody is aware of a linear time algorithm for finding the greatest common divisor?
Linear time algorithm for finding the greatest common divisor

Best Answer
If there is, noone has found it yet; from Wikipedia;

Relate
 Nasm Greatest common divisor
 Using Greatest Common Divisor fun
 Greatest common divisor VHDL FSM
 Euclidian greatest common divisor for more than two numbers
 How do I program a greatest common divisor program is 80x86 assembly?
 Finding CRC collisions for specific divisor
 Common Divisor Between 2 number With PHP [closed]
 Finding common elements in arrays
 Finding common clusters
 Linear Linked List  valid/common terminology?
 longest common subsequence with linear memory usage [closed]
 finding the character frequency in common lisp
 finding common sub trees in a tree
 Finding common elements in two arrays
 Finding common rows in 2 dataframes
N
in this case? The number of (binary) digits of the largest number? Also, what is the domain? Most GCD algorithms use division somewhere, and division isO(1)
for 64 bit integers, but at leastO(n)
for integers of arbitrary precision.N
is just the value of the largest integer, then the runtime complexity isO(log n)
even for the euclidean algorithm. This is much better thanO(n)
.