Note sul calcolo dei grandi numeri

Nelle applicazioni pratiche può succedere che sia impossibile calcolare i valori di disposizioni, permutazioni e combinazioni usando direttamente le formule riportate. Ad esempio, se si vuole calcolare il numero di quartetti che si possono costituire da un gruppo di 200 persone, le calcolatrici vanno in ``overflow'' se si tenta di calcolare

$$\frac{200!}{196!4!}\,.$$

.

Lo stesso succede se si tenta di valutare $26^{200}$ (il numero di frasi diverse di 200 lettere a partire da un alfabeto di 26 lettere). A seconda dei casi si possono adottare diverse tecniche per risolvere il problema.

• Il metodo più semplice, soprattutto quando si ha interesse al risultato esatto (un intero), consiste nel risalire dalle formule compatte a quelle originali. In genere significa tornare dalla (3.4) alla (3.3) e riscrivere, ad esempio,
  $$\frac{200!}{196!4!} = \frac{200\times 199\times 198\times 197} {4!} = 64^\cdot684^\cdot950\,.$$
  Un altro trucco per evitare overflow anche nelle stesse moltiplicazioni, consiste nel fare la divisione dopo qualche moltiplicazione, oppure, soprattutto se si vuole arrivare a numeri interi esatti, conviene espandere anche il fattoriale del denominatore ed effettuare le opportune semplificazioni.

  Questo metodo funziona quando i grandi fattoriali si semplificano e i risultati rientrano nella capacità della calcolatrice.

• Se si hanno numeri diversi da 10 elevati a potenze molto grandi, come nel nostro esempio di $26^{200}$, conviene utilizzare le proprietà dei logaritmi^3.1. Infatti, valendo
  

  $$\log{b^a} = a \log{b} \,,$$

  
  
  ne segue
  

  $$b^a = 10^{a \log{b}} \,.$$

  
  
  Quindi nel nostro esempio avremmo
  

  $$26^{200} = 10^{282.9946696} = 10^{282+0.9946696} = 9.878013\times 10^{282}\,.$$

  
  
  Logaritmi importanti che andrebbero ricordati sono quelli in base dieci di 2 e di $e$, almeno nella loro forma approssimata: $\log{2} = 0.30$ e $\log{e}=0.43\approx 0.4$. Essi permettono infatti di stimare l'ordine di grandezza di potenze (calcolabili o no con la calcolatrice) che possono capitare di frequente. Ad esempio
  

  $$2^{64} \approx 10^{19}$$

  $$e^{-20} \approx 10^{-9} \div 10^{-8}$$

  
  

• Per i grandi fattoriali si usa invece la formula approssimata di Stirling:

  $$n! \approx \sqrt{2\pi n}\, n^n\,e^{-n}\,,$$ (3.12)

  
  
  in genere nella sua forma logaritmica poiché quando $n!$ dà overflow sulla calcolatrice a maggior ragione diventa incalcolabile $n^n$:

  $$\log{\frac{n!}{\sqrt{2\pi}}} \approxeq (n+\frac{1}{2})\, \log{n} -n\log{e}\,.$$ (3.13)

  
  
  Ad esempio, provando l'approssimazione con il maggiore fattoriale calcolabile con la maggior parte delle calcolatrici tascabili, abbiamo (con tutte le cifre indicate)
  

  $$\log{\frac{69!}{\sqrt{2\pi}}} \approxeq 97.83369255 = 97 + 0.83369255\,,$$

  
  
  da cui
  

  $$69! = \sqrt{2\pi} \times 10^{0.83369255}\times 10^{97} = 1.70915907 \times 10^{98}\,,$$

  
  
  da confrontare con $1.711224523 \times 10^{98}$ calcolato direttamente. Quindi l'approssimazione è accurata a circa una parte su mille già per $n\gtrsim 70$.