Return to gcd_1.c CVS log

Up to [local] / OpenXM_contrib / gmp / mpn / generic

Annotation of OpenXM_contrib/gmp/mpn/generic/gcd_1.c, Revision 1.1.1.2

1.1       maekawa     1: /* mpn_gcd_1 --
                      2:
1.1.1.2 ! maekawa     3: Copyright (C) 1994, 1996, 2000 Free Software Foundation, Inc.
1.1       maekawa     4:
                      5: This file is part of the GNU MP Library.
                      6:
                      7: The GNU MP Library is free software; you can redistribute it and/or modify
1.1.1.2 ! maekawa     8: it under the terms of the GNU Lesser General Public License as published by
        !             9: the Free Software Foundation; either version 2.1 of the License, or (at your
1.1       maekawa    10: option) any later version.
                     11:
                     12: The GNU MP Library is distributed in the hope that it will be useful, but
                     13: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
1.1.1.2 ! maekawa    14: or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
1.1       maekawa    15: License for more details.
                     16:
1.1.1.2 ! maekawa    17: You should have received a copy of the GNU Lesser General Public License
1.1       maekawa    18: along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
                     19: the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
                     20: MA 02111-1307, USA. */
                     21:
                     22: #include "gmp.h"
                     23: #include "gmp-impl.h"
                     24: #include "longlong.h"
                     25:
                     26: /* Does not work for U == 0 or V == 0.  It would be tough to make it work for
                     27:    V == 0 since gcd(x,0) = x, and U does not generally fit in an mp_limb_t.  */
                     28:
                     29: mp_limb_t
1.1.1.2 ! maekawa    30: #if __STDC__
        !            31: mpn_gcd_1 (mp_srcptr up, mp_size_t size, mp_limb_t vlimb)
        !            32: #else
1.1       maekawa    33: mpn_gcd_1 (up, size, vlimb)
                     34:      mp_srcptr up;
                     35:      mp_size_t size;
                     36:      mp_limb_t vlimb;
1.1.1.2 ! maekawa    37: #endif
1.1       maekawa    38: {
                     39:   mp_limb_t ulimb;
                     40:   unsigned long int u_low_zero_bits, v_low_zero_bits;
                     41:
                     42:   if (size > 1)
                     43:     {
                     44:       ulimb = mpn_mod_1 (up, size, vlimb);
                     45:       if (ulimb == 0)
                     46:        return vlimb;
                     47:     }
                     48:   else
                     49:     ulimb = up[0];
                     50:
                     51:   /*  Need to eliminate low zero bits.  */
                     52:   count_trailing_zeros (u_low_zero_bits, ulimb);
                     53:   ulimb >>= u_low_zero_bits;
                     54:
                     55:   count_trailing_zeros (v_low_zero_bits, vlimb);
                     56:   vlimb >>= v_low_zero_bits;
                     57:
                     58:   while (ulimb != vlimb)
                     59:     {
                     60:       if (ulimb > vlimb)
                     61:        {
                     62:          ulimb -= vlimb;
                     63:          do
                     64:            ulimb >>= 1;
                     65:          while ((ulimb & 1) == 0);
                     66:        }
                     67:       else /*  vlimb > ulimb.  */
                     68:        {
                     69:          vlimb -= ulimb;
                     70:          do
                     71:            vlimb >>= 1;
                     72:          while ((vlimb & 1) == 0);
                     73:        }
                     74:     }
                     75:
                     76:   return  ulimb << MIN (u_low_zero_bits, v_low_zero_bits);
                     77: }