Integer Square Root
(math/number-theory/isqrt.hpp)

• View this file on GitHub
• Last update: 2024-01-08 17:31:43+09:00
• Include: #include "math/number-theory/isqrt.hpp"

Code

#pragma once

/**
 * @brief Integer Square Root
 */
unsigned long long isqrt(unsigned long long n) {
    unsigned long long x0 = n / 2;
    if (x0 == 0) return n;
    unsigned long long x1 = (x0 + n / x0) / 2;
    while (x1 < x0) {
        x0 = x1;
        x1 = (x0 + n / x0) / 2;
    }
    return x0;
}

#line 2 "math/number-theory/isqrt.hpp"

/**
 * @brief Integer Square Root
 */
unsigned long long isqrt(unsigned long long n) {
    unsigned long long x0 = n / 2;
    if (x0 == 0) return n;
    unsigned long long x1 = (x0 + n / x0) / 2;
    while (x1 < x0) {
        x0 = x1;
        x1 = (x0 + n / x0) / 2;
    }
    return x0;
}

Back to top page