如何快速计算任意底数的整数对数？
How can you quickly compute the integer logarithm for any base?
如何快速计算任何底数的整数对数，而不仅仅是以 10 为底数？ This question 有一个以 10 为基数的非常有效的解决方案，但我想了解如何将其推广到其他基数。
基础知识
任何数 n log_b(n) 的对数底数 b 可以使用 log(n) / log(b) 计算，其中 log 是任何底数的对数（通常是自然对数）。 log(b) 是一个常数，所以如果我们可以有效地计算某些底数的对数，我们就可以有效地计算 任何 底数的对数。
不幸的是，这种转换只有在我们不丢弃数字的情况下才有可能。对于整数，我们只能快速计算底对数。例如，log_2(10) = 3。这将是 8 到 15 之间任何数字的结果，尽管它们的小数位数不同。所以这个二进制对数可以帮助我们做出一个很好的猜测，但我们需要改进这个猜测。
基数 10
上述问题的解决方法如下：
constexpr unsigned log2floor(uint64_t x) {
// implementation for C++17 using clang or gcc
return x ? 63 - __builtin_clzll(x) : 0;
// implementation using the new C++20 <bit> header
return x ? 63 - std::countl_zero(x) : 0;
}
constexpr unsigned log10floor(unsigned x) {
constexpr unsigned char guesses[32] = {
0, 0, 0, 0, 1, 1, 1, 2, 2, 2,
3, 3, 3, 3, 4, 4, 4, 5, 5, 5,
6, 6, 6, 6, 7, 7, 7, 8, 8, 8,
9, 9
};
constexpr uint64_t powers[11] = {
1, 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000, 1000000000, 10000000000
};
unsigned guess = guesses[log2floor(x)];
return guess + (x >= powers[guess + 1]);
}
请注意，我必须进行一些修改，因为该解决方案实际上并非 100% 正确。
如问题中所述，我们根据可以非常有效地计算的二进制对数进行猜测，然后在必要时增加我们的猜测。
猜测 table 可以使用以下方法计算：
index -> log_10(exp(2, index)) = log_10(1 << index)
您可以看到 table 首先在索引 4 处有一个 1 条目，因为 exp(2, 4) = 16 有一个 floored log_10 of 1.
例子
假设我们想知道 log_10(15):
- 我们计算
log_2(15) = 3
- 我们查找
log_10(exp(2, 3)) = log_10(8) = 0。这是我们的初步猜测。
- 我们查找
exp(10, guess + 1) = exp(10, 1) = 10.
15 >= 10，所以我们的猜测太低了，我们 return guess + 1 = 0 + 1 = 1 相反。
任何基础的泛化
要将此方法推广到任何基础，我们必须在 constexpr 上下文中计算查找 tables。要计算猜测值 table，我们首先需要对任何基数进行简单的对数实现：
template <typename Uint>
constexpr Uint logFloor_naive(Uint val, unsigned base) {
Uint result = 0;
while (val /= base) {
++result;
}
return result;
}
现在，我们可以计算查找 tables:
#include <limits>
#include <array>
template <typename Uint, size_t BASE>
constexpr std::array<uint8_t, std::numeric_limits<Uint>::digits> makeGuessTable()
{
decltype(makeGuessTable<Uint, BASE>()) result{};
for (size_t i = 0; i < result.size(); ++i) {
Uint pow2 = static_cast<Uint>(Uint{1} << i);
result.data[i] = logFloor_naive(pow2, BASE);
}
return result;
}
// The maximum possible exponent for a given base that can still be represented
// by a given integer type.
// Example: maxExp<uint8_t, 10> = 2, because 10^2 is representable by an 8-bit unsigned
// integer but 10^3 isn't.
template <typename Uint, unsigned BASE>
constexpr Uint maxExp = logFloor_naive<Uint>(static_cast<Uint>(~Uint{0u}), BASE);
// the size of the table is maxPow<Uint, BASE> + 2 because we need to store the maximum power
// +1 because we need to contain it, we are dealing with a size, not an index
// +1 again because for narrow integers, we access guess+1
template <typename Uint, size_t BASE>
constexpr std::array<uint64_t, maxExp<Uint, BASE> + 2> makePowerTable()
{
decltype(makePowerTable<Uint, BASE>()) result{};
uint64_t x = 1;
for (size_t i = 0; i < result.size(); ++i, x *= BASE) {
result.data[i] = x;
}
return result;
}
请注意，我们需要 maxExp 模板常量来确定第二次查找的大小 table。最后，我们可以使用查找 tables 得出最终函数：
// If our base is a power of 2, we can convert between the
// logarithms of different bases without losing any precision.
constexpr bool isPow2or0(uint64_t val) {
return (val & (val - 1)) == 0;
}
template <size_t BASE = 10, typename Uint>
constexpr Uint logFloor(Uint val) {
if constexpr (isPow2or0(BASE)) {
return log2floor(val) / log2floor(BASE);
}
else {
constexpr auto guesses = makeGuessTable<Uint, BASE>();
constexpr auto powers = makePowerTable<Uint, BASE>();
uint8_t guess = guesses[log2floor(val)];
// Accessing guess + 1 isn't always safe for 64-bit integers.
// This is why we need this condition. See below for more details.
if constexpr (sizeof(Uint) < sizeof(uint64_t)
|| guesses.back() + 2 < powers.size()) {
return guess + (val >= powers[guess + 1]);
}
else {
return guess + (val / BASE >= powers[guess]);
}
}
}
关于 powers 查找的注释 Table
我们总是使用 uint64_t 作为 powers table 的原因是我们访问 guess + 1 而 exp(10, guess + 1) 并不总是代表 table。例如，如果我们使用 8 位整数并猜测 2，那么 exp(10, guess + 1) 将是 1000，这不代表 table 使用 8 位整数.
通常，这会导致 64 位整数出现问题，因为没有更大的整数类型可用。但也有例外。比如2的最大representable次方exp(2, 63)低于10的最大representable次方exp(10, 19)。 guess 将是 18 并且 exp(10, guess + 1) = exp(10, 19) 是 representable。因此，我们始终可以安全地访问 powers[guess + 1].
这些异常非常有用，因为在这种情况下我们可以避免整数除法。如上所示，可以通过以下方式检测到这样的异常：
guesses.back() + 2 < powers.size()
如何快速计算任何底数的整数对数，而不仅仅是以 10 为底数？ This question 有一个以 10 为基数的非常有效的解决方案，但我想了解如何将其推广到其他基数。
基础知识
任何数 n log_b(n) 的对数底数 b 可以使用 log(n) / log(b) 计算，其中 log 是任何底数的对数（通常是自然对数）。 log(b) 是一个常数，所以如果我们可以有效地计算某些底数的对数，我们就可以有效地计算 任何 底数的对数。
不幸的是，这种转换只有在我们不丢弃数字的情况下才有可能。对于整数，我们只能快速计算底对数。例如，log_2(10) = 3。这将是 8 到 15 之间任何数字的结果，尽管它们的小数位数不同。所以这个二进制对数可以帮助我们做出一个很好的猜测，但我们需要改进这个猜测。
基数 10
上述问题的解决方法如下：
constexpr unsigned log2floor(uint64_t x) {
// implementation for C++17 using clang or gcc
return x ? 63 - __builtin_clzll(x) : 0;
// implementation using the new C++20 <bit> header
return x ? 63 - std::countl_zero(x) : 0;
}
constexpr unsigned log10floor(unsigned x) {
constexpr unsigned char guesses[32] = {
0, 0, 0, 0, 1, 1, 1, 2, 2, 2,
3, 3, 3, 3, 4, 4, 4, 5, 5, 5,
6, 6, 6, 6, 7, 7, 7, 8, 8, 8,
9, 9
};
constexpr uint64_t powers[11] = {
1, 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000, 1000000000, 10000000000
};
unsigned guess = guesses[log2floor(x)];
return guess + (x >= powers[guess + 1]);
}
请注意，我必须进行一些修改，因为该解决方案实际上并非 100% 正确。
如问题中所述，我们根据可以非常有效地计算的二进制对数进行猜测，然后在必要时增加我们的猜测。
猜测 table 可以使用以下方法计算：
index -> log_10(exp(2, index)) = log_10(1 << index)
您可以看到 table 首先在索引 4 处有一个 1 条目，因为 exp(2, 4) = 16 有一个 floored log_10 of 1.
例子
假设我们想知道 log_10(15):
- 我们计算
log_2(15) = 3 - 我们查找
log_10(exp(2, 3)) = log_10(8) = 0。这是我们的初步猜测。 - 我们查找
exp(10, guess + 1) = exp(10, 1) = 10. 15 >= 10，所以我们的猜测太低了，我们 returnguess + 1 = 0 + 1 = 1相反。
任何基础的泛化
要将此方法推广到任何基础，我们必须在 constexpr 上下文中计算查找 tables。要计算猜测值 table，我们首先需要对任何基数进行简单的对数实现：
template <typename Uint>
constexpr Uint logFloor_naive(Uint val, unsigned base) {
Uint result = 0;
while (val /= base) {
++result;
}
return result;
}
现在，我们可以计算查找 tables:
#include <limits>
#include <array>
template <typename Uint, size_t BASE>
constexpr std::array<uint8_t, std::numeric_limits<Uint>::digits> makeGuessTable()
{
decltype(makeGuessTable<Uint, BASE>()) result{};
for (size_t i = 0; i < result.size(); ++i) {
Uint pow2 = static_cast<Uint>(Uint{1} << i);
result.data[i] = logFloor_naive(pow2, BASE);
}
return result;
}
// The maximum possible exponent for a given base that can still be represented
// by a given integer type.
// Example: maxExp<uint8_t, 10> = 2, because 10^2 is representable by an 8-bit unsigned
// integer but 10^3 isn't.
template <typename Uint, unsigned BASE>
constexpr Uint maxExp = logFloor_naive<Uint>(static_cast<Uint>(~Uint{0u}), BASE);
// the size of the table is maxPow<Uint, BASE> + 2 because we need to store the maximum power
// +1 because we need to contain it, we are dealing with a size, not an index
// +1 again because for narrow integers, we access guess+1
template <typename Uint, size_t BASE>
constexpr std::array<uint64_t, maxExp<Uint, BASE> + 2> makePowerTable()
{
decltype(makePowerTable<Uint, BASE>()) result{};
uint64_t x = 1;
for (size_t i = 0; i < result.size(); ++i, x *= BASE) {
result.data[i] = x;
}
return result;
}
请注意，我们需要 maxExp 模板常量来确定第二次查找的大小 table。最后，我们可以使用查找 tables 得出最终函数：
// If our base is a power of 2, we can convert between the
// logarithms of different bases without losing any precision.
constexpr bool isPow2or0(uint64_t val) {
return (val & (val - 1)) == 0;
}
template <size_t BASE = 10, typename Uint>
constexpr Uint logFloor(Uint val) {
if constexpr (isPow2or0(BASE)) {
return log2floor(val) / log2floor(BASE);
}
else {
constexpr auto guesses = makeGuessTable<Uint, BASE>();
constexpr auto powers = makePowerTable<Uint, BASE>();
uint8_t guess = guesses[log2floor(val)];
// Accessing guess + 1 isn't always safe for 64-bit integers.
// This is why we need this condition. See below for more details.
if constexpr (sizeof(Uint) < sizeof(uint64_t)
|| guesses.back() + 2 < powers.size()) {
return guess + (val >= powers[guess + 1]);
}
else {
return guess + (val / BASE >= powers[guess]);
}
}
}
关于 powers 查找的注释 Table
我们总是使用 uint64_t 作为 powers table 的原因是我们访问 guess + 1 而 exp(10, guess + 1) 并不总是代表 table。例如，如果我们使用 8 位整数并猜测 2，那么 exp(10, guess + 1) 将是 1000，这不代表 table 使用 8 位整数.
通常，这会导致 64 位整数出现问题，因为没有更大的整数类型可用。但也有例外。比如2的最大representable次方exp(2, 63)低于10的最大representable次方exp(10, 19)。 guess 将是 18 并且 exp(10, guess + 1) = exp(10, 19) 是 representable。因此，我们始终可以安全地访问 powers[guess + 1].
这些异常非常有用，因为在这种情况下我们可以避免整数除法。如上所示，可以通过以下方式检测到这样的异常：
guesses.back() + 2 < powers.size()