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.3

1.1.1.3 ! ohara       1: /* mpn_gcd_1 -- mpn and limb greatest common divisor.
1.1       maekawa     2:
1.1.1.3 ! ohara       3: Copyright 1994, 1996, 2000, 2001 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:
1.1.1.3 ! ohara      26:
1.1       maekawa    27: /* Does not work for U == 0 or V == 0.  It would be tough to make it work for
1.1.1.3 ! ohara      28:    V == 0 since gcd(x,0) = x, and U does not generally fit in an mp_limb_t.
        !            29:
        !            30:    The threshold for doing u%v when size==1 will vary by CPU according to
        !            31:    the speed of a division and the code generated for the main loop.  Any
        !            32:    tuning for this is left to a CPU specific implementation.  */
1.1       maekawa    33:
                     34: mp_limb_t
1.1.1.2   maekawa    35: mpn_gcd_1 (mp_srcptr up, mp_size_t size, mp_limb_t vlimb)
1.1       maekawa    36: {
1.1.1.3 ! ohara      37:   mp_limb_t      ulimb;
        !            38:   unsigned long  zero_bits, u_low_zero_bits;
        !            39:
        !            40:   ASSERT (size >= 1);
        !            41:   ASSERT (vlimb != 0);
        !            42:   ASSERT_MPN_NONZERO_P (up, size);
        !            43:
        !            44:   ulimb = up[0];
        !            45:
        !            46:   /* Need vlimb odd for modexact, want it odd to get common zeros. */
        !            47:   count_trailing_zeros (zero_bits, vlimb);
        !            48:   vlimb >>= zero_bits;
1.1       maekawa    49:
                     50:   if (size > 1)
                     51:     {
1.1.1.3 ! ohara      52:       /* Must get common zeros before the mod reduction.  If ulimb==0 then
        !            53:         vlimb already gives the common zeros.  */
        !            54:       if (ulimb != 0)
        !            55:        {
        !            56:          count_trailing_zeros (u_low_zero_bits, ulimb);
        !            57:          zero_bits = MIN (zero_bits, u_low_zero_bits);
        !            58:        }
        !            59:
        !            60:       ulimb = MPN_MOD_OR_MODEXACT_1_ODD (up, size, vlimb);
1.1       maekawa    61:       if (ulimb == 0)
1.1.1.3 ! ohara      62:        goto done;
        !            63:
        !            64:       goto strip_u_maybe;
1.1       maekawa    65:     }
                     66:
1.1.1.3 ! ohara      67:   /* size==1, so up[0]!=0 */
1.1       maekawa    68:   count_trailing_zeros (u_low_zero_bits, ulimb);
                     69:   ulimb >>= u_low_zero_bits;
1.1.1.3 ! ohara      70:   zero_bits = MIN (zero_bits, u_low_zero_bits);
1.1       maekawa    71:
1.1.1.3 ! ohara      72:   /* make u bigger */
        !            73:   if (vlimb > ulimb)
        !            74:     MP_LIMB_T_SWAP (ulimb, vlimb);
        !            75:
        !            76:   /* if u is much bigger than v, reduce using a division rather than
        !            77:      chipping away at it bit-by-bit */
        !            78:   if ((ulimb >> 16) > vlimb)
        !            79:     {
        !            80:       ulimb %= vlimb;
        !            81:       if (ulimb == 0)
        !            82:        goto done;
        !            83:       goto strip_u_maybe;
        !            84:     }
1.1       maekawa    85:
                     86:   while (ulimb != vlimb)
                     87:     {
1.1.1.3 ! ohara      88:       ASSERT (ulimb & 1);
        !            89:       ASSERT (vlimb & 1);
        !            90:
1.1       maekawa    91:       if (ulimb > vlimb)
                     92:        {
                     93:          ulimb -= vlimb;
                     94:          do
1.1.1.3 ! ohara      95:            {
        !            96:              ulimb >>= 1;
        !            97:              ASSERT (ulimb != 0);
        !            98:            strip_u_maybe:
        !            99:              ;
        !           100:            }
1.1       maekawa   101:          while ((ulimb & 1) == 0);
                    102:        }
                    103:       else /*  vlimb > ulimb.  */
                    104:        {
                    105:          vlimb -= ulimb;
                    106:          do
1.1.1.3 ! ohara     107:            {
        !           108:              vlimb >>= 1;
        !           109:              ASSERT (vlimb != 0);
        !           110:            }
1.1       maekawa   111:          while ((vlimb & 1) == 0);
                    112:        }
                    113:     }
                    114:
1.1.1.3 ! ohara     115:  done:
        !           116:   return vlimb << zero_bits;
1.1       maekawa   117: }