Greatest Common Divisor in all languages

Greatest Common Divisor in Java

Posted: 2016-07-17 21:13, Last Updated: 2019-12-14 13:54

Java™ is a compiled language used for many purposes, ranging from embedded systems, UI-applications to web servers.

Greatest Common Divisor in C

Posted: 2019-11-22 22:51, Last Updated: 2019-11-23 16:37

C is a compiled language used for many purposes, although it can be primarily found in systems where importance is important. This is because C offers a lot of low-level support for optimization, at the cost of not having some of the convenient abstractions that other languages offer. C is therefore primarily found in situations where available computation power is low such as embedded systems, or situations where required computation power is high, such as simulation or deep learning.

See Code

Greatest Common Divisor in Javascript

Posted: 2019-11-24 20:01, Last Updated: 2019-12-14 16:32

JavaScript JavaScript is an interpreted scripting language previously primarily used in web pages (executed in browsers) that has since…

See Code

Greatest Common Divisor in Python

Posted: 2019-09-07 16:44, Last Updated: 2019-12-14 13:39

Python Python™ is an interpreted language used for many purposes ranging from embedded programming to web development, with one of the largest use cases being data science.

See Code

Greatest Common Divisor in R

Posted: 2019-11-23 15:50, Last Updated: 2019-12-20 20:30

R R is an interpreted language first released in 1993 with a significant increase in popularity in recent years. It is primarily used for data mining and -science as well as statistics, and is a popular language in non-computer science disciplines ranging from Biology to Physics. R is dynamically typed, and has one of the widest variety of libraries for statistics, machine learning, data mining etc.

See Code

About the algorithm:

Euclidean Greatest Common Divisor (GCD) Algorithm

The greatest common divisor of two numbers (in this case a and b) is the biggest number which both numbers can be divided by without a rest. This greatest common divisor algorithm, called the euclidean algorithm, determines this number. The greatest common divisor is also often abbreviated as gcd.

Description of the Algorithm

The basic principle behind thus gcd algorithm is to recursively determine the gcd of a and b by determining the gcd of b and a % b This hinges on the fact that the gcd of two numbers also divides their difference, e.g. the greatest common divisor of 16 and 24 (which is 8) is also the greatest common divisor of 24-16=8. This is therefore also true for 16 and 40 - in fact, rather than taking the difference, the remainder can also be used (repeatedly recursing on the difference will inevitable “pass” the remainder). In summary, the euclidean gcd algorithm uses these 2 steps:

if a or b is 0, return the other one.
Repeat with the new a as b and the new b as a % b.

Using the remainder has a much faster runtime compared to using the difference.

Example of the Algorithm

When computing the gcd of 1071 and 462, the following steps will be taken:

a is 1071, new b is 462
Recursing with new a = b and new b = a % b…
New a is 462, new b is 147
Recursing with new a = b and new b = a % b…
New a is 147, new b is 21
Recursing with new a = b and new b = a % b…
New a is 21, new b is 0
b is 0, stopping recursion, a is the gcd: 21

Runtime Complexity of the Algorithm

The runtime complexity of the Euclidean greatest common divisor algorithm is O(log(max(a,b))) (the logarithm of the maximum of the two numbers). Using the remainder rather than the difference is considerably faster - if the difference would’ve been used this greatest common divisor algorithm would’ve had a runtime of O(max(a,b))

Space Complexity of the Algorithm

The space complexity of the Euclidean greatest common divisor algorithm is equal to the runtime, since every recursive call is saved in the stack and everything else is constant.