累乗根（ニュートン法）
(algorithm/Math/Algebra/nth_root.hpp)

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/Math/Algebra/nth_root.hpp"

概要

非負の実数 $x$ に対する $n$ 乗根 $\sqrt[n]{x}$ を求める（ただし，$n$ は自然数）．

本実装では「ニュートン法」を用いており，近似解を計算する．

参考文献

1. 吉田 俊之ほか. “4.3 ニュートン法”. 工学のための数値計算. 数理工学社, 2008, p.62-64.
2. “冪根”. Wikipedia. https://ja.wikipedia.org/wiki/冪根.
3. “ニュートン法”. Wikipedia. https://ja.wikipedia.org/wiki/ニュートン法.

Depends on

• 繰り返し二乗法 (algorithm/Math/Algebra/power.hpp)

Verified with

• verify/aoj-ITP1_10_D-nth_root.test.cpp

Code

#ifndef ALGORITHM_NTH_ROOT_HPP
#define ALGORITHM_NTH_ROOT_HPP 1

#include <cassert>
#include <cmath>

#include "power.hpp"

namespace algorithm {

// 累乗根（ニュートン法）．xのn乗根を求める．
constexpr double nth_root(double x, long long n, double eps = 1e-10) {
    assert(x >= 0.0);
    assert(n >= 1);
    double res = 1.0;
    while(true) {
        double tmp = (x / pow(res, n - 1) + (n - 1) * res) / n;
        if(std::abs(tmp - res) < eps) break;
        res = tmp;
    }
    return res;
}

}  // namespace algorithm

#endif

#line 1 "algorithm/Math/Algebra/nth_root.hpp"



#include <cassert>
#include <cmath>

#line 1 "algorithm/Math/Algebra/power.hpp"



#line 5 "algorithm/Math/Algebra/power.hpp"

namespace algorithm {

// 繰り返し二乗法．O(logK).
template <typename Type>
constexpr Type pow(Type n, long long k) {
    assert(k >= 0);
    Type res = 1;
    while(k > 0) {
        if(k & 1LL) res *= n;
        n *= n;
        k >>= 1;
    }
    return res;
}

}  // namespace algorithm


#line 8 "algorithm/Math/Algebra/nth_root.hpp"

namespace algorithm {

// 累乗根（ニュートン法）．xのn乗根を求める．
constexpr double nth_root(double x, long long n, double eps = 1e-10) {
    assert(x >= 0.0);
    assert(n >= 1);
    double res = 1.0;
    while(true) {
        double tmp = (x / pow(res, n - 1) + (n - 1) * res) / n;
        if(std::abs(tmp - res) < eps) break;
        res = tmp;
    }
    return res;
}

}  // namespace algorithm

Back to top page