Modo più efficace per ottenere il conteggio delle cifre del numero arbitrariamente grande

Question

Qual è il modo più efficace per ottenere le cifre di un numero?

Inizia con un esempio:

Immagina la sequenza di fibonacci. Ora diciamo che vogliamo sapere quale numero di fibonacci è il primo ad avere 1000 cifre (nella rappresentazione di base 10). Fino a 308 cifre (1476 ° numero di fibonacci) possiamo facilmente farlo usando logBase 10 <number>. Se il numero è maggiore del 1476 ° numero Fibonacci, logBase restituirà Infinity e il calcolo fallirà. Il problema è che 308 è un po 'lontano da 1000, che era il nostro obiettivo iniziale.

Una possibile soluzione è di convertire il numero che desideri conoscere il numero di cifre di una stringa e utilizzare la sua lunghezza per determinare il conteggio delle cifre. Questo è un po 'inefficiente per i miei scopi perché provarlo con 10000 prende il suo tempo dolce.

il metodo più efficiente mostrato in altre domande < / A> sta hardcoding Tutti i casi possibili che I veramente non si desidera fare, soprattutto perché il numero di cifre supera i 10 se necessario nelle soluzioni proposte.

Pertanto tornare alla mia domanda: qual è il modo migliore (più efficiente) per determinare un numero di cifre di base di 10 numeri? È davvero convertendo a una stringa e usando la sua lunghezza o ci sono trucchi "hacker" come 0x5f3759df ?

Nota: apprezzo le soluzioni in qualsiasi lingua, anche se questo è taggato "Haskell".

Answer 1

Perché non utilizzare div finché non è più superiore 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

.

Questa è la complessità O(n), in cui n è il numero di cifre e è possibile accelerarlo facilmente controllando contro 1000, quindi 100, quindi 10, ma questo sarà probabilmente sufficiente per la maggior parte degli usi.

---

.

Per riferimento, sul mio laptop non-così-grande che lo esegue solo in GHCI e utilizzando l'orribilmente inaccurato flag di statistiche :set +s:

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

.

Quindi sembra piuttosto veloce, può stenuire di un numero di 10001 cifre in meno di un secondo secondo senza ottimizzazioni.

---

.

Se volevi veramente la complessità O(log(n)), consiglierei di scrivere la tua versione in cui ti dividi per 2 ogni volta, ma quello è un po 'più coinvolto e più complicato che dividere per 10. Per i tuoi scopi questa versione calcolerà facilmente il Numero di cifre fino a circa 20000 cifre senza problemi.

Answer 2

Se si desidera semplicemente trovare il primo numero con almeno cifre digitCount in un elenco, è possibile testare ciascun numero in O(1) controllando se fibBeingTested >= 10digitCount - 1.Funziona da quando 10digitCount - 1 è il numero più basso con cifre almeno 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)

.

Utilizziamo digitCount - 1 perché 10^1, ad esempio, è 10 che ha due cifre.

A seguito della complessità O(1) che questo confronto ha, è possibile trovare i numeri di fibonacci molto rapidamente.Sulla mia macchina:

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

.

Se l'elenco di fibs è già stato calcolato fino alla cifra 10,000th Fibonacci (ad esempio, se si esegue findFib 10000 due volte) è ancora più veloce, il che mostra che più calcolo è in atto nel calcolare ciascun numero di fibonacci rispetto a trovare quello di fibonacci rispetto aStai cercando:

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

.

Answer 3

Per essere appena arrivato a un numero di fibonacci che ha più di 1000 cifre, length . show (su Integer) è sufficiente.

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)

.

Per i numeri del punto flottante (in modo da poter utilizzare il logbase) al di fuori dell'intervallo di doppia occhiata al pacchetto numbers.Sono down-a destra lenti, ma devi pagare qualcosa per quel tipo di precisione.

Answer 4

Puoi sempre provare la ricerca binaria per trovare il numero di cifre di n : prima trova un k tale che 10 ^ 2 ^ k ≥ n, quindi dividi nPorreva di 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)

.

Per il caso specifico dei numeri di fibonacci, è possibile provare anche matematica: il numero n -th fibonacci numero f (n) è tra (φ ^ n-1) / √5 e (φⁿ + +1) / √5 Quindi per la base 10 logaritmo Abbiamo:

.

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

L'intervallo diventa piccolo subito.