matematica_light

Negli anni ’90 del secolo scorso i personal computer cominciavano a essere una presenza usuale, e spuntavano i primi giochi grafici: il guaio è che per avere della bella grafica occorre fare tanti conti e la potenza di quei computer non era certo quella attuale, soprattutto se si dovevano usare le operazioni in virgola mobile e non quelle con gli interi. Occorreva dunque inventarsi i più strani metodi per eseguire le operazioni più complicate: ma l’algoritmo per la radice quadrata inversa veloce ha battuto ogni record.

Per prima cosa, che significa “Radice quadrata inversa”? È l’operazione che da x ottiene x^−½, cioè l’inverso della radice quadrata di x. Naturalmente “veloce” significa che l’algoritmo usato è più veloce di quello standard, probabilmente legato all’iterazione con il metodo di Newton a partire da una approssimazione. La prima implementazione per la radice quadrata inversa veloce prevedeva una tabella precompilata di dati da cui partire e migliorare il risultato approssimato; ma anche lo spazio a disposizione non era poi troppo. L’algoritmo che secondo Wikipedia fu ideato alla Silicon Graphics non aveva invece bisogno di una tabella, ma solo di una costante magica: 0x5f3759df. Come funzionava questo algoritmo? Si prendeva il numero x (float a 32 bit), e si salvava la sua metà x2 = x/2 per dopo. Poi si prendeva x, lo si leggeva come se la successione di bit rappresentasse un intero, si faceva uno shift logico a sinistra di una posizione (il primo bit veniva buttato via, gli altri scalavano di una posizione a sinistra, e si metteva uno zero in fondo), si sottraeva questo numero dalla costante magica e si leggeva il risultato y come fosse un float. Seguiva un’iterazione dove y veniva ricalcolato come 1,5 − (x2 × y²). Tutto qua.

Ma come è stata trovata questa costante? Non ho avuto voglia di leggermi tutta questa tesina, lo ammetto :-) Tanto ormai le CPU calcolano in virgola mobile a una velocità incredibile…

Ultimo aggiornamento: 2026-06-10 13:00

No, niente sesso. Molto più banalmente, calcolate l’area della parte colorata di questo triangolo.

Come racconta Presh Talwalkar, l’area colorata è uguale all’area del triangolo grande, cioè 32,5 cm², meno quella del triangolo non colorato, che è 8 cm² (la sua altezza è 5−2 cm e la sua base 13−5 cm); in tutto dunque 24,5 cm². Ma possiamo anche calcolarla direttamente, come la somma delle aree dei due triangoli colorati: quello rosso ha area 20 cm², mentre quello verde ha area 5 cm². Totale: 25 cm². Dove abbiamo sbagliato i conti?? Da nessuna parte!

Il trucco è esattamente quello del quadretto mancante, che vedete qui a destra. In pratica, quello che sembra un triangolo non lo è perché le due linee diagonali hanno una pendenza leggermente diversa, ed è proprio quella diversità che porta ad avere una differenza di un quadretto se sovrapponessimo le due figure.

I lettori più interessati si saranno chiesti se è un caso che le misure che abbiamo nel problema sono dei numeri di Fibonacci. La risposta è ovviamente no, non è un caso; dati tre numeri di Fibonacci consecutivi $ F_{n-1}, F_n, F_{n+1} $ vale sempre la relazione $ (F_n)^2 = (F_{n-1})(F_{n+1}) \pm 1 $ , con i più e i meno che si alternano se $ n $ è pari o dispari.

Quando ho scritto Chiamatemi pi greco, ho mostrato una formula che permetteva di calcolare l’n-sima cifra esadecimale della nostra costante preferita senza dovere calcolare quelle precedenti. Terminavo scrivendo

Chissà, magari in futuro qualcuno troverà una formula simile in base 10… La cosa non è impossibile, e per qualche altra costante matematica una formula di quel tipo esiste davvero, ma almeno per il momento non pare che ci siano buone notizie su quel fronte.

Le bozze del libro mi sono arrivate il 28 gennaio 2022. Il giorno dopo Simon Plouffe, uno degli scopritori della formula che avevo citato, ha pubblicato un preprint dove ha mostrato una formula per trovare l’n-sima cifra decimale di π. Come indovino ho ancora qualche margine di miglioramento…

Potete vedere qui sotto (oltre che nella figura iniziale…) la formula in questione. Prima si definisce il numero

$ \pi_n = \left( \frac{2(-1)^{n+1}(2n)!}{2^{2n}B_{2n}(1-2^{-n})(1-3^{-n})(1-5^{-n})(1-7^{-n})} \right)^{1/(2n)} $

