next up previous contents index Search
Next: Source Code Up: 0.5 Miscellaneous Algorithms Previous: References

0.5.6 Greatest Common Divisor, Least Common Multiple

The greatest common divisor of two integers, i and j, is the largest integer that divides both i and j exactly. Likewise the least common multiple of the same two integers is returns the smallest integer is an even multiple of both i and j. The given implementation of the greatest_common_div operation runs O(log m). Because the least_common_mul operation calls greatest_common_div, it, too, runs in logarithmic time. While these are not, in the strictest sense, ``computer science'' algorithms they may be useful to you nonetheless.

Scott Gasch