Greatest Common Divisor

Let $a_1, \ldots, a_m$ be given nonzero integers. Then $g$ is called the greatest common divisor (GCD) of $a_1, \ldots, a_m$ if and only if it is the largest integer that divides all $a_1, \ldots, a_m$ .

Parameters

$n$ : sum of number of bits among the integers

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 4 of 4 algorithms


Sthele, Zimmermann	2006	$O(n \log^2 n \log \log n)$	$O(n)$
Binary GCD algorithm	1967	$O(n^2)$	$O(n)$
Lehmer's GCD algorithm	1940	$O(n^2)$	$O(n)$
Euclid's algorithm	-300	$O(n^2)$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms