sqrt_int.hpp

View this file on GitHub
Last update: 2025-01-19 15:28:01+08:00
Include: #include "sqrt_int.hpp"

Verified with

test/enumerative_combinatorics/factorial.0.test.cpp

Code

#pragma once

#include <cassert>
#include <type_traits>

// see:
// [1]: Richard P. Brent and Paul Zimmermann. Modern Computer Arithmetic.

// returns floor(m^(1/2))
template<typename Int> inline std::enable_if_t<std::is_integral_v<Int>, Int> sqrt_int(Int m) {
    assert(m >= 0);
    if (m == 0) return 0;
    for (Int u = m;;) {
        std::add_const_t<Int> s = u;
        u                       = (s + m / s) / 2;
        if (u >= s) return s;
    }
}

#line 2 "sqrt_int.hpp"

#include <cassert>
#include <type_traits>

// see:
// [1]: Richard P. Brent and Paul Zimmermann. Modern Computer Arithmetic.

// returns floor(m^(1/2))
template<typename Int> inline std::enable_if_t<std::is_integral_v<Int>, Int> sqrt_int(Int m) {
    assert(m >= 0);
    if (m == 0) return 0;
    for (Int u = m;;) {
        std::add_const_t<Int> s = u;
        u                       = (s + m / s) / 2;
        if (u >= s) return s;
    }
}