È difficile immaginare i grandi numeri: scacchi, carte e… un premio da un milione di dollari

“Un chicco di riso nella prima casella, due nella seconda, quattro nella terza e così via raddoppiando”. Tutti conosciamo la leggenda: l’inventore degli scacchi chiede questo come compenso e l’imperatore ci casca. Sì, perché è difficile immaginare a che punto arriva questo ripetuto raddoppio. Solo sull’ultima casella ci dovrebbero essere 2^63 = 9.223.372.036.854.775.808 chicchi. Certo è un numerone, ma non sembra una quantità esagerata. In effetti la notazione che usiamo per scrivere i numeri ne oscura l’enormità; capiamo di più confrontando i numeri con quantità note. Per esempio, sull’ultima casella l’imperatore dovrebbe metterci 362 volte l’intera produzione mondiale di riso del 2022.

La nostra intuizione vacilla anche con numeri più piccoli. Per esempio, per la nostra esperienza con gli euro distinguiamo bene fra 10^3, cioè mille, e 10^6, un milione; ma è già difficile avere il senso di quanto più grande sia 10^9, un miliardo. Lettore, prova tu stesso: a occhio, quanti minuti o ore o giorni sono un milione e un miliardo di secondi? Altro esempio: partendo da un normale foglio di carta, ad ogni passo raddoppio: al primo passo impilo due fogli, al secondo quattro eccetera. Dopo 50 passi come sarà il mucchio di fogli? Alto come una casa? Come un aereo in volo? Arriverà poco più in là della Luna? Quasi al Sole? Alla stella più vicina? Metto le risposte alla fine.

Un altro mostro: dato un numero n, n fattoriale (che si scrive n!), è il prodotto n*(n-1)*…*2*1. Anche questo è un numero che cresce in modo spaventoso; eppure è semplicemente il numero di modi per mettere in fila n oggetti. Prendiamo delle carte da gioco: con due carte ho due modi di metterle in fila; con tre ne ho 3!=6 e così via. Quanti modi ci sono di mettere in fila tutto il mazzo di 40 carte? Il numero è assurdo, non provo neanche a ragionaci sopra. Facciamo con un mazzo di 20 carte: i possibili modi di riordinarlo sono 20!, che è più di 24*(10^17). Lettore, rispondi a sentimento: se rimescolassimo il mazzo ogni secondo, per esaurire tutte le possibilità quanti giorni (o mesi o anni) occorrerebbero?

L’incredibile crescita del numero 2^n (e di 3^n, 10^n ecc., cioè quelle che si chiamano funzioni esponenziali) e di n! al crescere di n è una seccatura per i programmatori; è anche la ragione per un premio di un milione di dollari: ne ho parlato in un vecchio post e ne parlo dopo. La “complessità computazionale” di un algoritmo, cioè di un procedimento di calcolo, è il numero di operazioni necessarie. È una funzione della quantità di dati in ingresso. Per esempio, se devo sommare n numeri occorrono n-1 addizioni; questa è una complessità bassissima, quasi la migliore auspicabile. All’altro estremo c’è n!, la complessità di un algoritmo che ordini n oggetti in tutti i modi possibili.

In generale, sono accettabili gli algoritmi la cui complessità è una funzione polinomiale; quelli che hanno complessità esponenziale o addirittura fattoriale sono pessimi: potremmo non arrivare al risultato in un tempo ragionevole. In realtà, anche questi hanno una loro utilità “a rovescio”: i correnti metodi di protezione dei dati (Rsa), quando facciamo transazioni su internet, sono basati proprio sul fatto che gli algoritmi conosciuti per la decrittazione (per chi non ha la chiave) hanno complessità esponenziale. Ripeto: algoritmi conosciuti; domani qualcuno potrebbe inventare un algoritmo più furbo, a complessità polinomiale; o potrebbe risolvere il problema della decrittazione con un computer quantistico.

E il milione di dollari? È il premio che il Clay Institute offre a chi dimostri che una certa classe di problemi (chiamata NP) – fra cui ce ne sono alcuni che per ora sono risolti solo da algoritmi con complessità esponenziale – sia risolubile con complessità polinomiale. Ma dubito che il premio venga ritirato: se qualcuno riuscisse nell’impresa, guadagnerebbe molto ma molto di più fottendo i sistemi di transazione “sicura”.

Risposte approssimate ai quesiti (non ci credete? fate i conti!)
1) Mille secondi = 16,7 minuti, un milione di secondi = 11,6 giorni, un miliardo di secondi = 31,7 anni.
2) Dopo 50 raddoppi, il mucchio di fogli (ognuno spesso un decimo di millimetro) sarebbe alto 112 milioni di Km; il Sole dista 150 milioni di Km. Per superare la Luna (405.000 Km) bastano 42 raddoppi. Con 69 si va oltre Proxima Centauri (38.000 miliardi di Km).
3) Per rimescolare in tutti i modi 20 carte (una volta al secondo) occorrerebbero 77 miliardi di anni. L’universo ha meno di 14 miliardi di anni.