1/* mpfr_sqrt -- square root of a floating-point number 2 3Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 Free Software Foundation, Inc. 4Contributed by the AriC and Caramel projects, INRIA. 5 6This file is part of the GNU MPFR Library. 7 8The GNU MPFR Library is free software; you can redistribute it and/or modify 9it under the terms of the GNU Lesser General Public License as published by 10the Free Software Foundation; either version 3 of the License, or (at your 11option) any later version. 12 13The GNU MPFR Library is distributed in the hope that it will be useful, but 14WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 15or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 16License for more details. 17 18You should have received a copy of the GNU Lesser General Public License 19along with the GNU MPFR Library; see the file COPYING.LESSER. If not, see 20http://www.gnu.org/licenses/ or write to the Free Software Foundation, Inc., 2151 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. */ 22 23#include "mpfr-impl.h" 24 25int 26mpfr_sqrt (mpfr_ptr r, mpfr_srcptr u, mpfr_rnd_t rnd_mode) 27{ 28 mp_size_t rsize; /* number of limbs of r (plus 1 if exact limb multiple) */ 29 mp_size_t rrsize; 30 mp_size_t usize; /* number of limbs of u */ 31 mp_size_t tsize; /* number of limbs of the sqrtrem remainder */ 32 mp_size_t k; 33 mp_size_t l; 34 mpfr_limb_ptr rp, rp0; 35 mpfr_limb_ptr up; 36 mpfr_limb_ptr sp; 37 mp_limb_t sticky0; /* truncated part of input */ 38 mp_limb_t sticky1; /* truncated part of rp[0] */ 39 mp_limb_t sticky; 40 int odd_exp; 41 int sh; /* number of extra bits in rp[0] */ 42 int inexact; /* return ternary flag */ 43 mpfr_exp_t expr; 44 MPFR_TMP_DECL(marker); 45 46 MPFR_LOG_FUNC 47 (("x[%Pu]=%.*Rg rnd=%d", mpfr_get_prec (u), mpfr_log_prec, u, rnd_mode), 48 ("y[%Pu]=%.*Rg inexact=%d", 49 mpfr_get_prec (r), mpfr_log_prec, r, inexact)); 50 51 if (MPFR_UNLIKELY(MPFR_IS_SINGULAR(u))) 52 { 53 if (MPFR_IS_NAN(u)) 54 { 55 MPFR_SET_NAN(r); 56 MPFR_RET_NAN; 57 } 58 else if (MPFR_IS_ZERO(u)) 59 { 60 /* 0+ or 0- */ 61 MPFR_SET_SAME_SIGN(r, u); 62 MPFR_SET_ZERO(r); 63 MPFR_RET(0); /* zero is exact */ 64 } 65 else 66 { 67 MPFR_ASSERTD(MPFR_IS_INF(u)); 68 /* sqrt(-Inf) = NAN */ 69 if (MPFR_IS_NEG(u)) 70 { 71 MPFR_SET_NAN(r); 72 MPFR_RET_NAN; 73 } 74 MPFR_SET_POS(r); 75 MPFR_SET_INF(r); 76 MPFR_RET(0); 77 } 78 } 79 if (MPFR_UNLIKELY(MPFR_IS_NEG(u))) 80 { 81 MPFR_SET_NAN(r); 82 MPFR_RET_NAN; 83 } 84 MPFR_SET_POS(r); 85 86 MPFR_TMP_MARK (marker); 87 MPFR_UNSIGNED_MINUS_MODULO(sh,MPFR_PREC(r)); 88 if (sh == 0 && rnd_mode == MPFR_RNDN) 89 sh = GMP_NUMB_BITS; /* ugly case */ 90 rsize = MPFR_LIMB_SIZE(r) + (sh == GMP_NUMB_BITS); 91 /* rsize is the number of limbs of r + 1 if exact limb multiple and rounding 92 to nearest, this is the number of wanted limbs for the square root */ 93 rrsize = rsize + rsize; 94 usize = MPFR_LIMB_SIZE(u); /* number of limbs of u */ 95 rp0 = MPFR_MANT(r); 96 rp = (sh < GMP_NUMB_BITS) ? rp0 : MPFR_TMP_LIMBS_ALLOC (rsize); 97 up = MPFR_MANT(u); 98 sticky0 = MPFR_LIMB_ZERO; /* truncated part of input */ 99 sticky1 = MPFR_LIMB_ZERO; /* truncated part of rp[0] */ 100 odd_exp = (unsigned int) MPFR_GET_EXP (u) & 1; 101 inexact = -1; /* return ternary flag */ 102 103 sp = MPFR_TMP_LIMBS_ALLOC (rrsize); 104 105 /* copy the most significant limbs of u to {sp, rrsize} */ 106 if (MPFR_LIKELY(usize <= rrsize)) /* in case r and u have the same precision, 107 we have indeed rrsize = 2 * usize */ 108 { 109 k = rrsize - usize; 110 if (MPFR_LIKELY(k)) 111 MPN_ZERO (sp, k); 112 if (odd_exp) 113 { 114 if (MPFR_LIKELY(k)) 115 sp[k - 1] = mpn_rshift (sp + k, up, usize, 1); 116 else 117 sticky0 = mpn_rshift (sp, up, usize, 1); 118 } 119 else 120 MPN_COPY (sp + rrsize - usize, up, usize); 121 } 122 else /* usize > rrsize: truncate the input */ 123 { 124 k = usize - rrsize; 125 if (odd_exp) 126 sticky0 = mpn_rshift (sp, up + k, rrsize, 1); 127 else 128 MPN_COPY (sp, up + k, rrsize); 129 l = k; 130 while (sticky0 == MPFR_LIMB_ZERO && l != 0) 131 sticky0 = up[--l]; 132 } 133 134 /* sticky0 is non-zero iff the truncated part of the input is non-zero */ 135 136 /* mpn_rootrem with NULL 2nd argument is faster than mpn_sqrtrem, thus use 137 it if available and if the user asked to use GMP internal functions */ 138#if defined(WANT_GMP_INTERNALS) && defined(HAVE___GMPN_ROOTREM) 139 tsize = __gmpn_rootrem (rp, NULL, sp, rrsize, 2); 140#else 141 tsize = mpn_sqrtrem (rp, NULL, sp, rrsize); 142#endif 143 144 /* a return value of zero in mpn_sqrtrem indicates a perfect square */ 145 sticky = sticky0 || tsize != 0; 146 147 /* truncate low bits of rp[0] */ 148 sticky1 = rp[0] & ((sh < GMP_NUMB_BITS) ? MPFR_LIMB_MASK(sh) 149 : ~MPFR_LIMB_ZERO); 150 rp[0] -= sticky1; 151 152 sticky = sticky || sticky1; 153 154 expr = (MPFR_GET_EXP(u) + odd_exp) / 2; /* exact */ 155 156 if (rnd_mode == MPFR_RNDZ || rnd_mode == MPFR_RNDD || sticky == MPFR_LIMB_ZERO) 157 { 158 inexact = (sticky == MPFR_LIMB_ZERO) ? 0 : -1; 159 goto truncate; 160 } 161 else if (rnd_mode == MPFR_RNDN) 162 { 163 /* if sh < GMP_NUMB_BITS, the round bit is bit (sh-1) of sticky1 164 and the sticky bit is formed by the low sh-1 bits from 165 sticky1, together with the sqrtrem remainder and sticky0. */ 166 if (sh < GMP_NUMB_BITS) 167 { 168 if (sticky1 & (MPFR_LIMB_ONE << (sh - 1))) 169 { /* round bit is set */ 170 if (sticky1 == (MPFR_LIMB_ONE << (sh - 1)) && tsize == 0 171 && sticky0 == 0) 172 goto even_rule; 173 else 174 goto add_one_ulp; 175 } 176 else /* round bit is zero */ 177 goto truncate; /* with the default inexact=-1 */ 178 } 179 else /* sh = GMP_NUMB_BITS: the round bit is the most significant bit 180 of rp[0], and the remaining GMP_NUMB_BITS-1 bits contribute to 181 the sticky bit */ 182 { 183 if (sticky1 & MPFR_LIMB_HIGHBIT) 184 { /* round bit is set */ 185 if (sticky1 == MPFR_LIMB_HIGHBIT && tsize == 0 && sticky0 == 0) 186 goto even_rule; 187 else 188 goto add_one_ulp; 189 } 190 else /* round bit is zero */ 191 goto truncate; /* with the default inexact=-1 */ 192 } 193 } 194 else /* rnd_mode=GMP_RDNU, necessarily sticky <> 0, thus add 1 ulp */ 195 goto add_one_ulp; 196 197 even_rule: /* has to set inexact */ 198 if (sh < GMP_NUMB_BITS) 199 inexact = (rp[0] & (MPFR_LIMB_ONE << sh)) ? 1 : -1; 200 else 201 inexact = (rp[1] & MPFR_LIMB_ONE) ? 1 : -1; 202 if (inexact == -1) 203 goto truncate; 204 /* else go through add_one_ulp */ 205 206 add_one_ulp: 207 inexact = 1; /* always here */ 208 if (sh == GMP_NUMB_BITS) 209 { 210 rp ++; 211 rsize --; 212 sh = 0; 213 } 214 if (mpn_add_1 (rp0, rp, rsize, MPFR_LIMB_ONE << sh)) 215 { 216 expr ++; 217 rp[rsize - 1] = MPFR_LIMB_HIGHBIT; 218 } 219 goto end; 220 221 truncate: /* inexact = 0 or -1 */ 222 if (sh == GMP_NUMB_BITS) 223 MPN_COPY (rp0, rp + 1, rsize - 1); 224 225 end: 226 MPFR_ASSERTN (expr >= MPFR_EMIN_MIN && expr <= MPFR_EMAX_MAX); 227 MPFR_EXP (r) = expr; 228 MPFR_TMP_FREE(marker); 229 230 return mpfr_check_range (r, inexact, rnd_mode); 231} 232