c-不同基数的大整数位数的上限

Question

我想从字符串表示中创建一个大整数，为了有效地做到这一点，我需要目标基数中位数的上限，以避免重新分配内存。

示例：

一个640 bit数字在base 2中有640位，但在base 2^64中只有10位，所以我必须分配10个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范围的二进制（非负）整数。由于源和目标碱基的数量相对较少，这些值可以预先计算并在表中查找，但在数学上k（b，w）=[wlog2/logb]（其中[.]表示整数部分。）

对于给定的n，设m=ceil（n/k（b，w））。则保持小于b^n的数字所需的最大dst_base位数为：

ceil（log（b^n-1）/log（2^w））≤ceil（log（b^n）/log≤ceil（m.log（b^k（1b，w））/log（2^w））≤m。

简言之，如果您预先计算k（b，w）值，您可以通过将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);
}

请注意：

• 此函数返回的结果与您的不同！然而，在我查看的每一个案例中，两者都是正确的（值越小越准确，但您的要求只是一个上限）
• 我编写的整数版本接收log2_dst_base而不是dst_base，以避免2^64溢出
• 使用查找表可以使CCD_ 18更加高效
• 我用了unsigned int而不是int