Calculate GCD (JavaScript)

Program

Description

This JavaScript program calculates the greatest common divisor (GCD) of the given two non-negative integers. The code implements big integer arithmetic, hence the numbers can be arbitrarily big (though computation time is the limiting factor). This implements the binary GCD algorithm, which runs in Θ(n²) time with respect to the bit length of the numbers. The source TypeScript code and compiled JavaScript code are available for viewing.

Examples

• gcd(0, 2) = 2.
• gcd(3, 5) = 1.
• gcd(24, 18) = 6.

More info

• Wikipedia: Greatest common divisor
• Wikipedia: Binary GCD algorithm
• MathWorld: Greatest Common Divisor