不同基数中大整数位数的上限

Question

我想从字符串表示中创建一个大整数并高效地执行此操作，我需要目标基数中的位数上限以避免重新分配内存。

示例：

一个640 bit数在base 2中有640位，但在base 2^64中只有十位，所以我将不得不分配十个64 bit整数来保存结果.

我目前使用的功能是：

int get_num_digits_in_different_base(int n_digits, double src_base, double dst_base){
    return ceil(n_digits*log(src_base)/log(dst_base));
}

其中 src_base 在 {2, ..., 10 + 26} 中，dst_base 在 {2^8, 2^16, 2^32, 2^64} 中。

我不确定结果是否总是正确四舍五入。 log2 会更容易推理，但我读到旧版本的 Microsoft Visual C++ 不支持该功能。它可以像 log2(x) = log(x)/log(2) 一样被模拟，但现在我回到了我开始的地方。

GMP 可能实现了一个函数来进行基础转换，但我可能没有阅读源代码，否则我可能会患上 GPL 癌症，所以我不能这样做。

Answer 1

我认为速度是一个问题，否则您可以尝试基于浮点数的估计，如果结果太小则进行调整。在那种情况下，可以牺牲估计的严密性来换取速度。

下面设dst_base为2^w，src_base为b，n_digits 为 n.

令 k(b,w)=max {j | b^j < 2^w}。这表示 b 的最大幂，保证适合 w 范围的二进制（非负）整数。由于源和目标碱基的数量相对较少，这些值可以在 table 中预先计算和查找，但在数学上 k(b,w)=[w log 2/log b]（其中[.]表示整数部分。）

对于给定的 n 让 m=ceil( n / k(b,w))。那么容纳一个小于b^n的数需要的最大dst_base位数是：

ceil(log (b^n-1)/log (2^w)) ≤ ceil(log (b^n) / log (2^w) ) ≤ ceil( m .log (b^k(b,w)) / log (2^w) ) ≤ m.

简而言之，如果您预先计算 k(b,w) 值，您可以通过除以 [=26= 来快速获得上限（这并不严格！） ]n 通过 k，四舍五入。

Answer 2

我不确定这种情况下的浮点数舍入，但仅使用整数来实现它相对容易，因为 log2 是一种经典的位操作模式，整数除法可以很容易地向上舍入。以下代码与您的代码等效，但使用整数：

// Returns log2(x) rounded up using bit manipulation (not most efficient way)
unsigned int log2(unsigned int x)
{
    unsigned int y = 0;
    --x;
    while (x) {
        y++;
        x >>= 1;
    }
    return y;
}

// Returns ceil(a/b) using integer division
unsigned int roundup(unsigned int a, unsigned int b)
{
    return (a + b - 1) / b;
}

unsigned int get_num_digits_in_different_base(unsigned int n_digits, unsigned int src_base, unsigned int log2_dst_base)
{
    return roundup(n_digits * log2(src_base), log2_dst_base);
}

请注意：

此函数return 与您的结果不同！但是，在我查看的每种情况下，两者都仍然正确（较小的值更准确，但您的要求只是一个上限）。
我写的整数版本接收 log2_dst_base 而不是 dst_base 以避免 2^64.
log2 使用查找表可以提高效率。
我用 unsigned int 而不是 int。

不同基数中大整数位数的上限

Upper bound for number of digits of big integer in different base

c

floating-point

floating-accuracy

floating-point-precision