如何通过按位运算尽可能精确地计算C中整数的log2

Question

我需要计算熵，由于我的系统的限制，我需要使用受限的 C 功能（没有循环，没有浮点支持）并且我需要尽可能高的精度。从 here 我弄清楚了如何使用按位运算来估计整数的 floor log2。尽管如此，我需要提高结果的精度。由于不允许进行浮点运算，有没有办法用x < y计算log2(x/y)，使结果类似于log2(x/y)*10000，旨在通过算术整数获得我需要的精度？

Answer 1

您将根据公式

制定算法

log2(x/y) = K*(-log(x/y));

哪里

 K        = -1.0/log(2.0); // you can precompute this constant before run-time
 a        = (y-x)/y;
-log(x/y) = a + a^2/2 + a^3/3 + a^4/4 + a^5/5 + ...

如果您正确编写循环——或者，如果您愿意，展开循环以无环地编写相同的操作序列——那么您可以处理整数运算中的所有内容：

(y^N*(1*2*3*4*5*...*N)) * (-log(x/y))
  = y^(N-1)*(2*3*4*5*...*N)*(y-x) + y^(N-2)*(1*3*4*5*...*N)*(y-x)^2 + ...

当然，幂运算符 ^ 绑定比 * 更紧密，它不是 C 运算符，但您可以在（可能展开的）循环的上下文中有效地实现它运行个产品。

N 是一个足够大的整数，可以提供所需的精度，但又不会大到超过您可用的位数。如果不确定，则尝试 N = 6 例如。关于K，你可能会反对它是一个浮点数，但这对你来说不是问题，因为你要预先计算K，将它存储为整数的比率。

示例代码

这是一个玩具代码，但它适用于 x 和 y 的小值，例如 5 和 7，因此足以证明这个概念。在玩具代码中，较大的值会悄无声息地溢出默认的 64 位寄存器。需要做更多的工作才能使代码健壮。

#include <stddef.h>
#include <stdlib.h>
// Your program will not need the below headers, which are here
// included only for comparison and demonstration.
#include <math.h>
#include <stdio.h>

const size_t     N = 6;
const long long Ky = 1 << 10; // denominator of K
// Your code should define a precomputed value for Kx here.

int main(const int argc, const char *const *const argv)
{
    // Your program won't include the following library calls but this
    // does not matter.  You can instead precompute the value of Kx and
    // hard-code its value above with Ky.
    const long long Kx = lrintl((-1.0/log(2.0))*Ky); // numerator of K
    printf("K == %lld/%lld\n", Kx, Ky);

    if (argc != 3) exit(1);

    // Read x and y from the command line.
    const long long x0 = atoll(argv[1]);
    const long long y  = atoll(argv[2]);
    printf("x/y == %lld/%lld\n", x0, y);
    if (x0 <= 0 || y <= 0 || x0 > y) exit(1);

    // If 2*x <= y, then, to improve accuracy, double x repeatedly
    // until 2*x > y. Each doubling offsets the log2 by 1. The offset
    // is to be recovered later.
    long long               x = x0;
    int integral_part_of_log2 = 0;
    while (1) {
        const long long trial_x = x << 1;
        if (trial_x > y) break;
        x = trial_x;
        --integral_part_of_log2;
    }
    printf("integral_part_of_log2 == %d\n", integral_part_of_log2);

    // Calculate the denominator of -log(x/y).
    long long yy = 1;
    for (size_t j = N; j; --j) yy *= j*y;

    // Calculate the numerator of -log(x/y).
    long long xx = 0;
    {
        const long long y_minus_x = y - x;
        for (size_t i = N; i; --i) {
            long long term = 1;
            size_t j       = N;
            for (; j > i; --j) {
                term *= j*y;
            }
            term *= y_minus_x;
            --j;
            for (; j; --j) {
                term *= j*y_minus_x;
            }
            xx += term;
        }
    }

    // Convert log to log2.
    xx *= Kx;
    yy *= Ky;

    // Restore the aforementioned offset.
    for (; integral_part_of_log2; ++integral_part_of_log2) xx -= yy;

    printf("log2(%lld/%lld) == %lld/%lld\n", x0, y, xx, yy);
    printf("in floating point, this ratio of integers works out to %g\n",
      (1.0*xx)/(1.0*yy));
    printf("the CPU's floating-point unit computes the log2 to be  %g\n",
      log2((1.0*x0)/(1.0*y)));

    return 0;
}

运行在我的机器上使用 5 7 的命令行参数，它输出：

K == -1477/1024
x/y == 5/7
integral_part_of_log2 == 0
log2(5/7) == -42093223872/86740254720
in floating point, this ratio of integers works out to -0.485279
the CPU's floating-point unit computes the log2 to be  -0.485427

N = 12 和 Ky = 1 << 20 会显着提高准确性，但为此您需要更节俭的代码或超过 64 位。

节俭代码

更节俭的代码，需要更多的努力来编写，可能代表素数中的分子和分母。例如，它可能将 500 表示为 [2 0 3]，意思是 (2²)(3⁰)(5³).

然而，您的想象力可能会得到进一步的改进。

另一种方法

对于替代方法，虽然它可能无法完全满足您的要求，但如果您的程序是我的，@phuclv 已经给出了我倾向于遵循的建议：反向解决问题，猜测对数的值c/d，然后计算2^(c/d)，大概是通过Newton-Raphson迭代。就个人而言，我更喜欢 Newton-Raphson 方法。见教派。 4.8 here（我的原创）.

数学背景

包括我的链接在内的多个来源解释了第一种方法的泰勒级数和第二种方法的牛顿-拉夫森迭代。不幸的是，数学并不平凡，但你已经知道了。祝你好运。

如何通过按位运算尽可能精确地计算C中整数的log2

How to calculate the log2 of integer in C as precisely as possible with bitwise operations

c

bit-manipulation

entropy

bitwise-operators