C:使用对数函数安全地计算基数 (b) 的整数 (N) 的位数

Question

给定公式:

NUM_DIGITS_IN_N_FOR_BASE_B = 1 + floor(ln(abs(N))/ln(b))

b 是 2 到 36 之间的基数，N 是 int 类型。

根据这篇文章post 1似乎可以假设为所有整数 [INT_MIN, INT_MAX] 范围返回的值将在没有舍入或溢出错误的情况下工作。我对此有点怀疑。我的怀疑来自于我最近的一篇帖子@ post 2 .如果在计算机程序中使用数学定义不“安全”，是否有另一种技巧可用于计算给定基数 b 的数字 N 中的位数？

Answer 1

Is it safe to calculate the number of digits in an integer N in base b using logarithmic functions?

不，绝对不是，由于舍入误差。具体来说，风险是 log(N)/log(b)会略小于精确值。这最有可能发生在 N 时。是 b 的精确倍数.

How does one count the number of digits in an integer N in base b?

划分N通过 b循环直到N为零。查看 countDigits函数在下面的代码中。处理 N <= 0 的值留给读者作为练习。

---

例如，考虑下面的代码

int countDigits( int N, int b )
{
    int count;
    for ( count = 0; N; count++ )
        N /= b;
    return count;
}

int main( void )
{
    int N, b;
    if ( scanf( "%d %d", &N, &b ) != 2 )
        return 1;

    printf( "log(%3d) = %.50lf\n", N, log(N) );
    printf( "log(%3d) = %.50lf\n", b, log(b) );
    printf( "ratio    = %.50lf\n", log(N)/log(b) );
    printf( "expected = %d\n", countDigits(N, b) );
    double digits = 1 + floor(log(N) / log(b));
    printf( "computed = %lf\n", digits );
}

如果用户为 N 输入 243，为 b 输入 3，则输出为

log(243) = 5.49306144334054824440727315959520637989044189453125
log(  3) = 1.09861228866810978210821758693782612681388854980469
ratio    = 4.99999999999999911182158029987476766109466552734375
expected = 6
computed = 5.000000

由于 243₁₀ = 100000₃，因此预期位数为 6。对数法的问题是 log(243)有点太小或log(3)稍微太大，导致比率刚好低于 5什么时候应该是 5 .