sqrt.h

 
//          Copyright John McFarlane 2021.
// Distributed under the Boost Software License, Version 1.0.
//    (See accompanying file ../LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt)
 
#if !defined(CNL_IMPL_CMATH_SQRT_H)
#define CNL_IMPL_CMATH_SQRT_H
 
#include "../../integer.h"
#include "../cnl_assert.h"
#include "../num_traits/digits.h"
 
namespace cnl {
 
    template<integer Integer>
    [[nodiscard]] constexpr auto sqrt(Integer const& x)
    {
        CNL_ASSERT(x >= Integer{0});
 
        auto root = +Integer{0};
        auto bit = Integer{1} << ((digits_v<Integer> - 1) & ~1);
        auto num = decltype(root + bit){x};
 
        while (bit > num) {
            bit >>= 2;
        }
 
        while (bit) {
            if (num >= root + bit) {
                num -= root + bit;
                root = (root >> 1) + bit;
            } else {
                root >>= 1;
            }
            bit >>= 2;
        }
        return root;
    }
}
 
#endif  // CNL_IMPL_CMATH_SQRT_H