integer_kth_root.hpp

SECTIONMath INCLUDEnoya/integer_kth_root.hpp

精确计算 64 位无符号整数的 \(k\) 次方根下取整，不受浮点误差和乘法溢出影响。

\[ \displaystyle r=\lfloor x^{1/k}\rfloor \]

Complexity: Time: O(k ceil(64/k)) = O(64) bounded multiplications for a 64-bit input. Space: O(1).

AC 记录：kth_root_integer。

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(k ceil(64/k)) = O(64) bounded multiplications for a
/// 64-bit input.  Space: O(1).

#include <cassert>
#include <cstdint>

namespace noya {

/// @brief Return floor(val^(1/exp)) for an unsigned 64-bit integer.
/// Binary search uses an exponent-dependent upper bound.  The comparison
/// checks prd <= val / bas before multiplying by bas, so it is
/// exact and never relies on floating-point rounding or overflowing products.
inline std::uint64_t integer_kth_root(std::uint64_t val, int exp) {
  assert(1 <= exp && exp <= 64);
  if (exp == 1 || val <= 1) {
    return val;
  }
  auto chk = [&](std::uint64_t bas) {
    std::uint64_t prd = 1;
    for (int cnt = 0; cnt < exp; cnt++) {
      if (bas != 0 && prd > val / bas) {
        return false;
      }
      prd *= bas;
    }
    return true;
  };
  int ub = (64 + exp - 1) / exp;
  std::uint64_t low = 0;
  std::uint64_t hig = std::uint64_t(1) << ub;
  while (hig - low > 1) {
    std::uint64_t mid = low + (hig - low) / 2;
    (chk(mid) ? low : hig) = mid;
  }
  return low;
}

} // namespace noya

#ifndef NOYA_INTEGER_KTH_ROOT_HPP
#define NOYA_INTEGER_KTH_ROOT_HPP 1

/// @complexity Time: O(k ceil(64/k)) = O(64) bounded multiplications for a
/// 64-bit input.  Space: O(1).

#include <cassert>
#include <cstdint>

namespace noya {

/// @brief Return floor(val^(1/exp)) for an unsigned 64-bit integer.
/// Binary search uses an exponent-dependent upper bound.  The comparison
/// checks prd <= val / bas before multiplying by bas, so it is
/// exact and never relies on floating-point rounding or overflowing products.
inline std::uint64_t integer_kth_root(std::uint64_t val, int exp) {
  assert(1 <= exp && exp <= 64);
  if (exp == 1 || val <= 1) {
    return val;
  }
  auto chk = [&](std::uint64_t bas) {
    std::uint64_t prd = 1;
    for (int cnt = 0; cnt < exp; cnt++) {
      if (bas != 0 && prd > val / bas) {
        return false;
      }
      prd *= bas;
    }
    return true;
  };
  int ub = (64 + exp - 1) / exp;
  std::uint64_t low = 0;
  std::uint64_t hig = std::uint64_t(1) << ub;
  while (hig - low > 1) {
    std::uint64_t mid = low + (hig - low) / 2;
    (chk(mid) ? low : hig) = mid;
  }
  return low;
}

} // namespace noya

#endif // NOYA_INTEGER_KTH_ROOT_HPP

#include <cassert>
#include <cstdint>

/// @complexity Time: O(k ceil(64/k)) = O(64) bounded multiplications for a
/// 64-bit input.  Space: O(1).

namespace noya {

/// @brief Return floor(val^(1/exp)) for an unsigned 64-bit integer.
/// Binary search uses an exponent-dependent upper bound.  The comparison
/// checks prd <= val / bas before multiplying by bas, so it is
/// exact and never relies on floating-point rounding or overflowing products.
inline std::uint64_t integer_kth_root(std::uint64_t val, int exp) {
  assert(1 <= exp && exp <= 64);
  if (exp == 1 || val <= 1) {
    return val;
  }
  auto chk = [&](std::uint64_t bas) {
    std::uint64_t prd = 1;
    for (int cnt = 0; cnt < exp; cnt++) {
      if (bas != 0 && prd > val / bas) {
        return false;
      }
      prd *= bas;
    }
    return true;
  };
  int ub = (64 + exp - 1) / exp;
  std::uint64_t low = 0;
  std::uint64_t hig = std::uint64_t(1) << ub;
  while (hig - low > 1) {
    std::uint64_t mid = low + (hig - low) / 2;
    (chk(mid) ? low : hig) = mid;
  }
  return low;
}

} // namespace noya