tests/ceil_log.test.cpp

• View this file on GitHub
• Last update: 2025-02-10 01:30:13+09:00

Depends on

• Assertion macro (tools/assert_that.hpp)
• $\left\lceil \frac{x}{y} \right\rceil$ (tools/ceil.hpp)
• $\left\lceil \log_b(x) \right\rceil$ (tools/ceil_log.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• std::is_unsigned extended for tools::int128_t and tools::uint128_t (tools/is_unsigned.hpp)

Code

// competitive-verifier: STANDALONE

#include <cstdlib>
#include <iostream>
#include "tools/assert_that.hpp"
#include "tools/ceil_log.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  assert_that(tools::ceil_log(2, 1) == 0);
  assert_that(tools::ceil_log(2, 2) == 1);
  assert_that(tools::ceil_log(2, 3) == 2);
  assert_that(tools::ceil_log(2, 4) == 2);
  assert_that(tools::ceil_log(2, 5) == 3);
  assert_that(tools::ceil_log(2, 6) == 3);
  assert_that(tools::ceil_log(2, 7) == 3);
  assert_that(tools::ceil_log(2, 8) == 3);
  assert_that(tools::ceil_log(2, 9) == 4);
  assert_that(tools::ceil_log(3, 1) == 0);
  assert_that(tools::ceil_log(3, 2) == 1);
  assert_that(tools::ceil_log(3, 3) == 1);
  assert_that(tools::ceil_log(3, 4) == 2);
  assert_that(tools::ceil_log(3, 5) == 2);
  assert_that(tools::ceil_log(3, 6) == 2);
  assert_that(tools::ceil_log(3, 7) == 2);
  assert_that(tools::ceil_log(3, 8) == 2);
  assert_that(tools::ceil_log(3, 9) == 2);
  assert_that(tools::ceil_log(4, 1) == 0);
  assert_that(tools::ceil_log(4, 2) == 1);
  assert_that(tools::ceil_log(4, 3) == 1);
  assert_that(tools::ceil_log(4, 4) == 1);
  assert_that(tools::ceil_log(4, 5) == 2);
  assert_that(tools::ceil_log(4, 6) == 2);
  assert_that(tools::ceil_log(4, 7) == 2);
  assert_that(tools::ceil_log(4, 8) == 2);
  assert_that(tools::ceil_log(4, 9) == 2);
  assert_that(tools::ceil_log(2, 576460752303423487) == 59);
  assert_that(tools::ceil_log(2, 576460752303423488) == 59);
  assert_that(tools::ceil_log(2, 576460752303423489) == 60);
  assert_that(tools::ceil_log(2, 1000000000000000000) == 60);
  assert_that(tools::ceil_log(1000000000000000000, 1) == 0);
  assert_that(tools::ceil_log(1000000000000000000, 2) == 1);
  assert_that(tools::ceil_log(999999999999999999, 999999999999999998) == 1);
  assert_that(tools::ceil_log(999999999999999999, 999999999999999999) == 1);
  assert_that(tools::ceil_log(999999999999999999, 1000000000000000000) == 2);

  return 0;
}

#line 1 "tests/ceil_log.test.cpp"
// competitive-verifier: STANDALONE

#include <cstdlib>
#include <iostream>
#line 1 "tools/assert_that.hpp"



#line 6 "tools/assert_that.hpp"

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    ::std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    ::std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 1 "tools/ceil_log.hpp"



#include <type_traits>
#include <cassert>
#line 1 "tools/ceil.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 1 "tools/is_unsigned.hpp"



#line 5 "tools/is_unsigned.hpp"

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

  template <typename T>
  inline constexpr bool is_unsigned_v = ::tools::is_unsigned<T>::value;
}


#line 8 "tools/ceil.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> ceil(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x > 0) {
        return (x - 1) / y + 1;
      } else {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      }
    } else {
      if (x >= 0) {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      } else {
        return (x + 1) / y + 1;
      }
    }
  }
}


#line 7 "tools/ceil_log.hpp"

namespace tools {

  template <typename M, typename N>
  ::std::common_type_t<M, N> ceil_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::ceil(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)) {
      ++logarithm;
    }

    return logarithm;
  }
}


#line 7 "tests/ceil_log.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  assert_that(tools::ceil_log(2, 1) == 0);
  assert_that(tools::ceil_log(2, 2) == 1);
  assert_that(tools::ceil_log(2, 3) == 2);
  assert_that(tools::ceil_log(2, 4) == 2);
  assert_that(tools::ceil_log(2, 5) == 3);
  assert_that(tools::ceil_log(2, 6) == 3);
  assert_that(tools::ceil_log(2, 7) == 3);
  assert_that(tools::ceil_log(2, 8) == 3);
  assert_that(tools::ceil_log(2, 9) == 4);
  assert_that(tools::ceil_log(3, 1) == 0);
  assert_that(tools::ceil_log(3, 2) == 1);
  assert_that(tools::ceil_log(3, 3) == 1);
  assert_that(tools::ceil_log(3, 4) == 2);
  assert_that(tools::ceil_log(3, 5) == 2);
  assert_that(tools::ceil_log(3, 6) == 2);
  assert_that(tools::ceil_log(3, 7) == 2);
  assert_that(tools::ceil_log(3, 8) == 2);
  assert_that(tools::ceil_log(3, 9) == 2);
  assert_that(tools::ceil_log(4, 1) == 0);
  assert_that(tools::ceil_log(4, 2) == 1);
  assert_that(tools::ceil_log(4, 3) == 1);
  assert_that(tools::ceil_log(4, 4) == 1);
  assert_that(tools::ceil_log(4, 5) == 2);
  assert_that(tools::ceil_log(4, 6) == 2);
  assert_that(tools::ceil_log(4, 7) == 2);
  assert_that(tools::ceil_log(4, 8) == 2);
  assert_that(tools::ceil_log(4, 9) == 2);
  assert_that(tools::ceil_log(2, 576460752303423487) == 59);
  assert_that(tools::ceil_log(2, 576460752303423488) == 59);
  assert_that(tools::ceil_log(2, 576460752303423489) == 60);
  assert_that(tools::ceil_log(2, 1000000000000000000) == 60);
  assert_that(tools::ceil_log(1000000000000000000, 1) == 0);
  assert_that(tools::ceil_log(1000000000000000000, 2) == 1);
  assert_that(tools::ceil_log(999999999999999999, 999999999999999998) == 1);
  assert_that(tools::ceil_log(999999999999999999, 999999999999999999) == 1);
  assert_that(tools::ceil_log(999999999999999999, 1000000000000000000) == 2);

  return 0;
}

Back to top page