2 Copyright (C) 2001-2002, 2006 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2001.
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2, or (at your option)
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
21 /* This file can also be used to define gcd functions for other unsigned
22 types, such as 'unsigned long long' or 'uintmax_t'. */
26 # define WORD_T unsigned long
32 /* Return the greatest common divisor of a > 0 and b > 0. */
34 GCD (WORD_T a, WORD_T b)
36 /* Why no division, as in Euclid's algorithm? Because in Euclid's algorithm
37 the division result floor(a/b) or floor(b/a) is very often = 1 or = 2,
38 and nearly always < 8. A sequence of a few subtractions and tests is
39 faster than a division. */
40 /* Why not Euclid's algorithm? Because the two integers can be shifted by 1
41 bit in a single instruction, and the algorithm uses fewer variables than
42 Euclid's algorithm. */
46 /* c = largest power of 2 that divides a and b. */
65 odd_odd: /* a/c and b/c both odd */
71 even_odd: /* a/c even, b/c odd */
79 odd_even: /* a/c odd, b/c even */