Numeri grandi di Fibonacci

Numeri grandi di Fibonacci

Come trovare velocemente i loro esatti valori numerici

Cristiano Teodoro

cristianoteodoro@virgilio.it

Sommario

Sommario: in questo articolo viene proposto, in alternativa al metodo classico per il calcolo dei numeri della successione di Fibonacci, un algoritmo con il quale, tramite l’ausilio di un’altra importante successione di numeri, quella relativa ai numeri di Lucas, è possibile calcolare il valore esatto di un numero grande di Fibonacci in un tempo molto più rapido. Per numeri di Fibonacci molto grandi composti da migliaia di cifre il tempo di calcolo risulta essere almeno di 35 volte più breve.

I numeri di Fibonacci sono sufficientemente noti per cui qui si accennerà solo alla loro definizione e si illustrerà un algoritmo per il calcolo rapido del loro esatto valore numerico. Per una descrizione dettagliata riguardante la loro implicazione in numerose e diverse discipline interessanti sia il campo della scienza o della tecnica o dell’economia come pure il campo dell’arte si rimanda alla lettura di numerosi e interessanti articoli comparsi sui Siti Internet.

La successione di Fibonacci

I numeri di Fibonacci scaturiscono da una successione di numeri che obbediscono alle seguenti regole:

Partendo da due numeri iniziali che indicheremo con F(0) e F(1), rispettivamente di valore 0 e 1, il successivo numero di Fibonacci F(2) è dato dalla somma di F(0) con F(1), cioè F(2) = F(0) + F(1) = 0 + 1 = 1.

I successivi numeri si trovano sommando sempre i due precedenti numeri. Pertanto per essi vale la formula seguente: F(k) = F(k – 1) + F(k – 2), dove con F(k) si indica il numero generico di Fibonacci che nella successione occupa il (k + 1)-esimo posto, con k denominato indice del numero.

Pertanto la successione generica di numeri di Fibonacci può indicarsi come segue:

F(0) = 0 F(1) = 1

F(2) = F(0) + F(1) = 1

F(3) = F(1) + F(2) = 2

F(4) = F(3) + F(2) = 3

F(5) = F(3) + F(4) = 5

F(6) = F(4) + F(5) = 8

…………………..

F(k) = F(k – 2) + F(k – 1) = ?

..................................

Il calcolo dei numeri grandi

Ora, volendo conoscere il valore numerico di F(k), se non si hanno disponibili per tali numeri altre formule, risulta evidente che per trovarlo occorre conoscere e quindi calcolare tutti i precedenti numeri di Fibonacci.

Questo metodo di procedere risulta adeguato solo se il valore dell’indice k non è molto grande. Ma se l’indice k ha valore grande, ad esempio k = 100000, per trovare F(k) sarebbe necessario effettuare un numero di addizioni pari a k e cioè centomila di addizioni.

Realizzando su un Personal Computer in un qualsiasi linguaggio evoluto un semplice programma per il calcolo di F(100000), anche impiegando un PC sofisticato il tempo per effettuare 100000 operazioni aritmetiche di addizione non risulta indifferente (vedi Tabella in fondo all’articolo).

Sorge poi un altro problema: quanto può essere grande F(100000)? Di quante cifre è composto?

Il numero di cifre

Per rispondere a questo quesito fortunatamente la matematica mette a disposizione la seguente formula per il calcolo del numero di cifre:

(1)

⎛ ⎞ k

+

1 1 5

⎜ ⎟

⎜ ⎟

F(k) = ⎝ ⎠

2

5

x

10 si può trovare il valore dell’esponente x da cui si ricava

Da tale formula, uguagliandola a

immediatamente il numero Nc delle cifre componenti F(k) come parte intera di x aumentata di 1

⎞

⎛

⎛ ⎞ k +

+ 1 5 1

1 1 5 ⎟

⎜

⎜ ⎟ +

−

x ⎣ ⎦

⎟

⎜

⎜ ⎟ 10 x 1

log log 5

k

si ha pertanto = da cui x = e quindi Nc =

⎠

⎝

⎝ ⎠ 2 2

2

5

Facciamo un esempio proprio con k = 100000: svolgendo i calcoli relativi con la formula suddetta si trova x = 20898.41454… Quindi 20899 è il numero effettivo di cifre di cui risulta composto F(100000).

______________

(1) - Per il calcolo del numero di cifre che compongono il numero di Fibonacci è lecito trascurare la parte con segno negativo della formula di Binet (vedi la formula a pag. seguente) 1

Il calcolo esatto

Ma pur conoscendo l’esatto numero di cifre di F(100000), come è possibile calcolare il suo valore esatto dato l’enorme numero di cifre implicate?

Dobbiamo inevitabilmente fare ricorso ad operazioni aritmetiche che elaborano numeri molto grandi per i quali non risulta più sufficiente l’aritmetica che normalmente viene messa a disposizione sul PC dal software utilizzato.

Si presentano pertanto due problemi da risolvere:

• Il primo è quello di riuscire a manipolare e potere fare calcoli aritmetici esatti su numeri molto grandi;
• Il secondo è quello di poter in qualche modo evitare di effettuare un numero grande di operazioni aritmetiche e cioè 100000 addizioni, ad esempio per il calcolo esatto di F(100000).

Per evitare di effettuare questo grande numero di addizioni si potrebbe pensare di ricorrere alla formula di Binet [1], [2], che dà in forma concisa il valore di un qualsiasi numero di Fibonacci F(k):

⎛ ⎞

⎛ ⎞ k k

−

+

1 1 5 1 1 5

⎜ ⎟

⎜ ⎟ − ⎜ ⎟

⎜ ⎟ ⎝ ⎠

⎝ ⎠

2 2

5 5

Sfortunatamente questa formula, nemmeno usando un’aritmetica a precisione multipla, si presta ad essere utilizzata per il calcolo esatto di F(k) in quanto, pur prescindendo dal grande numero di elevazione a potenza

5

(difficoltà questa che si potrebbe facilmente superare), nella formula compare il numero irrazionale, per giunta anche a denominatore.