/* mpfr_sqrt -- square root of a floating-point number Copyright 1999-2016 Free Software Foundation, Inc. Contributed by the AriC and Caramba projects, INRIA. This file is part of the GNU MPFR Library. The GNU MPFR Library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version. The GNU MPFR Library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with the GNU MPFR Library; see the file COPYING.LESSER. If not, see http://www.gnu.org/licenses/ or write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. */ #include "mpfr-impl.h" int mpfr_sqrt (mpfr_ptr r, mpfr_srcptr u, mpfr_rnd_t rnd_mode) { mp_size_t rsize; /* number of limbs of r (plus 1 if exact limb multiple) */ mp_size_t rrsize; mp_size_t usize; /* number of limbs of u */ mp_size_t tsize; /* number of limbs of the sqrtrem remainder */ mp_size_t k; mp_size_t l; mpfr_limb_ptr rp, rp0; mpfr_limb_ptr up; mpfr_limb_ptr sp; mp_limb_t sticky0; /* truncated part of input */ mp_limb_t sticky1; /* truncated part of rp[0] */ mp_limb_t sticky; int odd_exp; int sh; /* number of extra bits in rp[0] */ int inexact; /* return ternary flag */ mpfr_exp_t expr; MPFR_TMP_DECL(marker); MPFR_LOG_FUNC (("x[%Pu]=%.*Rg rnd=%d", mpfr_get_prec (u), mpfr_log_prec, u, rnd_mode), ("y[%Pu]=%.*Rg inexact=%d", mpfr_get_prec (r), mpfr_log_prec, r, inexact)); if (MPFR_UNLIKELY(MPFR_IS_SINGULAR(u))) { if (MPFR_IS_NAN(u)) { MPFR_SET_NAN(r); MPFR_RET_NAN; } else if (MPFR_IS_ZERO(u)) { /* 0+ or 0- */ MPFR_SET_SAME_SIGN(r, u); MPFR_SET_ZERO(r); MPFR_RET(0); /* zero is exact */ } else { MPFR_ASSERTD(MPFR_IS_INF(u)); /* sqrt(-Inf) = NAN */ if (MPFR_IS_NEG(u)) { MPFR_SET_NAN(r); MPFR_RET_NAN; } MPFR_SET_POS(r); MPFR_SET_INF(r); MPFR_RET(0); } } if (MPFR_UNLIKELY(MPFR_IS_NEG(u))) { MPFR_SET_NAN(r); MPFR_RET_NAN; } MPFR_SET_POS(r); MPFR_TMP_MARK (marker); MPFR_UNSIGNED_MINUS_MODULO (sh, MPFR_GET_PREC (r)); if (sh == 0 && rnd_mode == MPFR_RNDN) sh = GMP_NUMB_BITS; /* ugly case */ rsize = MPFR_LIMB_SIZE(r) + (sh == GMP_NUMB_BITS); /* rsize is the number of limbs of r + 1 if exact limb multiple and rounding to nearest, this is the number of wanted limbs for the square root */ rrsize = rsize + rsize; usize = MPFR_LIMB_SIZE(u); /* number of limbs of u */ rp0 = MPFR_MANT(r); rp = (sh < GMP_NUMB_BITS) ? rp0 : MPFR_TMP_LIMBS_ALLOC (rsize); up = MPFR_MANT(u); sticky0 = MPFR_LIMB_ZERO; /* truncated part of input */ sticky1 = MPFR_LIMB_ZERO; /* truncated part of rp[0] */ odd_exp = (unsigned int) MPFR_GET_EXP (u) & 1; inexact = -1; /* return ternary flag */ sp = MPFR_TMP_LIMBS_ALLOC (rrsize); /* copy the most significant limbs of u to {sp, rrsize} */ if (MPFR_LIKELY(usize <= rrsize)) /* in case r and u have the same precision, we have indeed rrsize = 2 * usize */ { k = rrsize - usize; if (MPFR_LIKELY(k)) MPN_ZERO (sp, k); if (odd_exp) { if (MPFR_LIKELY(k)) sp[k - 1] = mpn_rshift (sp + k, up, usize, 1); else sticky0 = mpn_rshift (sp, up, usize, 1); } else MPN_COPY (sp + rrsize - usize, up, usize); } else /* usize > rrsize: truncate the input */ { k = usize - rrsize; if (odd_exp) sticky0 = mpn_rshift (sp, up + k, rrsize, 1); else MPN_COPY (sp, up + k, rrsize); l = k; while (sticky0 == MPFR_LIMB_ZERO && l != 0) sticky0 = up[--l]; } /* sticky0 is non-zero iff the truncated part of the input is non-zero */ tsize = mpn_sqrtrem (rp, NULL, sp, rrsize); /* a return value of zero in mpn_sqrtrem indicates a perfect square */ sticky = sticky0 || tsize != 0; /* truncate low bits of rp[0] */ sticky1 = rp[0] & ((sh < GMP_NUMB_BITS) ? MPFR_LIMB_MASK(sh) : ~MPFR_LIMB_ZERO); rp[0] -= sticky1; sticky = sticky || sticky1; expr = (MPFR_GET_EXP(u) + odd_exp) / 2; /* exact */ if (rnd_mode == MPFR_RNDZ || rnd_mode == MPFR_RNDD || sticky == MPFR_LIMB_ZERO) { inexact = (sticky == MPFR_LIMB_ZERO) ? 0 : -1; goto truncate; } else if (rnd_mode == MPFR_RNDN) { /* if sh < GMP_NUMB_BITS, the round bit is bit (sh-1) of sticky1 and the sticky bit is formed by the low sh-1 bits from sticky1, together with the sqrtrem remainder and sticky0. */ if (sh < GMP_NUMB_BITS) { if (sticky1 & (MPFR_LIMB_ONE << (sh - 1))) { /* round bit is set */ if (sticky1 == (MPFR_LIMB_ONE << (sh - 1)) && tsize == 0 && sticky0 == 0) goto even_rule; else goto add_one_ulp; } else /* round bit is zero */ goto truncate; /* with the default inexact=-1 */ } else /* sh = GMP_NUMB_BITS: the round bit is the most significant bit of rp[0], and the remaining GMP_NUMB_BITS-1 bits contribute to the sticky bit */ { if (sticky1 & MPFR_LIMB_HIGHBIT) { /* round bit is set */ if (sticky1 == MPFR_LIMB_HIGHBIT && tsize == 0 && sticky0 == 0) goto even_rule; else goto add_one_ulp; } else /* round bit is zero */ goto truncate; /* with the default inexact=-1 */ } } else /* rnd_mode=GMP_RDNU, necessarily sticky <> 0, thus add 1 ulp */ goto add_one_ulp; even_rule: /* has to set inexact */ if (sh < GMP_NUMB_BITS) inexact = (rp[0] & (MPFR_LIMB_ONE << sh)) ? 1 : -1; else inexact = (rp[1] & MPFR_LIMB_ONE) ? 1 : -1; if (inexact == -1) goto truncate; /* else go through add_one_ulp */ add_one_ulp: inexact = 1; /* always here */ if (sh == GMP_NUMB_BITS) { rp ++; rsize --; sh = 0; } /* now rsize = MPFR_LIMB_SIZE(r) */ if (mpn_add_1 (rp0, rp, rsize, MPFR_LIMB_ONE << sh)) { expr ++; rp0[rsize - 1] = MPFR_LIMB_HIGHBIT; } goto end; truncate: /* inexact = 0 or -1 */ if (sh == GMP_NUMB_BITS) MPN_COPY (rp0, rp + 1, rsize - 1); end: /* Do not use MPFR_SET_EXP because the range has not been checked yet. */ MPFR_ASSERTN (expr >= MPFR_EMIN_MIN && expr <= MPFR_EMAX_MAX); MPFR_EXP (r) = expr; MPFR_TMP_FREE(marker); return mpfr_check_range (r, inexact, rnd_mode); }