我需要计算熵，由于我的系统的限制，我需要使用受限的C特性(没有循环，没有浮点支持(，我需要尽可能多的精度。从这里我了解了如何使用逐位运算来估计整数的下限log2。尽管如此，我还是需要提高结果的准确性。由于不允许进行浮点运算，有没有办法用x < y计算log2(x/y)，使结果类似于log2(x/y)*10000，目的是通过算术整数获得我需要的精度？
您将基于公式来创建算法
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，因此足以证明这一概念。在toy代码中，较大的值可以无声地溢出默认的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/%lldn", 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/%lldn", 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 == %dn", 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/%lldn", x0, y, xx, yy);
printf("in floating point, this ratio of integers works out to %gn",
(1.0*xx)/(1.0*yy));
printf("the CPU's floating-point unit computes the log2 to be %gn",
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位的代码。
THRIFTIER代码
更繁荣的代码，需要更多的精力来编写，可能会在素数中表示分子和分母。例如，它可以将500表示为[2 0 3]，意思是(22((3<0>(。
然而，你的想象力可能会得到进一步的提升。
替代方法
对于另一种方法，尽管它可能无法完全满足您的要求，但@phuclv给出了一个建议，如果您的程序是我的，我会倾向于遵循这个建议：反向解决问题，猜测对数的值c/d，然后计算2^(c/d)，大概是通过Newton-Raphson迭代。就我个人而言，我更喜欢Newton-Raphson方法。见第节。4.8这里(我的原件(。
数学背景
包括我在内的几个来源已经解释了第一种方法的泰勒级数和第二种方法的牛顿-拉斐森迭代。不幸的是，数学并不平凡，但你已经掌握了。祝你好运。