Re: [bug-gnulib] generic gcd

[Bruno Haible]

Oskar Liljeblad wrote:
> I propose this patch to make gcd generic.
> I needed an uintmax_t gcd for an application.

OK, I'm committing the appended patch.

I didn't apply your patch as-is because

  - There's no reason to omit the #include "gcd.h".

  - The name of the type should be uppercase, not gcd_t. It is common GNU style
    to use uppercase names for macros that cannot be used like functions.
    Notable exceptions to these rule are:
        memchr.c:# define reg_char char
        memcmp.c:# define op_t  unsigned long int
        memrchr.c:# define reg_char char
        offtostr.c:#define inttype off_t
        strftime.c:# define extra_args , ut, ns
        strftime.c:# define extra_args_spec , int ut, int ns
        tempname.c:# define struct_stat64 struct stat64
        tempname.c:# define struct_stat64 struct stat

  - The description of the module in the modules/* files should be a one-liner.
    Further doc belongs in the doc/ directory.

Bruno



2006-04-29  Bruno Haible  <address@hidden>

        * gcd.texi: New file.
        * gnulib.texi: Include it.

2006-04-29  Bruno Haible  <address@hidden>

        * gcd.c: Use WORD_T and GCD instead of unsigned long and gcd.
        Suggested by Oskar Liljeblad <address@hidden>.

diff -c -3 -r1.4 gcd.c
*** lib/gcd.c   14 May 2005 06:03:58 -0000      1.4
--- lib/gcd.c   29 Apr 2006 16:06:40 -0000
***************
*** 1,5 ****
  /* Arithmetic.
!    Copyright (C) 2001-2002 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2001.
  
     This program is free software; you can redistribute it and/or modify
--- 1,5 ----
  /* Arithmetic.
!    Copyright (C) 2001-2002, 2006 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2001.
  
     This program is free software; you can redistribute it and/or modify
***************
*** 16,29 ****
     along with this program; if not, write to the Free Software Foundation,
     Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  
  /* Specification.  */
! #include "gcd.h"
  
  #include <stdlib.h>
  
  /* Return the greatest common divisor of a > 0 and b > 0.  */
! unsigned long
! gcd (unsigned long a, unsigned long b)
  {
    /* Why no division, as in Euclid's algorithm? Because in Euclid's algorithm
       the division result floor(a/b) or floor(b/a) is very often = 1 or = 2,
--- 16,35 ----
     along with this program; if not, write to the Free Software Foundation,
     Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  
+ /* This file can also be used to define gcd functions for other unsigned
+    types, such as 'unsigned long long' or 'uintmax_t'.  */
+ #ifndef WORD_T
  /* Specification.  */
! # include "gcd.h"
! # define WORD_T unsigned long
! # define GCD gcd
! #endif
  
  #include <stdlib.h>
  
  /* Return the greatest common divisor of a > 0 and b > 0.  */
! WORD_T
! GCD (WORD_T a, WORD_T b)
  {
    /* Why no division, as in Euclid's algorithm? Because in Euclid's algorithm
       the division result floor(a/b) or floor(b/a) is very often = 1 or = 2,
***************
*** 33,39 ****
       bit in a single instruction, and the algorithm uses fewer variables than
       Euclid's algorithm.  */
  
!   unsigned long c = a | b;
    c = c ^ (c - 1);
    /* c = largest power of 2 that divides a and b.  */
  
--- 39,45 ----
       bit in a single instruction, and the algorithm uses fewer variables than
       Euclid's algorithm.  */
  
!   WORD_T c = a | b;
    c = c ^ (c - 1);
    /* c = largest power of 2 that divides a and b.  */