Return to udiv_qrnnd.c CVS log

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

Annotation of OpenXM_contrib/gmp/mpn/pa64/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:
                     28: mp_limb_t
                     29: #if __STDC__
                     30: __MPN(udiv_qrnnd) (mp_limb_t n1, mp_limb_t n0, mp_limb_t d, mp_limb_t *r)
                     31: #else
                     32: __MPN(udiv_qrnnd) (n1, n0, d, r)
                     33:      mp_limb_t n1;
                     34:      mp_limb_t n0;
                     35:      mp_limb_t d;
                     36:      mp_limb_t *r;
                     37: #endif
                     38: {
                     39:   mp_limb_t q1, q2, q;
                     40:   mp_limb_t p1, p0;
                     41:   double di, dq;
                     42:
                     43:   di = 1.0 / d;
                     44:
                     45:   /* Generate upper 53 bits of quotient.  Be careful here; the `double'
                     46:      quotient may be rounded to 2^64 which we cannot safely convert back
                     47:      to a 64-bit integer.  */
                     48:   dq = (TWO64 * (double) n1 + (double) n0) * di;
                     49:   if (dq >= TWO64)
                     50:     q1 = 0xfffffffffffff800LL;
                     51:   else
                     52:     q1 = (mp_limb_t) dq;
                     53:
                     54:   /* Multiply back in order to compare the product to the dividend.  */
                     55:   umul_ppmm (p1, p0, q1, d);
                     56:
                     57:   /* Was the 53-bit quotient greater that our sought quotient?  Test the
                     58:      sign of the partial remainder to find out.  */
                     59:   if (n1 < p1 || (n1 == p1 && n0 < p0))
                     60:     {
                     61:       /* 53-bit quotient too large.  Partial remainder is negative.
                     62:         Compute the absolute value of the remainder in n1,,n0.  */
                     63:       n1 = p1 - (n1 + (p0 < n0));
                     64:       n0 = p0 - n0;
                     65:
                     66:       /* Now use the partial remainder as new dividend to compute more bits of
                     67:         quotient.  This is an adjustment for the one we got previously.  */
                     68:       q2 = (mp_limb_t) ((TWO64 * (double) n1 + (double) n0) * di);
                     69:       umul_ppmm (p1, p0, q2, d);
                     70:
                     71:       q = q1 - q2;
                     72:       if (n1 < p1 || (n1 == p1 && n0 <= p0))
                     73:        {
                     74:          n0 = p0 - n0;
                     75:        }
                     76:       else
                     77:        {
                     78:          n0 = p0 - n0;
                     79:          n0 += d;
                     80:          q--;
                     81:        }
                     82:     }
                     83:   else
                     84:     {
                     85:       n1 = n1 - (p1 + (n0 < p0));
                     86:       n0 = n0 - p0;
                     87:
                     88:       q2 = (mp_limb_t) ((TWO64 * (double) n1 + (double) n0) * di);
                     89:       umul_ppmm (p1, p0, q2, d);
                     90:
                     91:       q = q1 + q2;
                     92:       if (n1 < p1 || (n1 == p1 && n0 < p0))
                     93:        {
                     94:          n0 = n0 - p0;
                     95:          n0 += d;
                     96:          q--;
                     97:        }
                     98:       else
                     99:        {
                    100:          n0 = n0 - p0;
                    101:          if (n0 >= d)
                    102:            {
                    103:              n0 -= d;
                    104:              q++;
                    105:            }
                    106:        }
                    107:     }
                    108:
                    109:   *r = n0;
                    110:   return q;
                    111: }