c++ - 这个基数有多少位？

Question

问题是推导一个公式来确定给定十进制数在给定基数中可能具有的位数。

例如:十进制数100006可以分别用2、3、4、5、6、7、8为底的17、11、9、8、7、6、8位数字表示。

到目前为止，我得出的公式是这样的:(log10(num)/log10(base)) + 1。

在 C/C++ 中，我使用这个公式来计算上面给定的结果。

long long int size = ((double)log10(num)/(double)log10(base)) + 1.0;

但遗憾的是，在某些情况下公式没有给出正确答案，例如:

Number 8 in  base 2 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 64 in  base 2 : 1,0,0,0,0,0,0
Number of digits: 7
Formula returned: 6

Number 64 in  base 4 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 125 in  base 5 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 128 in  base 2 : 1,0,0,0,0,0,0,0
Number of digits: 8
Formula returned: 7

Number 216 in  base 6 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 243 in  base 3 : 1,0,0,0,0,0
Number of digits: 6
Formula returned: 5

Number 343 in  base 7 : 1,0,0,0
Number of digits: 4
Formula returned: 3

所以误差是 1 位数。我只是希望有人帮我更正公式，以便它适用于所有可能的情况。

编辑: 根据输入规范，我必须处理像 10000000000 这样的情况，即 10^10，我不认为 C/C++ 中的 log10() 可以处理这种情况？因此，对于此问题的任何其他程序/公式将不胜感激。

Answer 1

您的编译器设置中有快速 float 操作。您需要精确的 float 操作。问题是 log10(8)/log10(2) 在数学上总是 3。但是，例如，您的结果可能是 2.99999。这是坏的。您必须添加少量添加剂，但不能添加 0.5。它应该大约是 .00001 或类似的东西。

几乎正确的公式:

int size = static_cast<int>((log10((double)num) / log10((double)base)) + 1.00000001);

真正的解决方案

您应该检查公式的结果。复杂度为 O(log log n) 或 O(log result)!

int fast_power(int base, int s)
{
    int res = 1;
    while (s) {
        if (s%2) {
            res*=base;
            s--;
        } else {
            s/=2;
            base*=base;
        }
    }
    return res;
}

int digits_size(int n, int base)
{
    int s = int(log10(1.0*n)/log10(1.0*base)) + 1;
    return fast_power(base, s) > n ? s : s+1;
}

此检查优于使用 base 乘法的蛮力测试。