Number Gems

Euclidean algorithm

The algorithm is a simple method to compute the greatest common divisor (GCD).

Code (JavaScript) Sample
 Number.prototype.gcd = function(m, n) {
    if (n == 0)
        return m;
    if (m < n)
        return this.gcd(n, m);
    while (n != 0) {
        var odd = m % n;
        m = n;
        n = odd;
    }
    return m;
};
GCD(,) =

References

  1. Friendly Introduction to Number Theory, A (3rd Edition)
Topic revision: r3 - 2011-06-29 - 16:02:16 - SatoshiKonno
 

Copyright © 2012 by Satoshi Konno Powerd by TWiki logoTWiki.