$\left\lfloor \log_b(x) \right\rfloor$ (tools/floor_log.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2025-02-10 01:30:13+09:00
Include: #include "tools/floor_log.hpp"

template <typename M, typename N>
std::common_type_t<M, N> floor_log(M b, N x);

It returns $\left\lfloor \log_b(x) \right\rfloor$.

Constraints

$2 \leq b \leq 10^{18}$
$1 \leq x \leq 10^{18}$

Time Complexity

$O(\log x)$

License

Author

anqooqie

Depends on

Verified with

tests/floor_log.test.cpp

Code

#ifndef TOOLS_FLOOR_LOG_HPP
#define TOOLS_FLOOR_LOG_HPP

#include <type_traits>
#include <cassert>
#include "tools/floor.hpp"

namespace tools {

  template <typename M, typename N>
  ::std::common_type_t<M, N> floor_log(const M& base, const N& antilogarithm) {
    assert(2 <= base && base <= 1000000000000000000);
    assert(1 <= antilogarithm && antilogarithm <= 1000000000000000000);

    const ::std::common_type_t<M, N> threshold = ::tools::floor(antilogarithm, base);
    ::std::common_type_t<M, N> logarithm = 0;
    for (::std::common_type_t<M, N> pow = 1; pow <= antilogarithm; pow = (pow <= threshold ? pow * base : antilogarithm + 1)) {
      ++logarithm;
    }

    return logarithm - 1;
  }
}

#endif

#line 1 "tools/floor_log.hpp"



#include <type_traits>
#include <cassert>
#line 1 "tools/floor.hpp"



#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 7 "tools/floor.hpp"

namespace tools {

  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> floor(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x >= 0) {
        return x / y;
      } else {
        return (x + 1) / y - 1;
      }
    } else {
      if (x > 0) {
        return (x - 1) / y - 1;
      } else {
        return x / y;
      }
    }
  }
}


#line 7 "tools/floor_log.hpp"

namespace tools {

  template <typename M, typename N>
  ::std::common_type_t<M, N> floor_log(const M& base, const N& antilogarithm) {
    assert(2 <= base && base <= 1000000000000000000);
    assert(1 <= antilogarithm && antilogarithm <= 1000000000000000000);

    const ::std::common_type_t<M, N> threshold = ::tools::floor(antilogarithm, base);
    ::std::common_type_t<M, N> logarithm = 0;
    for (::std::common_type_t<M, N> pow = 1; pow <= antilogarithm; pow = (pow <= threshold ? pow * base : antilogarithm + 1)) {
      ++logarithm;
    }

    return logarithm - 1;
  }
}