flint_mpn_brsqrt, flint_mpn_bsqrt
#include <flint/mpn_extras.h>int flint_mpn_brsqrt(mp_ptr res, mp_srcptr x, mp_size_t xn, mp_size_t n)sourceint flint_mpn_bsqrt(mp_ptr res, mp_srcptr x, mp_size_t xn, mp_size_t n)sourceIf x \equiv 1 \pmod 8, set (\mathit{res}, n) to the 2-adic reciprocal square root y (with x y^2 \equiv 1 \pmod{B^n}), respectively the square root s (with s^2 \equiv x \pmod{B^n}), that is congruent to 1 modulo 4, and return 1. Otherwise return 0 without writing anything (an odd x is a square modulo B^n if and only if x \equiv 1 \pmod 8).
The reciprocal square root is computed by a Newton iteration in bit precision (each step maps c correct bits to 2c - 2), using high products with known low part above the basecase range and full low products below FLINT_MPN_BRSQRT_MULLOW_CUTOFF limbs. The square root adds one Karp–Markstein refinement to a reciprocal square root of \lceil n/2 \rceil + 1 limbs.
The FLINT team, “flint_mpn_brsqrt, flint_mpn_bsqrt (mpn_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/mpn_extras/flint_mpn_brsqrt.html (generated 2026-10-20).
@misc{flint-doc-mpn-extras-flint-mpn-brsqrt,
author = {{The FLINT team}},
title = {{flint\_mpn\_brsqrt, flint\_mpn\_bsqrt (mpn\_extras.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/mpn_extras/flint_mpn_brsqrt.html},
note = {Generated 2026-10-20}
}