Return to pow_1.c CVS log

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

Annotation of OpenXM_contrib/gmp/mpn/generic/pow_1.c, Revision 1.1

1.1     ! ohara       1: /* mpn_pow_1 -- Compute powers R = U^exp.
        !             2:
        !             3:    THE FUNCTIONS IN THIS FILE ARE FOR INTERNAL USE ONLY.  THEY'RE ALMOST
        !             4:    CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR COMPLETELY IN
        !             5:    FUTURE GNU MP RELEASES.
        !             6:
        !             7: Copyright 2002 Free Software Foundation, Inc.
        !             8:
        !             9: This file is part of the GNU MP Library.
        !            10:
        !            11: The GNU MP Library is free software; you can redistribute it and/or modify it
        !            12: under the terms of the GNU Lesser General Public License as published by the
        !            13: Free Software Foundation; either version 2.1 of the License, or (at your
        !            14: option) any later version.
        !            15:
        !            16: The GNU MP Library is distributed in the hope that it will be useful, but
        !            17: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
        !            18: FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
        !            19: for more details.
        !            20:
        !            21: You should have received a copy of the GNU Lesser General Public License along
        !            22: with the GNU MP Library; see the file COPYING.LIB.  If not, write to the Free
        !            23: Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
        !            24: USA.  */
        !            25:
        !            26:
        !            27: #include "gmp.h"
        !            28: #include "gmp-impl.h"
        !            29: #include "longlong.h"
        !            30:
        !            31: mp_size_t
        !            32: mpn_pow_1 (mp_ptr rp, mp_srcptr bp, mp_size_t bn, mp_limb_t exp, mp_ptr tp)
        !            33: {
        !            34:   mp_limb_t x;
        !            35:   int cnt, i;
        !            36:   mp_size_t rn;
        !            37:   int par;
        !            38:
        !            39:   if (exp <= 1)
        !            40:     {
        !            41:       if (exp == 0)
        !            42:        {
        !            43:          rp[0] = 1;
        !            44:          return 1;
        !            45:        }
        !            46:       else
        !            47:        {
        !            48:          MPN_COPY (rp, bp, bn);
        !            49:          return bn;
        !            50:        }
        !            51:     }
        !            52:
        !            53:   /* Count number of bits in exp, and compute where to put initial square in
        !            54:      order to magically get results in the entry rp.  Use simple code,
        !            55:      optimized for small exp.  For large exp, the bignum operations will take
        !            56:      so much time that the slowness of this code will be negligible.  */
        !            57:   par = 0;
        !            58:   cnt = GMP_LIMB_BITS;
        !            59:   for (x = exp; x != 0; x >>= 1)
        !            60:     {
        !            61:       par ^= x & 1;
        !            62:       cnt--;
        !            63:     }
        !            64:   exp <<= cnt;
        !            65:
        !            66:   if (bn == 1)
        !            67:     {
        !            68:       mp_limb_t bl = bp[0];
        !            69:
        !            70:       if ((cnt & 1) != 0)
        !            71:        MP_PTR_SWAP (rp, tp);
        !            72:
        !            73:       mpn_sqr_n (rp, bp, bn);
        !            74:       rn = 2 * bn; rn -= rp[rn - 1] == 0;
        !            75:
        !            76:       for (i = GMP_LIMB_BITS - cnt - 1;;)
        !            77:        {
        !            78:          exp <<= 1;
        !            79:          if ((exp & GMP_LIMB_HIGHBIT) != 0)
        !            80:            {
        !            81:              rp[rn] = mpn_mul_1 (rp, rp, rn, bl);
        !            82:              rn += rp[rn] != 0;
        !            83:            }
        !            84:
        !            85:          if (--i == 0)
        !            86:            break;
        !            87:
        !            88:          mpn_sqr_n (tp, rp, rn);
        !            89:          rn = 2 * rn; rn -= tp[rn - 1] == 0;
        !            90:          MP_PTR_SWAP (rp, tp);
        !            91:        }
        !            92:     }
        !            93:   else
        !            94:     {
        !            95:       if (((par ^ cnt) & 1) == 0)
        !            96:        MP_PTR_SWAP (rp, tp);
        !            97:
        !            98:       mpn_sqr_n (rp, bp, bn);
        !            99:       rn = 2 * bn; rn -= rp[rn - 1] == 0;
        !           100:
        !           101:       for (i = GMP_LIMB_BITS - cnt - 1;;)
        !           102:        {
        !           103:          exp <<= 1;
        !           104:          if ((exp & GMP_LIMB_HIGHBIT) != 0)
        !           105:            {
        !           106:              rn = rn + bn - (mpn_mul (tp, rp, rn, bp, bn) == 0);
        !           107:              MP_PTR_SWAP (rp, tp);
        !           108:            }
        !           109:
        !           110:          if (--i == 0)
        !           111:            break;
        !           112:
        !           113:          mpn_sqr_n (tp, rp, rn);
        !           114:          rn = 2 * rn; rn -= tp[rn - 1] == 0;
        !           115:          MP_PTR_SWAP (rp, tp);
        !           116:        }
        !           117:     }
        !           118:
        !           119:   return rn;
        !           120: }