e poi si calcola l’n-sima cifra decimale di pi greco come

$ d_n = \textrm{int} ( 10 \textrm{ frac} (10^{n-1} \pi_{n-1})) $

dove int() e frac() calcolano rispettivamente la parte intera e frazionaria di un numero.

So che ve lo state chiedendo: i B_n sono i numeri di Bernoulli. Plouffe spiega che a partire dal decimo numero di Bernoulli l’approssimazione

$ \pi \approx \left( \frac{2n!}{B_n2^n} \right )^{1/n} $

per n pari è molto precisa. (Se n è dispari i numeri di Bernoulli tranne il primo valgono tutti zero, quindi non funzionano). Preso per esempio $ n = 1000 $, l’errore che si commette è minore di $ 2^{-1000} $. I prodotti che vedete a denominatore arrivano infine dall’approssimazione della zeta di Riemann, scritta come produttoria infinita usando la formula di Eulero. È noto (l’ha dimostrato Eulero) che $ \zeta(2n) $ è un multiplo razionale di $ \pi^{2n} $; sostituendo il valore e prendendo i primi quattro valori della produttoria si arriva al risultato mostrato in cima.

Tutto bello, in teoria: peccato che la formula richieda di computare i numeri di Bernoulli, e per farlo in genere si usano formule che partono da un’espressione con pi greco. Insomma questo risultato è carino, ma assolutamente inutile in pratica!

Nel 2013 Dan Piponi, attualmente capo matematico di Epic Games, postò questo tweet, come ((molto) difficile) problema del giorno: dimostrare che $ π^{π^{π^π}} $ non è un numero naturale. Chiunque sa un po’ di matematica sarebbe pronto a scommettere che non lo è. Chiunque sa abbastanza matematica sa che non riuscirà a scoprirlo nel corso della sua vita.
Come può essere possibile, vi chiederete? Basta calcolare alcune cifre decimali del risultato, e si vede subito se non sono nulle. Peccato che, come potete leggere in questo articolo di Scientific American, le cose non siano tanto semplici.

Innanzitutto è possibile che una catena di esponenziali di questo tipo dia effettivamente un risultato che è un numero naturale. Per esempio, $ ( \sqrt{2} ^ \sqrt{2})^{\sqrt{2}} = \sqrt{2} ^ {\sqrt{2} \times \sqrt{2}} = \sqrt{2} ^2 = 2$. In linea di principio insomma non ci sono problemi. Il guaio è che i numeri in gioco, anche se non sembra, sono enormi. Quanto vale quel numero? Secondo le regole della matematica, bisogna calcolarlo dall’alto verso il basso. Partiamo quindi con $ π^π \approx $ 36,46. Se eleviamo pi greco a questo numero, otteniamo circa 1.34… x 10¹⁸, un numero dell’ordine del trilione (in italiano) o quintilione (nell’uso anglosassone). E dobbiamo ancora elevare pi greco a questo valore! Il risultato finale ha quasi 10¹⁸ cifre: per dare un’idea, noi conosciamo solo poco più di 10¹⁴ cifre decimali di pi greco, quindi siamo ben lontani dal riuscire anche solo ad avvicinarsi al calcolo. Tre anni fa Matt Parker ha fatto un video dove stima che ci vorrebbe almeno il doppio di cifre decimali note solo per calcolare la prima cifra decimale di quel valore, con il rischio che non basti nemmeno… (Come dice Timothy Gowers, se la catena fosse di soli tre esponenziali ce la potremmo ancora fare). Ed essendo pi greco un numero con infinite cifre dopo la virgola, non possiamo nemmeno pensare a qualche trucco per trovare solo le ultime cifre, come potremmo per esempio fare per scoprire quali sono le ultime due cifre di 1000000!

Vabbè, c’è sempre la possibilità di mettere in campo le armi teoriche della matematica e dimostrarlo in modo non numerico. O no? No. In teoria dei numeri è facile fare congetture: esiste per esempio la congettura di Schanuel, di cui è già difficile da comprendere il testo, che tra le tante cose dimostrerebbe che $ π^{π^{π^π}} $ è trascendente e quindi non può essere un numero naturale. Solo che nessuno ha nemmeno idea di dove iniziare a partire per dimostrare la congettura… Insomma, possiamo magnà tranquilli, non dovrò aggiornare il post per dire che il problema è stato risolto.

