这个基地有多少位数？

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

编译器设置中有快速浮动操作.您需要精确的浮动操作.问题是log10(8)/ log10(2)在数学中总是3.但可能是你的结果是2.99999,用于示例.这是坏的.您必须添加小添加剂,但不能添加0.5.它应该是大约.00001或类似的东西.

几乎真正的公式:

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

真的是真的解决方案

你应该检查你的公式的结果.Compexity是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乘法的强力测试.

Answer 2

以下任何一种都可以使用:

>>> from math import *
>>> def digits(n, b=10):
...     return int(1 + floor(log(n, b))) if n else 1
...
>>> def digits(n, b=10):
...     return int(ceil(log(n + 1, b))) if n else 1
... 

第一个版本在mathpath.org上解释.在第二个版本中,+ 1必须为任何数字n产生正确答案,该数字是基数b中具有d位数的最小数字.也就是说,那些在基数b中写成10 ... 0的数字.请注意,必须将输入视为特殊情况.0

十进制示例:

>>> digits(1)
1
>>> digits(9)
1
>>> digits(10)
2
>>> digits(99)
2
>>> digits(100)
3

二进制:

>>> digits(1, 2)
1
>>> digits(2, 2)
2
>>> digits(3, 2)
2
>>> digits(4, 2)
3
>>> digits(1027, 2)
11

编辑:OP声明该log解决方案可能不适用于大输入.我不知道这一点,但如果是这样,下面的代码不应该分解,因为它只使用整数运算(这次是在C中):

unsigned int 
digits(unsigned long long n, unsigned long long b)
{
  unsigned int d = 0;
  while (d++, n /= b);
  return d;
}

此代码可能效率较低.而且是,它是最大的朦胧点写.它只是使用观察,即每个数字至少有一个数字,并且每个b不产生的分数0意味着存在一个额外的数字.更具可读性的版本如下:

unsigned int 
digits(unsigned long long n, unsigned long long b)
{
  unsigned int d = 1;
  while (n /= b) {
    d++;
  }
  return d;
}

Answer 3

给定基数中数字的位数