如何快速计算任意基数的整数对数？

Question

我如何快速计算任何基数的整数对数，而不仅仅是基数10？This question对基数10有一个非常有效的解决方案，但我想了解如何将它推广到其他基。

Answer 1

基础知识

任意数的对数基b ( n log_b(n) )可以使用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%正确的。

正如问题中所解释的，我们根据二进制对数进行猜测，这是非常有效的计算，如果必要的话，我们可以增加我们的猜测。

可以使用以下方法计算猜测表：

index -> log_10(exp(2, index)) = log_10(1 << index)

您可以看到，该表首先在索引4处有一个4条目，因为exp(2, 4) = 16有一个泛泛的log_10 of 1。

示例

说我们想知道log_10(15)

我们计算log_2(15) = 3

• We查找log_10(exp(2, 3)) = log_10(8) = 0。这是我们最初的猜测。exp(10, guess + 1) = exp(10, 1) = 10.

• 15 >= 10，，

，

• ，查找，所以我们的猜测太低，我们返回guess + 1 = 0 + 1 = 1。

任意基的泛化

要将这种方法推广到任何基础，我们必须在constexpr上下文中计算查找表。要计算猜测表，我们首先需要对任何基本值进行简单的对数实现：

template <typename Uint>
constexpr Uint logFloor_naive(Uint val, unsigned base)  {
    Uint result = 0;
    while (val /= base) {
        ++result;
    }
    return result;
}

现在，我们可以计算查找表：

#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模板常量来确定第二个查找表的大小。最后，我们可以使用查找表来获得最后的函数：

// 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查找表的注记

我们总是将uint64_t用于powers表的原因是，我们访问guess + 1和exp(10, guess + 1)并不总是可表示的。例如，如果我们使用8位整数并猜测2，那么exp(10, guess + 1)将是1000，它不能使用8位整数表示。

通常，这会导致64位整数的问题，因为没有更大的整数类型可用.但也有例外。例如，最大的2的幂是可表示的，exp(2, 63)比exp(10, 19)低，后者是最大的可表示的10，这意味着最高的猜测是18，exp(10, guess + 1) = exp(10, 19)是可表示的。因此，我们始终可以安全地访问powers[guess + 1]。

这些异常非常有用，因为在这种情况下我们可以避免整数除法。如上文所示，这样的异常可以在以下情况下检测到：

guesses.back() + 2 < powers.size()