Il premio Abel è stato inventato dai norvegesi perché non esiste un Nobel per la matematica: non è così conosciuto, ma ha lo stesso valore (anche monetario, se siete quelli per cui pecunia non olet).
Quest’anno è stato assegnato a Michel Talagrand. Che ha fatto di importante? Beh, da quanto ho capito io il suo campo di studi consiste nell’usare tecniche stocastiche (e quindi legate alla casualità) per ottenere stime su quanto una soluzione si avvicina all’ottimalità. Pensate ai problemi NP-completi, come quello del commesso viaggiatore: trovare il miglior percorso per coprire 100 città è proibitivo, per quanto i computer possano migliorare in futuro. Ma se genero un certo numero di tentativi e faccio la media della lunghezza dei percorsi, se so che questa media può dare un’idea del valore ottimo, a questo punto se trovo un percorso più lungo del 3% rispetto al valore ottimo mi posso accontentare. Lo so, a qualcuno di voi può sembrare un’eresia usare la matematica per ottenere un valore che si sa essere errato: ma ricordatevi che la matematica serve anche come aiuto per vivere nel mondo reale.

Termino con due aneddoti. Stefano Pisani racconta che Talagrand riuscì a formalizzare matematicamente un’intuizione fisica di Giorgio Parisi che “i matematici considererebbero una stregoneria”: non ho nessun dubbio su questa frase di Talagrand, sapendo come i fisici mettano sotto il tappeto qualunque cosa se il loro “senso fisico” dice che stanno facendo una cosa giusta. Se poi andate sul suo sito, oltre a trovare una sezione dove seguendo un’onorata tradizione matematica ha messo una taglia su alcuni problemi irrisolti, troverete la seguente frase:

If you are desperate to get my books and your library can’t afford them, try to type the words “library genesis” in a search engine. I disagree with piracy, but this site saved me many trips to the library, which unfortunately does not carry electronic versions of older books.

Come si fa a non amarlo?

(immagine ufficiale di Talagrand, Peter Badge, Typos1, dal sito del Premio Abel)

Ultimo aggiornamento: 2024-03-27 22:16

La scorsa settimana è stato annunciato un nuovo record di numero di cifre di pi greco. Bisogna dire che non c’è stato chissà quale miglioramento: da 100 trilioni (o 100.000 miliardi, se vogliamo usare la scala lunga) siamo passati a 105 trilioni. La cifra in posizione 100 trilioni è un 6, almeno secondo il gruppo di lavoro che ha superato il proprio precedente record. Il tutto in due mesi e mezzo di computazione.

La cosa più interessante è che a quanto sembra il collo di bottiglia non è tanto la CPU, anche se hanno comunque usato un sistema 128-core dual-processor con 1 tera e mezzo di DRAM (ma che girava Windows Server 2022…), quanto lo spazio per salvare i dati! I 36 moduli SSD della Solidigm possono contenere un petabyte di spazio… (inutile dire che quelli di Solidigm si sono subito fatti pubblicità!)

Per i curiosi, il calcolo è stato eseguito applicando l’algoritmo di Chudnovsky: se avete letto il mio Chiamatemi Pi Greco sapete che alla fine del millennio i fratelli Chudnovsky hanno implementato una delle mistiche formule di Ramanujan e generato alcuni record per mezzo di un computer “casalingo”, nel senso che era stato assemblato nelle varie stanze di casa loro.

(immagine di lxlalexlxl da OpenClipArt)

Ieri avevo mostrato una successione generata con regole molto semplici che tendeva al valore pi greco. Spero che i miei ventun lettori, o almeno quelli di loro che hanno una formazione matematica, abbiano capito che era uno scherzo. Le successioni delle due colonne sono di tipo Fibonacci, visto che ogni numero è la somma dei due precedenti. Questo significa che il rapporto tra due numeri successivi in ogni colonna tende al valore aureo φ; le due colonne sono successioni di Fibonacci, la seconda scalata di un fattore 5 e la prima scalata di un fattore 6 e senza i primi due termini. Ciò significa che il rapporto tra le due successioni tenderà a 6/5 φ² (il bello del rapporto aureo è anche questo!)

Come spiegato in Futility Closet, il gioco funziona perché vale l’approssimazione $ 1,2 \cdot \phi^2 \approx \pi $; inoltre mi sono limitato a mostrare cinque cifre decimali e soprattutto mi sono fermato all’undicesima riga; proseguendo si sarebbe arrivati a un valore pari a circa 3,141640787 che è esattamente il rapporto approssimato indicato sopra ed è legato alla costruzione delle due colonne.

(immagine da Magazine uBC fumetti)

Ultimo aggiornamento: 2024-03-14 07:00