Fibonacci Seq. strani moduli di output (Haskell)

Question

Stavo guardando i risultati della mia implementazione della sequenza di Fibobacci in Haskell quando ho realizzato alcune forme "strane" nell'ottimizzazione dei numeri.

Prima di tutto, questo è il codice Haskell mi è venuta in mente:

fib :: Integer -> [Integer] 
fib 0 = [0] 
fib 1 = [0, 1] 
fib a = (fib' 0 1 [0,1] 1 a) 

fib' :: Integer -> Integer -> [Integer] -> Integer -> Integer -> [Integer] 
fib' n1 n2 l cont n 
     | cont == n = l 
     | otherwise = (fib' n2 n3 (l++[n3]) (cont+1) n) 
      where n3 = n2 + n1 

per qualcosa come 10 fib l'output sarà: [0,1,1,2,3,5, 8,13,21,34,55] Poi ho voluto provare qualcosa come fib 1000, mentre i numeri sono incredibilmente grandi e tutti ... quello che ho visto erano alcune strane elips formate dal "," che è stampato tra ogni intero dalla lista, ad esempio:

example1

così ho maxed la dimensione della finestra di output per vedere se questo strano modello sarebbe ancora ripetere, e la risposta è sì:

example2

E la mia domanda è:

Qualcuno sa perché appare questo modello in " , "tra gli Integer dalla lista? Non dovrebbe essere più casuale e meno come elipses?

Answer 1

numeri di Fibonacci grow as an exponential function di n.

La lunghezza di un numero decimale è essenzialmente la sua base logaritmo 10. Pertanto, la lunghezza di un Fibonacci cresce come una funzione lineare di n, perché il logaritmo ed esponenziale annullano a vicenda.

Quindi, se li hai stampati in una colonna, vedresti una linea retta. Ma li stampi uno dopo l'altro, quindi le posizioni si accumulano. Se stai prendendo somme cumulative di una sequenza lineare, ottieni una sequenza quadratica.

Localmente, ogni riga contiene circa lo stesso numero di numeri di Fibonacci, chiamiamolo k. Questo significa due cose:

1. numero la linea cambia linearmente con n.
2. Per calcolare le posizioni reali delle virgole (relative al bordo sinistro della finestra), dobbiamo prendere il resto della "posizione assoluta" cumulativa modulo la lunghezza della linea. Ciò equivale (in media) a sottrarre 1/k per ogni incremento di n. Questa regolazione è lineare e non modifica il comportamento quadratico della posizione.

Quindi quello che stai vedendo è una parabola - il grafico di una funzione quadratica.

Answer 2

Non c'è niente di strano quando vieni a pensarci. I numeri vicini di Fibonacci hanno una lunghezza simile e la lunghezza aumenta con la sequenza. Quindi, si supponga di avere una dimensione dello schermo di 30 caratteri, e il tuo attuale F(n) avere 29 cifre, quindi per i prossimi numeri, la lunghezza potrebbe essere:

29, 29, 29, 30, 30, 30, 31, 31, 31 

che vi dà la sinistra -> stabile -> movimento di destra .