如何快速计算任何底数的整数对数? [英] How can you quickly compute the integer logarithm for any base?

问题描述

如何快速计算任意底数而不是仅底数10的整数对数? 这个问题有一个针对10级基础的非常有效的解决方案，但我想了解如何将其推广到其他基础.

How can I quickly compute the integer logarithm for any base, not just base 10? This question has a really efficient solution for base 10 but I would like to understand how I can generalize that to other bases.

推荐答案

基础知识

任何数字n log_b(n)的对数底数b可以使用log(n) / log(b)计算，其中log是任何底数的对数(通常是自然对数). log(b)是常数，因此，如果我们可以有效地计算某个底数的对数，那么我们可以有效地计算任何底数的对数.

Fundamentals

The logarithm base b of any number n log_b(n) can be computed using log(n) / log(b) where log is the logarithm with any base (usually the natural logarithm). log(b) is a constant, so if we can compute the logarithm for some base efficiently, we can compute the logarithm for any base efficiently.

不幸的是，只有当我们不输入数字时，这种转换才可能进行.对于整数，我们只能快速计算底数对数.例如，log_2(10) = 3.这是8到15之间的任何数字的结果，尽管这些数字具有不同的十进制数字.因此，此二进制对数可以帮助我们做出一个很好的猜测，但是我们需要完善这个猜测.

Unfortunately, this conversion is only possible if we don't drop digits. For integers, we can only quickly compute the floored logarithm. For example, log_2(10) = 3. This would be the result for any number between 8 and 15, despite those having different amounts of decimal digits. So this binary logarithm can help us make a good guess, but we need to refine that guess.

上述问题具有以下解决方案:

The aforementioned question has the following solution:

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％正确，因此我必须进行一些修改.

Note that I had to make some modifications because the solution isn't actually 100% correct.

正如问题中所解释的那样，我们根据可以非常有效地计算出的二进制对数进行猜测，然后在必要时增加我们的猜测.

As explained in the question, we make a guess based on the binary logarithm which can be computed very efficiently and then increment our guess if necessary.

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

The guess table can be computed using:

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

您可以看到该表首先在索引4上具有1条目，因为exp(2, 4) = 16的底下log_10为1.

You can see that the table first has a 1 entry at index 4, because exp(2, 4) = 16 which has a floored log_10 of 1.

说我们想知道log_10(15):

1. 我们计算log_2(15) = 3
2. 我们查找log_10(exp(2, 3)) = log_10(8) = 0.这是我们最初的猜测.
3. 我们查找exp(10, guess + 1) = exp(10, 1) = 10.
4. 15 >= 10，所以我们的猜测太低，因此我们返回guess + 1 = 0 + 1 = 1.

1. We compute log_2(15) = 3
2. We lookup log_10(exp(2, 3)) = log_10(8) = 0. This is our initial guess.
3. We lookup exp(10, guess + 1) = exp(10, 1) = 10.
4. 15 >= 10, so our guess was too low and we return guess + 1 = 0 + 1 = 1 instead.

任何基础的通用化

要在任何基础上推广这种方法，我们必须在constexpr上下文中计算查找表.要计算猜测表，我们需要对任何基础优先的幼稚对数实现:

Generalization for any Base

To generalize this approach for any base, we must compute the lookup tables in a constexpr context. To compute the guess table, we need a naive logarithm implementation for any base first:

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

现在，我们可以计算查询表了:

Now, we can compute the lookup 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模板化常量来确定第二个查询表的大小.最后，我们可以使用查找表来提供最终功能:

Note that we need the maxExp templated constant to determine the size of the second lookup table. Finally, we can use the lookup tables to come up with the final function:

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

为什么我们总是在powers表中使用uint64_t是因为我们访问guess + 1而exp(10, guess + 1)并不总是可表示的.例如，如果我们使用8位整数，并且猜测为2，则exp(10, guess + 1)将为1000，而使用8位整数无法表示.

Notes on the powers Lookup Table

The reason why we always use uint64_t for our powers table is that we access guess + 1 and exp(10, guess + 1) isn't always representable. For example, if we are using 8-bit integers and have a guess of 2, then exp(10, guess + 1) would be 1000 which is not representable using an 8-bit integer.

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

Usually, this causes a problem for 64-bit integers, because there is no larger integer type available. But there are exceptions. For example, the largest power of 2 which is representable, exp(2, 63) is lower than exp(10, 19), which is the largest representable power of 10. This means that the highest guess will be 18 and exp(10, guess + 1) = exp(10, 19) is representable. Therefore, we can always safely access powers[guess + 1].

这些异常非常有用，因为在这种情况下我们可以避免整数除法.如上所示，可以通过以下方式检测到此类异常:

These exceptions are very useful because we can avoid an integer division in such cases. As seen above, exceptions like this can be detected with:

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

这篇关于如何快速计算任何底数的整数对数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！