realfrac - round haskell

La manera más eficiente de obtener el conteo de dígitos de un número arbitrariamente grande

Question

¿Cuál es la forma más eficiente de obtener los dígitos de un número?

Comencemos con un ejemplo:

Imagina la secuencia de Fibonacci. Ahora digamos que queremos saber qué número de Fibonacci es el primero en tener 1000 dígitos (en la representación de la base 10). Hasta 308 dígitos (número 1476a de Fibonacci) podemos hacer esto fácilmente usando logBase 10 <number> . Si el número es mayor que el 1476º número de Fibonacci, logBase devolverá Infinity y el cálculo fallará. El problema es que 308 está algo lejos de 1000, que era nuestro objetivo inicial.

Una posible solución es convertir el número que queremos saber la cantidad de dígitos de una cadena y usar su longitud para determinar el conteo de dígitos. Esto es un poco ineficiente para mis propósitos, ya que probar esto con 10000 lleva su buen momento.

El método más eficiente que se muestra en otras preguntas es codificar todos los casos posibles que realmente no quiero hacer, especialmente porque la cantidad de dígitos excede 10 según las soluciones propuestas.

Entonces, para volver a mi pregunta: ¿Cuál es la mejor (la más eficiente) forma de determinar un recuento de dígitos de 10 números base? ¿Realmente se está convirtiendo en una cadena y usando su longitud o hay algún truco de "hacker" como 0x5f3759df ?

Nota: Agradezco las soluciones en cualquier idioma, incluso si está etiquetado como "haskell".

Answer 1

¿Por qué no usar div hasta que ya no sea mayor a 10?

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

Esta es la complejidad de O(n) , donde n es el número de dígitos, y usted podría acelerarlo fácilmente comprobando contra 1000 , luego 100 , luego 10 , pero esto probablemente será suficiente para la mayoría de los usos.

A modo de referencia, en mi portátil no tan bueno, ejecutando solo en GHCi y usando la bandera de estadística horriblemente inexacta :set +s :

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

Por lo tanto, parece bastante rápido, puede batir a través de un número de 10001 dígitos en menos de una décima de segundo sin optimizaciones.

Si realmente deseaba la complejidad O(log(n)) , le recomendaría que escriba su propia versión en la que divide por 2 cada vez, pero esa es un poco más complicada y complicada que dividir por 10. Para sus propósitos, esta versión Calcule fácilmente el número de dígitos hasta aproximadamente 20000 dígitos sin problemas.

Answer 2

Si solo desea encontrar el primer número con al menos dígitos de digitCount en una lista, puede probar cada número en O(1) comprobando si fibBeingTested >= 10 digitCount - 1 . Esto funciona ya que 10 digitCount - 1 es el número más bajo con dígitos digitCount mínimo:

import Data.List (find)
fibs :: [Integer]
-- ...
findFib :: Int -> Integer
findFib digitCount =
let Just solution = find (>= tenPower) fibs
in
solution
where
tenPower = 10 ^ (digitCount - 1)

Usamos digitCount - 1 porque 10^1 , por ejemplo, es 10 que tiene dos dígitos.

Como resultado de la complejidad de O(1) que tiene esta comparación, puede encontrar los números de Fibonacci muy rápidamente. En mi máquina:

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

Si la lista de fibs ya se ha calculado hasta el dígito número 10,000th Fibonacci (por ejemplo, si ejecuta findFib 10000 dos veces) es incluso más rápido, lo que muestra que se está computando cada número de Fibonacci más que encontrar el que ''que estas buscando:

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

Answer 3

Siempre puede intentar la búsqueda binaria para encontrar el número de dígitos de n : primero encuentre una k tal que 10 ^ 2 ^ k ≥ n, y luego divida n sucesivamente por 10 ^ 2 ^ (k-1), 10 ^ 2 ^ ( k-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)

Para el caso específico de los números de Fibonacci, también podría intentar con las matemáticas: el n -ésimo número de Fibonacci F (n) está entre (φ ^ n-1) / √5 y (φⁿ + 1) / √5, por lo que para la base 10 logaritmo que tenemos:

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

Ese intervalo se pone muy pequeño de inmediato.

Answer 4

Solo por obtener un número de Fibonacci que tenga más de 1000 dígitos, length . show length . show (en Integer ) es suficiente.

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)

Para números de coma flotante (para que pueda usar logBase) fuera del rango de doble mirada al paquete de numbers . Son muy lento, pero tienes que pagar algo por ese tipo de precisión.