xref: /dragonfly/contrib/gmp/mpq/get_d.c (revision 86d7f5d3)
1 /* double mpq_get_d (mpq_t src) -- mpq to double, rounding towards zero.
2 
3 Copyright 1995, 1996, 2001, 2002, 2003, 2004, 2005 Free Software Foundation,
4 Inc.
5 
6 This file is part of the GNU MP Library.
7 
8 The GNU MP Library is free software; you can redistribute it and/or modify
9 it under the terms of the GNU Lesser General Public License as published by
10 the Free Software Foundation; either version 3 of the License, or (at your
11 option) any later version.
12 
13 The GNU MP Library is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
16 License for more details.
17 
18 You should have received a copy of the GNU Lesser General Public License
19 along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
20 
21 #include <stdio.h>  /* for NULL */
22 #include "gmp.h"
23 #include "gmp-impl.h"
24 #include "longlong.h"
25 
26 
27 /* All that's needed is to get the high 53 bits of the quotient num/den,
28    rounded towards zero.  More than 53 bits is fine, any excess is ignored
29    by mpn_get_d.
30 
31    N_QLIMBS is how many quotient limbs we need to satisfy the mantissa of a
32    double, assuming the highest of those limbs is non-zero.  The target
33    qsize for mpn_tdiv_qr is then 1 more than this, since that function may
34    give a zero in the high limb (and non-zero in the second highest).
35 
36    The use of 8*sizeof(double) in N_QLIMBS is an overestimate of the
37    mantissa bits, but it gets the same result as the true value (53 or 48 or
38    whatever) when rounded up to a multiple of GMP_NUMB_BITS, for non-nails.
39 
40    Enhancements:
41 
42    Use the true mantissa size in the N_QLIMBS formula, to save a divide step
43    in nails.
44 
45    Examine the high limbs of num and den to see if the highest 1 bit of the
46    quotient will fall high enough that just N_QLIMBS-1 limbs is enough to
47    get the necessary bits, thereby saving a division step.
48 
49    Bit shift either num or den to arrange for the above condition on the
50    high 1 bit of the quotient, to save a division step always.  A shift to
51    save a division step is definitely worthwhile with mpn_tdiv_qr, though we
52    may want to reassess this on big num/den when a quotient-only division
53    exists.
54 
55    Maybe we could estimate the final exponent using nsize-dsize (and
56    possibly the high limbs of num and den), so as to detect overflow and
57    return infinity or zero quickly.  Overflow is never very helpful to an
58    application, and can therefore probably be regarded as abnormal, but we
59    may still like to optimize it if the conditions are easy.  (This would
60    only be for float formats we know, unknown formats are not important and
61    can be left to mpn_get_d.)
62 
63    Future:
64 
65    If/when mpn_tdiv_qr supports its qxn parameter we can use that instead of
66    padding n with zeros in temporary space.
67 
68    If/when a quotient-only division exists it can be used here immediately.
69    remp is only to satisfy mpn_tdiv_qr, the remainder is not used.
70 
71    Alternatives:
72 
73    An alternative algorithm, that may be faster:
74    0. Let n be somewhat larger than the number of significant bits in a double.
75    1. Extract the most significant n bits of the denominator, and an equal
76       number of bits from the numerator.
77    2. Interpret the extracted numbers as integers, call them a and b
78       respectively, and develop n bits of the fractions ((a + 1) / b) and
79       (a / (b + 1)) using mpn_divrem.
80    3. If the computed values are identical UP TO THE POSITION WE CARE ABOUT,
81       we are done.  If they are different, repeat the algorithm from step 1,
82       but first let n = n * 2.
83    4. If we end up using all bits from the numerator and denominator, fall
84       back to a plain division.
85    5. Just to make life harder, The computation of a + 1 and b + 1 above
86       might give carry-out...  Needs special handling.  It might work to
87       subtract 1 in both cases instead.
88 
89    Not certain if this approach would be faster than a quotient-only
90    division.  Presumably such optimizations are the sort of thing we would
91    like to have helping everywhere that uses a quotient-only division. */
92 
93 double
mpq_get_d(const MP_RAT * src)94 mpq_get_d (const MP_RAT *src)
95 {
96   double res;
97   mp_srcptr np, dp;
98   mp_ptr remp, tp;
99   mp_size_t nsize = src->_mp_num._mp_size;
100   mp_size_t dsize = src->_mp_den._mp_size;
101   mp_size_t qsize, prospective_qsize, zeros, chop, tsize;
102   mp_size_t sign_quotient = nsize;
103   long exp;
104 #define N_QLIMBS (1 + (sizeof (double) + BYTES_PER_MP_LIMB-1) / BYTES_PER_MP_LIMB)
105   mp_limb_t qarr[N_QLIMBS + 1];
106   mp_ptr qp = qarr;
107   TMP_DECL;
108 
109   ASSERT (dsize > 0);    /* canonical src */
110 
111   /* mpn_get_d below requires a non-zero operand */
112   if (UNLIKELY (nsize == 0))
113     return 0.0;
114 
115   TMP_MARK;
116   nsize = ABS (nsize);
117   dsize = ABS (dsize);
118   np = src->_mp_num._mp_d;
119   dp = src->_mp_den._mp_d;
120 
121   prospective_qsize = nsize - dsize + 1;   /* from using given n,d */
122   qsize = N_QLIMBS + 1;                    /* desired qsize */
123 
124   zeros = qsize - prospective_qsize;       /* padding n to get qsize */
125   exp = (long) -zeros * GMP_NUMB_BITS;     /* relative to low of qp */
126 
127   chop = MAX (-zeros, 0);                  /* negative zeros means shorten n */
128   np += chop;
129   nsize -= chop;
130   zeros += chop;                           /* now zeros >= 0 */
131 
132   tsize = nsize + zeros;                   /* size for possible copy of n */
133 
134   if (WANT_TMP_DEBUG)
135     {
136       /* separate blocks, for malloc debugging */
137       remp = TMP_ALLOC_LIMBS (dsize);
138       tp = (zeros > 0 ? TMP_ALLOC_LIMBS (tsize) : NULL);
139     }
140   else
141     {
142       /* one block with conditionalized size, for efficiency */
143       remp = TMP_ALLOC_LIMBS (dsize + (zeros > 0 ? tsize : 0));
144       tp = remp + dsize;
145     }
146 
147   /* zero extend n into temporary space, if necessary */
148   if (zeros > 0)
149     {
150       MPN_ZERO (tp, zeros);
151       MPN_COPY (tp+zeros, np, nsize);
152       np = tp;
153       nsize = tsize;
154     }
155 
156   ASSERT (qsize == nsize - dsize + 1);
157   mpn_tdiv_qr (qp, remp, (mp_size_t) 0, np, nsize, dp, dsize);
158 
159   /* strip possible zero high limb */
160   qsize -= (qp[qsize-1] == 0);
161 
162   res = mpn_get_d (qp, qsize, sign_quotient, exp);
163   TMP_FREE;
164   return res;
165 }
166