Самый эффективный способ получить количество цифр произвольно большого числа

Почему бы не использовать 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-значное число менее чем за 10-ю долю секунды без оптимизации.

Если вам действительно нужна сложность O(log(n)), я бы порекомендовал написать свою собственную версию, в которой вы каждый раз делите на 2, но это немного сложнее и сложнее, чем деление на 10. Для ваших целей эта версия легко вычислит количество цифр. примерно до 20000 цифр без проблем.

Если вы просто хотите найти первое число, содержащее не менее digitCount цифр в списке, вы можете проверить каждое число в O(1), проверив, соответствует ли fibBeingTested >= 10digitCount - 1. Это работает, поскольку 10digitCount - 1 — это наименьшее число, состоящее как минимум из digitCount цифр:

import Data.List (find)

fibs :: [Integer]
-- ...

findFib :: Int -> Integer
findFib digitCount =
  let Just solution = find (>= tenPower) fibs
  in
  solution
  where
    tenPower = 10 ^ (digitCount - 1)

Мы используем digitCount - 1, потому что, например, 10^1 — это 10, состоящее из двух цифр.

В результате O(1) сложности, которую имеет это сравнение, вы можете очень быстро найти числа Фибоначчи. На моей машине:

λ> :set +s
λ> findFib 10000
[... the first Fibonacci number with at least 10,000 digits ...]
(0.23 secs, 121255512 bytes)

Если список из fibs уже был рассчитан до 10,000th цифры Фибоначчи (например, если вы запускаете findFib 10000 дважды), он выполняется даже быстрее, что показывает, что при вычислении каждого числа Фибоначчи выполняется больше вычислений, чем при нахождении того, которое вы ищете. находясь в поиске:

λ> findFib 10000   -- Second run of findFib 10000
[... the first Fibonacci number with at least 10,000 digits ...]
(0.04 secs, 9922000 bytes)

Чтобы просто получить число Фибоначчи, которое состоит из более чем 1000 цифр, достаточно length . show (на Integer).

GHCi> let fibs = Data.Function.fix $ (0:) . scanl (+) 1
GHCi> let digits = length . (show :: Integer -> String)
GHCi> :set +t +s
GHCi> fst . head . dropWhile ((1000>) . digits . snd) $ zip [0..] fibs
4782
it :: Integer
(0.10 secs, 149103264 bytes)

Для чисел с плавающей запятой (чтобы вы могли использовать logBase) за пределами диапазона Double посмотрите на пакет numbers. Они очень медленные, но за такую ​​точность приходится платить.

Вы всегда можете попробовать двоичный поиск, чтобы найти количество цифр n: сначала найдите k такое, что 10^2^k ≥ n, а затем последовательно разделите n на 10. ^2^(к-1), 10^2^(к-2),..., 10^2^0:

numDigits n = fst $ foldr step (1,n) tenToPow2s
  where
    pow2s = iterate (*2) 1
    tenToPow2s = zip pow2s . takeWhile (<=n) . iterate (^2) $ 10
    step (k,t) (d,n) = if n>=t then (d+k, n `div` t) else (d,n)

Для конкретного случая чисел Фибоначчи вы также можете просто попробовать математику: n-е число Фибоначчи F(n) находится между (φ^n-1)/√5 и (φⁿ+1)/ √5, поэтому для логарифма по основанию 10 имеем:

log(F(n)) - n log(φ) + log(√5) ∈ [log(1 - 1/φⁿ), log(1 + 1/φⁿ)]

Этот интервал сразу становится крошечным.