Numeri grandi di Fibonacci

NUMERI GRANDI DI FIBONACCI

come trovare velocemente i loro esatti valori numerici

Cristiano Teodoro

cristianoteodoro@virgilio.it

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.

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 ) = ?

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

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?

Per rispondere a questo quesito fortunamente la matematica mette a disposizione la seguente formula per il

(

1

)

calcolo del numero di cifre : ⎛ ⎞ 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

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

nota in matematica come 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.

Per risolvere il primo problema come si è accennato, occorre fare ricorso all’uso di un aritmetica a

precisione multipla, messa a disposizione da specializzati pacchetti software o come si è fatto nei programmi

realizzati creando opportune istruzioni nel linguaggio evoluto utilizzato.

Resta da risolvere il secondo problema.

Per esso bisogna fare ricorso all’impiego di un’altra famosa successione di numeri denominati numeri di

Lucas prendendo in considerazione particolari relazioni che legano fra di loro i numeri delle due

successioni.

Questa nuova successione, indicando con L(k) il suo generico termine è analoga alla successione di

Fibonacci, ma con i suoi primi due termini aventi i seguenti valori. L(0) =2 e L(1) = 1

Anche qui vale la relazione L(k) = L(k – 2) + L( k – 1)

Pertanto i primi sette numeri della successione di Lucas sono i seguenti:

L(0) = 2 L(1) = 1

L(2) = L(0) + L(1) = 3

L(3) = L(1) + L(2) = 4

L(4) = L(3) + L(2) = 7

L(5) = L(3) + L(4) = 11

L(6) = L(4) + L(5) = 18

……………………….

Come detto sopra, occorre considerare delle peculiari relazioni esistenti fra i numeri di queste due

successioni, relazioni che si possono trovare in opportuni testi di matematica [3],[4],[5]. Da esse si possono

ottenere dopo adeguate manipolazioni le seguenti finali relazioni che interessano il nostro caso, e che quindi

prenderemo in considerazione:

per un indice k di valore pari, posto k = 2x: si ha :

F(k) = F(2x) = F(x) · L(x) (1p)

⋅ −

2 x

( ) 2 ( 1

)

x

L(k) = L(2x) = L – (2p)

per un indice k di valore dispari posto k = 2x+1 si ha :

⋅ −

2 x

( ) 2 ( 1

)

x – (1d)

2F(k) = F (2x +1) = F(x)L(x) + L ⋅ −

2 x

( ) 2 ( 1

)

x

2L(k) = L(2x +1) = L + 5 F(x) · L(x) – (2d)

Si fa osservare che per un indice k qualsiasi i valori di F(k) e di L(k) dipendono solo dall’indice x e dai

−

k 1

k

valori F(x) e L(x) dove risulta: per k pari x = ; per k dispari x =

2 2

2

k k

Consideriamo ora un qualsiasi indice k: posto = k si costruisca a partire da una successione di

n n

indici interi di valore numerico decrescente:

k , k , k ,.........

..........

..........

.....

k , k , k ,.........

..........

..........

........

k , k , k

− − + −

n n 1 n 2 i 1 i i 1 3 2 1

tale da rispettare le seguenti regole: k

= i

k

k

se il generico indice è di valore pari si pone −

i 1

i 2 − 1

k

= i

k

k

se il generico indice è di valore dispari si pone −

i 1

i 2 k = 1.

Si mette in evidenza che tale tipo di successione è limitata e termina sempre con il valore dell’indice 1

log k n

Essa risulta composta da un numero di indici uguale alla parte intera di aumentata di 1, dove con

log 2

il simbolo di log si indica il logaritmo in base 10. Ad esempio per un indice k = 100000 il numero totale

degli indici è 17. k k k

= 1 per il quale si ha F ( ) = 1 e L( ) = 1 si possono calcolare in relazione ai

Partendo dall’indice 1 1 1

k

k

vari indici della successione i valori di F( ) e di L( ) con l’impiego delle formule (1p) ,(2p), (1d), (2d)

i

i

adattate come qui indicato:

k

per un pari

i

F( ) = F( ) L( )

k · k (

k 3p)

− −

i i

1 1

i ⋅ − k −

2 ( 1 )

2 i 1

L( ) = L( )

k k – (4p)

−

i i 1

k

per un dispari

i ⋅ − k −

2 ( 1 )

2 i 1

2F( ) = F( ) · L( ) + L( ) –

k k k

k (3d)

− − −

i i i

1 1 1

i ⋅ − k −

2 ( 1 )

2 i 1

2L( ) = L( ) + 5 F( ) · L( ) –

k k k

k (4d)

− − −

i i i

1 1 1

i ⎢ ⎥

log k n

F L ⎢ ⎥

( k ) ( k )

e di con un ciclo limitato di iterazioni pari a

si arriverà così ai valori cercati di ⎣ ⎦

n n log 2

log k n

vale a dire al massimo intero contenuto in log 2

k k k k

Infatti con i valori di F( ) e di L( ), si possono calcolare i valori di F( ) e di L( ) dove

− −

i i i i

1 1

k k k

l'indice se è pari è il doppio dell'indice , se dispari è il doppio di aumentato di 1. Si arriva così,

−

i i i

1 ( k ) ( k )

partendo dai valori di F (1) e di L(1) , a trovare i valori di F e di L effettuando sulle formule

n n

mostrate nel riquadro il limitato suddetto ciclo di iterazioni.

Un semplice esempio chiarirà quanto detto.

Si voglia trovare il valore di F(k) e di L(k) per un indice k = 73 k

Innanzitutto vediamo di quanti valori è composta la successione degli indici i

log 73

Si ha = 6,1898…. e quindi il numero di iterazioni sarà pari a 6

log 2

La successione degli indi k tenendo conto delle regole summenzionate sarà poi la seguente:

k k k k

k k k

= 73 = 36 = 18 = 9 = 4 = 2 = 1

7 6 5 4 3 2 1

k k

utilizzando ora le relazioni (3p) e (4p) se è