| Webster's Online Dictionary |
| Expressions | Domain | Definition | |
| Euclid's Algorithm | Computing | Euclid's Algorithm (Or "Euclidean Algorithm") An algorithm for finding the greatest common divisor (GCD) of two numbers. It relies on the identity gcd (a, b)= gcd (a-b, b) To find the GCD of two numbers by this algorithm, repeatedly replace the larger by subtracting the smaller from it until the two numbers are equal. E.g. 132, 168 -> 132, 36 -> 96, 36 -> 60, 36 -> 24, 36 -> 24, 12 -> 12, 12 so the GCD of 132 and 168 is 12. This algorithm requires only subtraction and comparison operations but can take a number of steps proportional to the difference between the initial numbers (e.g.gcd (1, 1001) will take 1000 steps). (1997-06-30). Source: The Free On-line Dictionary of Computing.. | |
| Euclid's algorithm | Math | An algorithm to compute the greatest common divisor of two positive integers. It is Euclid (a, b){if (b=0) then return a; else return Euclid (b, a mod b); }. The run time complexity is O ((log a)(log b)) bit operations. (references) | |
| Extended Euclid's algorithm | Math | An algorithm to find the greatest common divisor, g, of two positive integers, a and b, and coefficients, h and j, such that g = ha + jb. (references) | |
Source: compiled by the editor from various references; see credits. | Top | ||
