最有效的方法来获得任意大数字的数字计数

Question

获取数字数字的最有效方法是什么？

让我们从一个例子开始:

想象一下Fibonacci序列.现在让我们说我们想要知道哪个Fibonacci数是第一个有1000个数字(以10为基数表示).最多308位数(1476th Fibonacci数)我们可以通过使用轻松完成此操作logBase 10 <number>.如果该数字大于第1476个Fibonacci数,logBase则返回Infinity并且计算将失败.问题是308距离1000有点远,这是我们最初的目标.

一种可能的解决方案是将我们想要知道的数字转换为字符串的数字,并使用它的长度来确定数字计数.这对我的目的来说效率有点低,因为用10000来尝试这个时间需要花费很多时间.

其他问题中显示的最有效的方法是硬编码我真正不想做的所有可能的情况,特别是因为所提出的解决方案中所需的位数超过10.

那么回到我的问题:确定基数为10的数字计数的最佳(最有效)方法是什么？是真的将它转换为字符串并使用它的长度还是有任何"黑客"技巧,如0x5f3759df？

注意:我很欣赏任何语言的解决方案,即使它被标记为"haskell".

Answer 1

为什么不使用div它直到它不再大于10？

digitCount :: Integer -> Int
digitCount = go 1 . abs
    where
        go ds n = if n >= 10 then go (ds + 1) (n `div` 10) else ds

这是O(n)复杂性,其中n是位数,你可以通过检查来轻松加快1000,然后100,然后10,这可能足以满足大多数用途.

作为参考,在我不太好的笔记本电脑上运行它只在GHCi中使用可怕的不准确的:set +s统计标志:

> let x = 10 ^ 10000 :: Integer
> :force x
<prints out 10 ^ 10000>
> digitCount x
10001
it :: Int
(0.06 secs, 23759220 bytes)

所以看起来非常快,它可以在不到10秒的时间内通过10001位数而无需优化.

如果你真的想要O(log(n))复杂性,我会建议你自己编写你每次除以2的版本,但是这个版本比除以10更复杂,更棘手.为了你的目的,这个版本将很容易计算出数字的位数大约20000位没有问题.