Return to udiv_qrnnd.c CVS log

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

Annotation of OpenXM_contrib/gmp/mpn/pa64w/udiv_qrnnd.c, Revision 1.1.1.1

1.1       maekawa     1: /*
                      2: Copyright (C) 1999, 2000 Free Software Foundation, Inc.
                      3:
                      4: This file is part of the GNU MP Library.
                      5:
                      6: The GNU MP Library is free software; you can redistribute it and/or modify
                      7: it under the terms of the GNU Lesser General Public License as published by
                      8: the Free Software Foundation; either version 2.1 of the License, or (at your
                      9: option) any later version.
                     10:
                     11: The GNU MP Library is distributed in the hope that it will be useful, but
                     12: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
                     13: or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
                     14: License for more details.
                     15:
                     16: You should have received a copy of the GNU Lesser General Public License
                     17: along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
                     18: the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
                     19: MA 02111-1307, USA.
                     20: */
                     21:
                     22: #include "gmp.h"
                     23: #include "gmp-impl.h"
                     24: #include "longlong.h"
                     25:
                     26: #define TWO64 18446744073709551616.0
                     27: #define TWO63 9223372036854775808.0
                     28:
                     29: mp_limb_t
                     30: #if __STDC__
                     31: __MPN(udiv_qrnnd) (mp_limb_t n1, mp_limb_t n0, mp_limb_t d, mp_limb_t *r)
                     32: #else
                     33: __MPN(udiv_qrnnd) (n1, n0, d, r)
                     34:      mp_limb_t n1;
                     35:      mp_limb_t n0;
                     36:      mp_limb_t d;
                     37:      mp_limb_t *r;
                     38: #endif
                     39: {
                     40:   mp_limb_t q1, q2, q;
                     41:   mp_limb_t p1, p0;
                     42:   double di, dq;
                     43:
                     44:   di = 1.0 / d;
                     45:
                     46:   /* Generate upper 53 bits of quotient.  Be careful here; the `double'
                     47:      quotient may be rounded to 2^64 which we cannot safely convert back
                     48:      to a 64-bit integer.  */
                     49:   dq = (TWO64 * (double) n1 + (double) n0) * di;
                     50:   if (dq >= TWO64)
                     51:     q1 = 0xfffffffffffff800L;
                     52: #ifndef __GNUC__
                     53:   /* Work around HP compiler bug.  */
                     54:   else if (dq > TWO63)
                     55:     q1 = (mp_limb_t) (dq - TWO63) + 0x8000000000000000L;
                     56: #endif
                     57:   else
                     58:     q1 = (mp_limb_t) dq;
                     59:
                     60:   /* Multiply back in order to compare the product to the dividend.  */
                     61:   umul_ppmm (p1, p0, q1, d);
                     62:
                     63:   /* Was the 53-bit quotient greater that our sought quotient?  Test the
                     64:      sign of the partial remainder to find out.  */
                     65:   if (n1 < p1 || (n1 == p1 && n0 < p0))
                     66:     {
                     67:       /* 53-bit quotient too large.  Partial remainder is negative.
                     68:         Compute the absolute value of the remainder in n1,,n0.  */
                     69:       n1 = p1 - (n1 + (p0 < n0));
                     70:       n0 = p0 - n0;
                     71:
                     72:       /* Now use the partial remainder as new dividend to compute more bits of
                     73:         quotient.  This is an adjustment for the one we got previously.  */
                     74:       q2 = (mp_limb_t) ((TWO64 * (double) n1 + (double) n0) * di);
                     75:       umul_ppmm (p1, p0, q2, d);
                     76:
                     77:       q = q1 - q2;
                     78:       if (n1 < p1 || (n1 == p1 && n0 <= p0))
                     79:        {
                     80:          n0 = p0 - n0;
                     81:        }
                     82:       else
                     83:        {
                     84:          n0 = p0 - n0;
                     85:          n0 += d;
                     86:          q--;
                     87:        }
                     88:     }
                     89:   else
                     90:     {
                     91:       n1 = n1 - (p1 + (n0 < p0));
                     92:       n0 = n0 - p0;
                     93:
                     94:       q2 = (mp_limb_t) ((TWO64 * (double) n1 + (double) n0) * di);
                     95:       umul_ppmm (p1, p0, q2, d);
                     96:
                     97:       q = q1 + q2;
                     98:       if (n1 < p1 || (n1 == p1 && n0 < p0))
                     99:        {
                    100:          n0 = n0 - p0;
                    101:          n0 += d;
                    102:          q--;
                    103:        }
                    104:       else
                    105:        {
                    106:          n0 = n0 - p0;
                    107:          if (n0 >= d)
                    108:            {
                    109:              n0 -= d;
                    110:              q++;
                    111:            }
                    112:        }
                    113:     }
                    114:
                    115:   *r = n0;
                    116:   return q;
                    117: }