haskell - 获得任意大数字的位数的最有效方法

Question

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

让我们从一个例子开始:

想象一下斐波那契数列。现在假设我们想知道哪个斐波那契数列是第一个拥有 1000 位数字的数列(以 10 为基数表示)。最多 308 位(第 1476 个斐波那契数)，我们可以通过使用 logBase 10 <number> 轻松做到这一点。如果数字大于第 1476 个斐波那契数，logBase将返回Infinity并且计算将会失败。问题是 308 距离我们最初的目标 1000 有点远。

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

other questions中所示的最有效的方法正在对我真的不想做的所有可能情况进行硬编码，特别是因为建议的解决方案中需要的位数超过 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)

看起来相当快，无需优化，它可以在不到十分之一秒的时间内处理完 10001 位数字。

<小时/>

如果您确实想要 O(log(n)) 复杂度，我建议您编写自己的版本，每次除以 2，但这个版本比除以 10。出于您的目的，此版本可以轻松计算最多约 20000 位的位数，不会出现任何问题。