lunedì 2 aprile 2018

Come fanno i computer a calcolare le radici quadrate? — Parte 1: calcolo manuale

“La risposta breve è: le calcolano come faremmo noi per calcolarle a mano”.

“Ah, certo, tutti calcolano radici a mano”.

“La mia professoressa delle medie mi insegnò a farlo, sai?”.

“Anche la mia, ma se devo dire che mi ricordo come si fa, direi una bugia”.

“Sì, il procedimento non è per niente intuitivo, soprattutto in una parte. Ma partiamo dall'inizio: la descrizione completa dell'algoritmo l'ha scritta .mau. un po' di tempo fa, ed è spiegata qua”.

“Oh, bene, bene, ora me la guardo. No, decisamente non mi ricordavo tutto. Anzi, posso dire che mi ricordavo solo che si dovevano raggruppare le cifre del numero a due a due”.

“Sì, quello è il punto di partenza. Vogliamo provare a calcolare una radice quadrata a mano, in modo da sottolineare i punti importanti del procedimento?”.

“Ok, andiamo”.

“Allora, proviamo a calcolare la radice di 7654. Scriviamo il numero raggruppando le cifre a due a due”.

“E quindi formiamo due gruppetti”.

“Sì, e scriviamo in questo modo il tutto:”.

76.54 | 
      |-------
      |

“Ok, ora che succede?”.

“Ora si prendono le prime due cifre e si dà per scontato che la radice del numero composto solo da quelle due cifre la sappiamo calcolare”.

“Io non so quanto valga esattamente la radice di 76, però”.

“Sei in buona compagnia: nessuno lo sa. Ma non ci serve una precisione infinita, perché lavoriamo solo sui numeri interi: per calcolare la radice di 76 ti serve soltanto conoscere le tabelline”.

“Ah, allora posso dire che 8 è troppo poco e 9 è troppo”.

“Approssimiamo per difetto”.

“Allora dico che la radice di 76 è 8”.

“Benissimo, il primo passo è fatto, scriviamo 8 come prima cifra”.

76.54 | 8
      |-------
      |

“Fin qua è stato facile”.

“Ora correggiamo l'errore: calcoliamo il vero quadrato di 8…”.

“Che è 64”.

“Lo scriviamo sotto al 76, e facciamo la differenza, in modo da trovare il resto”.

76.54 | 8
64    |-------
--    |
12    |


“Bene. Adesso? Non ricordo più come si va avanti”.

“Adesso c'è la parte magica del procedimento, ma prima di raccontarla vediamo quello che abbiamo fatto finora. In sostanza abbiamo capito che 76 = 82 + 12”.

“D'accordo”.

“Ma 76 è stato estratto dal numero 7654 prendendo le prime due cifre, e quindi quello che abbiamo fatto in realtà è stato capire che 7600 = 82 × 102 + 1200”.

“Va bene, hai moltiplicato tutto per cento”.

“Sì, in questo modo abbiamo calcolato la radice di 7600, con il suo resto. Però volevamo calcolare la radice di 7654, che è un po' più grande”.

“Ci basterà correggere il resto: 7654 = 82 × 102 + 1254”.

“Ah, certo, ma così il resto diventa un po' troppo grande: non possiamo fare di meglio?”.

“Non saprei. Cioè, immagino di sì, ma non so mica come”.

“Quell'80 è un po' troppo basso, se lo aumentiamo un pochino magari riusciamo a diminuire il resto”.

“Vero, se prendo ad esempio 81 mi viene che 7654 = 812 + 1093”.

“Va già meglio, ma hai scelto 81 a caso. Magari con 82 può andare meglio, o forse con 83, o chissà”.

“E come faccio?”.

“Prova a fare una stima: invece di usare 80, tu vuoi usare 80 + t”.

“E quanto vale t?”.

“Ancora non lo sai: è quello che vuoi stimare. Prova a scrivere 7654 come quadrato di 80 + t. Anzi, per maggiore generalità scrivi 8 × 10 + t”.

“Va bene: 7654 = (8 × 10 + t)2. E adesso?”.

“Adesso svolgi il quadrato di binomio, lasciando indicati tutti i calcoli”.

“Oh, vediamo: quadrato del primo termine, doppio prodotto, quadrato del secondo… Mi viene questa roba:”.

7654 = 802 + 2 × 8 × 10 × t + t2.

“Ottimo. 802 fa 6400, è un numero che avevi già calcolato nel primo passo dell'algoritmo del calcolo della radice quadrata. La parte interessante è quella che segue: 2 × 8 × 10 × t + t2”.

“Che deve dare il famoso 1254”.

“Proprio così. Scriviamolo per bene:”.

2 × 8 × 10 × t + t2 = 1254.

“Ok, e adesso?”.

“Raccogliendo a fattor comune t si ottiene”.

(2 × 8 × 10 + t) × t = 1254

“Bene, e questo mi aiuta a trovare t?”.

“Questo spiega il passaggio magico dell'algoritmo della radice quadrata. Ricordi che avevi trovato la prima cifra, 8?”.

“Sì, e l'avevo scritta in alto”.

“Bene. Adesso il procedimento dice: abbassa altre due cifre di 7654, e poi raddoppia le cifre che hai trovato provvisoriamente per la radice quadrata, scrivile sotto, in questo modo…”.

76.54 | 8
64    |-------
----- | 16
12.54 |


“E poi?”.

“E poi trasforma 16 in decine, e trova quella cifra t delle unità da aggiungere a 16 in modo da trovare un numero 16t tale che 16t × t sia il più vicino possibile a 1254, senza però superarlo”.

“Ma quando scrivi 16t non intendi 16 × t, vero?”.

“No, è per questo che ho sempre esplicitato il simbolo di moltiplicazione: in questo caso con 16t intendo un numero di tre cifre avente 1 come cifra delle centinaia, 6 come cifra delle decine, e t come cifra delle unità”.

“E come si fa a trovare quel numero?”.

“Lo spiega sempre .mau.: in sostanza si va per tentativi, facendo una stima grossolana per eccesso e poi scendendo. Avevamo trovato un resto parziale di 12, dopo aver scritto il primo 8”.

“Vero”.

“Ora, 12 sono diventate centinaia, e la cifra delle decine è diventata 5”.

“Sì, poi 4 è quella delle unità, in modo da ottenere 1254”.

“Tieni solo le prime 3, cioè 125”.

“Ok”.

“Adesso calcola 125 / 16”.

“Viene 7.8 e rotti”.

“Parti quindi da 8, e fai 168 × 8, scrivendolo nello spazio vuoto sotto a 8”.

“Così?”.

76.54 | 8
64    |---------------
----- | 168 × 8 = 1344
12.54 |


“Sì: come vedi 1344 è un numero maggiore di 1254”.

“Allora?”.

“Allora la stima t = 8 era troppo alta, abbassala di uno e ripeti il procedimento”.

76.54 | 8
64    |---------------
----- | 168 × 8 = 1344
12.54 | 167 × 7 = 1169


“Questo va bene, ora puoi scrivere 1169 sotto a 1254 e calcolare il resto giusto. E non dimenticare di aggiungere la cifra 7 al risultato della radice, in alto, di fianco all'8”.

“Ecco:”.

76.54 | 87
64    |---------------
----- | 168 × 8 = 1344
12.54 | 167 × 7 = 1169
11.69 |
----- |
   83 |

“Perfetto, fine del procedimento. La radice di 7654 è 87 con resto di 83”.

“Fammi capire meglio questa cosa del resto, che non l'avevo mai sentito associato alle radici quadrate”.

“Quello che abbiamo fatto è questo: dato m, numero intero positivo, lo abbiamo scritto così”.

m = s2 + r

“Ah, dove s è la radice quadrata approssimata per difetto”.

“E r è il resto, esatto. Nel nostro caso 7654 = 872 + 83”.

“Ho capito”.

“Il procedimento per fare il calcolo a mano è quello di fare i conti a pezzi, dando per scontato che riusciamo a calcolare a mente le radici dei numeri di due cifre”.

“Ok”.

“La cosa strana è che per poter andare avanti e aggiungere una cifra occorre inserire una strana moltiplicazione per 2, che non si sa bene da dove salti fuori”.

“Quando abbiamo preso l'8 appena scritto e lo abbiamo fatto diventare 16?”.

“Proprio così. La spiegazione di quella parte è che quella moltiplicazione per 2 corrisponde al famoso doppio prodotto che salta fuori nello sviluppo del quadrato del binomio”.

“Che roba”.

“E quindi la prossima cifra l'abbiamo cercata intorno all'approssimazione 125 diviso per il doppio prodotto, cioè 125 / 16”.

“Avremmo dovuto fare 1254 / 167”.

“Certo, ma quel 7 non lo conoscevamo ancora…”.

“Ah, già, è vero! E quindi abbiamo stimato 1254 / 16t facendo 125 / 16”.

“Sì, e poi abbiamo aggiustato il tiro”.

“E dici che i computer fanno la stessa cosa?”.

“Non so se tutti i computer facciano così, ma questo è l'algoritmo usato dalla libreria GMP: GNU multiple precision arithmetic library”.

“Dalla descrizione presente nell'introduzione, sembra il meglio che possiamo avere per fare calcoli”.

“Pare proprio di sì: precisione multipla, massima velocità. L'algoritmo usato dalla libreria è in realtà una generalizzazione di questo, ma si basa su questi identici concetti: prendo un numero arbitrariamente grande e lo spezzetto fino a che non so fare i calcoli”.

“A gruppi di 2 cifre?”.

“Non esattamente, ma lo vediamo in dettaglio la prossima volta. Per ora accontentiamoci di definire bene quello che vogliamo fare”.

“La radice quadrata, no?”.

“Certo, ma come definiamo per bene il resto? Quanto può essere grande al massimo?”.

“Ehm”.

“Vedi che occorre, prima di tutto, capire quello che vogliamo. Allora, dato un numero m, diciamo che s è la sua radice quadrata e r è il resto se valgono queste relazioni:”.

s2m = s2 + r < (s + 1)2

“Ok, credo di aver capito, il resto non deve essere così grande da farmi arrivare al quadrato successivo”.

“Esatto”.

martedì 13 marzo 2018

Insomma, pi greco

“Eccoci dunque al punto finale, la quadratura del cerchio”.

“Oh, bene”.

“Facciamo un riassunto di tutto quello che abbiamo detto finora”.

“Ottimo”.

“I numeri reali si dividono in due categorie: i numeri razionali, cioè le frazioni, e i numeri irrazionali”.

“Cioè tutti gli altri”.

“Esatto. Ora, anche gli irrazionali sono divisibili in due categorie: i numeri algebrici (di cui fanno parte anche i razionali) e i numeri trascendenti”.

“I numeri algebrici sono quelli che possono essere soluzioni di equazioni polinomiali, vero?”.

“Equazioni polinomiali a coefficienti interi, altrimenti tutti i numeri potrebbero essere soluzioni dell'equazione x = a, e fine della storia”.

“Giusto”.

“Invece i trascendenti non possono essere soluzioni di equazioni polinomiali a coefficienti interi”.

“E fin qua ci siamo”.

“Alcuni numeri algebrici, poi, sono costruibili”.

“Il che significa che sono costruibili con riga e compasso, vero?”.

“Sì. Con riga e compasso si possono costruire numeri che, a partire dall'unità, possono essere ottenuti con un numero finito di somme, sottrazioni, moltiplicazioni, divisioni, e estrazioni di radice quadrata”.

“E ora c'è pi greco”.

“Già. Il problema della quadratura del cerchio si traduce in questa domanda: usando solo riga e compasso è possibile costruire un quadrato avente la stessa area di un cerchio dato? Domanda che, in linguaggio aritmetico, diventa: pi greco è un numero costruibile?”.

“E la risposta è no”.

“La risposta è: pi greco è un numero trascendente, e quindi se non appartiene all'insieme dei numeri algebrici non può appartenere nemmeno all'insieme dei numeri costruibili, che è un sottoinsieme proprio degli algebrici. Ma la dimostrazione di questa affermazione è lunga e difficile”.

“Lo sospettavo”.

“Ricordi quando abbiamo dimostrato l'esistenza di un numero trascendente?”.

“Sì, abbiamo usato una proprietà dei trascendenti, se ben ricordo, che riguardava le approssimazioni che possiamo fare con le frazioni”.

“Esatto: il numero che abbiamo trovato può essere approssimato con frazioni del tipo m/n con precisione minore di 1/nk, per qualunque k”.

“Anche pi greco, quindi?”.

“Purtroppo no, per pi greco questo metodo non funziona. Bisogna generalizzarlo tanto”.

“Questo tanto mi inquieta”.

“Cominciamo con notare che π ed e, il numero di Nepero, sono strettamente legati”.

“Non sarà la solita storia della formula più bella della matematica?”.

“Eh, sì. Sappiamo che eiπ = −1”.

“Ok, e quindi?”.

“E quindi se riusciamo a dimostrare che ea, con a un qualunque numero algebrico, non può essere uguale a −1, siamo a posto”.

“Fammi capire”.

“Dato che sappiamo che eiπ è effettivamente uguale a −1, se riusciamo a dimostrare quel teorema possiamo concludere che iπ non è algebrico”.

“Quindi iπ è trascendente, ma come facciamo a togliere i?”.

“Beh, è facile, i è algebrico, perché è soluzione dell'equazione a coefficienti interi x+ 1=0, e quindi se il prodotto iπ è trascendente, significa che π deve esserlo”.

“Ah, ecco! Ottimo, quindi in effetti abbiamo spostato il problema dallo studio di pi greco allo studio della funzione esponenziale, vero?”.

“Proprio così. Ora, facciamo un passo più semplice di quello che vorremmo, giusto per capire come funzionano le cose: dimostriamo che e è irrazionale. Ci ricordiamo che per la funzione esponenziale esiste una serie di potenze che converge a essa”.

“Ed ecco che entra in campo l'analisi…”.

“Sì, una dimostrazione di teoria dei numeri fatta con l'analisi: bella roba. Ricordi quale serie di potenze converge all'esponenziale?”.

“Era una serie facile, mi pare 1 + x + x2/2! + x3/3! + …”.

“Esatto. Ora, supponiamo per assurdo che e sia razionale, cioè una frazione. Questo vuol dire che se moltiplico questa fantomatica frazione per un numero sufficientemente grande, ottengo un numero intero”.

“Certamente”.

“Allora calcolo n!e1, con n sufficientemente grande da fare in modo che il denominatore se ne vada. E uso proprio lo sviluppo in serie di ex”.

“Va bene, aspetta che provo a capire. Se prendo la serie dell'esponenziale vedo che si semplificano tanti denominatori”.

“Quanti?”.

“Beh, sicuramente quelli fino a xn/n!”.

“Giusto; e ricorda che abbiamo posto x = 1. Che succede dopo quel termine?”.

“Eh, mi sa che rimane una frazione: 1/(+ 1). Anzi, non solo una, poi c'è 1/(+ 1)(+ 2), e così via”.

“Esatto. E quindi n!e non può essere un intero”.

“E quindi e non può essere razionale! Molto bello”.

“E ora un altro passo di analisi: quello che abbiamo dimostrato non è che esiste soltanto un caso in cui, moltiplicando la frazione che dovrebbe essere uguale a e, si ottiene un assurdo. Di casi come quello che ne sono infiniti, basta prendere il moltiplicatore sempre più grande”.

“D'accordo”.

“Ogni volta che moltiplichiamo l'espansione in serie di e otteniamo una prima parte intera, e poi una coda composta da tante frazioni aventi il numeratore uguale a 1, e il denominatore che diventa sempre più grande.”.

“Immagino che il passo di analisi sia fare diventare infinitamente grande quel denominatore”.

“Immagini bene. Quello che abbiamo fatto, detto in altri termini, è questo: abbiamo trovato due successioni fn e gn tali che la differenza fnegn diventa sempre più piccola man mano che n diventa sempre più grande. Nel nostro caso, giusto per essere chiari, fn è uguale a n!, mentre gn è uguale a 1/(+ 1) + 1/(+ 1)(n + 2) + …”.

“Ok, ho capito”.

“Quindi questa è una tecnica per dimostrare che un numero è irrazionale: trovo due successioni con quelle proprietà, e sono a posto”.

“Bene”.

“Ora un altro passo: passiamo dalla dimostrazione di irrazionalità di e1 alla dimostrazione di irrazionalità di ea, con a razionale diverso da zero”.

“Procediamo sempre allo stesso modo, con quelle due successioni?”.

“Sì, ma ora dobbiamo farlo per il caso generale, dove l'esponente di e è variabile. E l'aiuto ci viene proprio dalle approssimazioni di Padé”.

“Oh”.

“Sì, dal fatto che ex può essere approssimata molto bene dal rapporto f(x)/g(x), eliminando il denominatore possiamo passare all'espressione g(x)ef(x), che diventa sempre più piccola all'aumentare del numero di termini con cui faccio l'approssimazione”.

“Mamma mia”.

“Uno studio super tecnico di come sono fatti i polinomi f(x) e g(x) porta alla dimostrazione dell'ultima affermazione”.

“Super tecnico?”.

“Sì, vengono espressi come funzioni integrali di altre funzioni, in modo da poter costruire delle disuguaglianze comode e utili”.

“Certo, comode e utili…”.

“L'analisi è la matematica delle disuguaglianze: tutto è stima”.

“Andiamo bene”.

“Ti faccio solo un esempio, giusto per darti un'idea del livello: l'approssimazione di Padé di ordine 8 per la funzione esponenziale è questa: ”.

(x8 − 72x7 + 2520x6 − 55440x5 + 831600x4 − 8648640x3 + 60540480x2 − 259459200x + 518918400) / (x8 + 72x7 + 2520x6 + 55440x5 + 831600x4 + 8648640x3 + 60540480x2 + 259459200x + 518918400)

“Argh”.

“Che corrisponde a questa bella formuletta:”.



“Orrore”.

“Dove f(x) è il denominatore della frazione enorme che ho scritto prima, e g(x) il numeratore”.

“Che roba. Ehi, però c'è un'esponenziale con esponente −x, come mai?”.

“L'abbiamo fatto solo per comodità, invece di avere l'esponenziale con esponente x che moltiplica g, abbiamo diviso tutto per ex per ottenere quell'integrale, che ci piace molto perché ha un fattoriale al denominatore. E quando nei denominatori ci sono di mezzo i fattoriali sappiamo che tutto diventa piccolo molto in fretta”.

“Già, il fattoriale diventa enorme molto in fretta”.

“E allora, se immaginiamo che π possa essere una frazione N/D, moltiplicandolo per D dovremmo ottenere un intero, e quindi anche l'espressione f(iDπ) − eiDπg(iDπ) sarà un intero, perché la formula più bella della matematica ci dice che eiπ è uguale a 1, mentre f(x) e g(x) sono polinomi”.

“Siii, e quindi?”.

“E quindi avremmo un intero positivo minore di un numero piccolo quanto vogliamo. Minore di 1, ad esempio”.

“Ma non esistono interi positivi minori di 1, no?”.

“Appunto: è assurdo. Quindi π non può essere una frazione”.

“Ah! Ecco la dimostrazione!”.

“Noi però vogliamo dimostrare che π è trascendente, non ci basta che sia irrazionale”.

“Oh, no, è vero! Per un attimo avevo avuto l'illusione di aver finito”.

“Eh, no. Questo era solo riscaldamento. La strada per dimostrare che π è trascendente segue, però, quella che abbiamo percorso adesso, con ulteriori complicazioni”.

“Capirai”.

“Per prima cosa, si prendono in considerazioni delle approssimazioni di Padé simultanee”.

“Ossignore”.

“Significa semplicemente che approssimano bene non solo in un punto, ma in tanti punti. In quell'integrale che ho scritto sopra, invece di avere una sola parentesi del tipo (x) ce ne saranno tante diverse”.

“Mah”.

“Avremo quindi polinomi f e g che non dipendono solo da una x, ma da tante x diverse”.

“Cioè avremo x1, x2, e così via?”.

“Esatto”.

“Ma tutto questo perché?”.

“Eh, prima non ne abbiamo avuto bisogno perché abbiamo supposto che π fosse una frazione, e ci è bastata una approssimazione di Padé normale”.

Normale”.

“Ora, invece, se vogliamo dimostrare che π è trascendente, l'assurdo dovrebbe partire dalla supposizione che π sia algebrico. E non tutti i numeri algebrici sono frazioni”.

“E allora come si fa?”.

“Se quei numeri algebrici li moltiplichiamo per opportuni altri numeri algebrici, però, diventano frazioni”.

“Uh, ma come? Fammi capire”.

“Prendi per esempio la radice di 2”.

“Ok”.

“Se la moltiplichi per radice di 2, ottieni 2, che è addirittura naturale”.

“Vabbé, così è facile”.

“Prendi allora l'espressione (3 − √2)”.

“Ok”.

“Se la moltiplichi per (3 + √2) ottieni 9 − 2 = 7”.

“Ah, vero. Funziona sempre questa cosa?”.

“Sì, per ogni numero algebrico esistono sempre altri numeri algebrici che, moltiplicati per il primo, mi danno un numero razionale. È legato al fatto che i numeri algebrici sono sempre soluzioni di polinomi con coefficienti interi: quindi dato il numero iniziale, prendo il polinomio di grado minimo di cui questo è soluzione. Questo avrà un certo numero di altre radici, e se le moltiplico tutte ottengo il termine noto di quel polinomio, che è un numero intero”.

“Forse ho capito, posso provare un esempio?”.

“Certo!”.

“Se prendo la radice cubica di 3, so che questa è soluzione di x3 − 3=0”.

“Giusto”.

“Quindi se prendo le tre soluzioni dell'equazione x3 − 3 = 0, e le moltiplico tra loro… cosa ottengo?”.

“Pensaci bene: se le tre soluzioni sono x1, x2 e x3, l'equazione x− 3 = 0 può anche essere scritta come (x1)(x2)(x3) = 0”.

“Vero”.

“E allora se svolgi tutto dove va a finire il prodotto x1x2x3?”.

“Ah! Nel termine noto, che è 3! Molto bene, funziona davvero”.

“E funziona anche con la somma: quanto fa x1 + x2 + x3?”.

“Vediamo, devo sempre prendere in considerazione quel prodotto di tre parentesi?”.

“Sì: dove salta fuori la somma delle tre soluzioni?”.

“Mi pare che si possa trovare nel coefficiente del termine di secondo grado: quando faccio tutti i possibili prodotti, posso raccogliere x2 e ottenere, come coefficiente, la somma x1 + x2 + x3”.

“Per essere più precisi, la somma cambiata di segno, ma non è molto importante. Il fatto importante è che la somma sia il coefficiente del termine di secondo grado, quindi ancora una volta un numero intero”.

“Ah, bene”.

“Dato che questi numeri che servono per avere somma e prodotto interi sono molto importanti in questo campo, i Veri Matematici hanno creato una definizione apposta per loro: si chiamano coniugati della radice del polinomio che abbiamo preso in considerazione”.

“Ok”.

“Ecco allora come funziona il giochino delle approssimazioni di Padé: vogliamo dimostrare che ea non può essere uguale a −1, qualunque sia a, algebrico. Si prendono allora tutti i coniugati di a, e si considerano i prodotti aventi come fattori (ea+ 1), in cui i termini ai sono, appunti, i coniugati”.

“Le cose si complicano”.

“Già. Poi si considerano le approssimazioni di Padé simultanee, cioè quelle approssimazioni che approssimano bene tutti i termini del tipo eb che saltano fuori svolgendo i prodotti appena fatti”.

“Oh, mamma”.

“Ancora una volta salta fuori un integrale con un bel fattoriale al denominatore”.

“E i fattoriali ci piacciono”.

“Esatto. Così risulta un numero naturale che può essere minore di 1”.

“E questo è impossibile”.

“Purché non sia zero…”.

“Santo cielo! Ma non c'è mai fine!”.

“La dimostrazione del fatto che quel numero che salta fuori non è zero ha bisogno delle congruenze, ma non mi azzardo a scrivere tutti i passaggi: ti dico solo che si riesce a vedere che comunque noi scegliamo un numero primo p quel numero è congruente a una certa espressione positiva modulo p. Se quindi prendiamo un numero primo p abbastanza grande, quel numero è positivo”.

“E dato che i numeri primi sono infiniti…”.

“Un numero primo abbastanza grande lo troviamo sempre, e qui la dimostrazione finisce davvero”.

“Gulp. Comincio a capire perché è una dimostrazione del 1882”.

“Eh, sì. Sviluppi in serie, formula di Eulero, integrali, approssimazioni, infinità dei numeri primi: contiene di tutto.”.

“Che fatica! Non oso pensare alla fatica che hanno fatto quelli che sono arrivati alla dimostrazione per primi”.

“Eh, erano bravi”.

lunedì 12 febbraio 2018

Padé, che approssimava bene

“Allora non ce la facciamo a capire se pi greco è trascendente o no? Con tutta la teoria che abbiamo visto…”.

“Eh, non basta”.

“Ma, scusa, avevi detto che se un numero è approssimabile da numeri razionali con errore più piccolo di qualunque potenza del denominatore, allora è trascendente”.

“Esatto”.

“Ma quindi?”.

“Non ho detto il viceversa. Non è mica vero che ogni trascendente è approssimabile come si vuole, purtroppo”.

“Ah”.

“Il numero di Liouville è stato costruito apposta per soddisfare quel teorema, ma pi greco è un'altra cosa. Diciamo che è più naturale del numero di Liouville, ammesso che questa affermazione abbia senso”.

“Ci sarebbe da discutere, infatti”.

“Fatto sta che non si può procedere con pi greco come abbiamo fatto con quel numero. Le cose diventano molto, molto più difficili”.

“Ahi, hai detto molto due volte”.

“Già. Invece di usare frazioni che approssimano, si usano polinomi che approssimano. E per fare vedere che pi greco è trascendente, serve l'analisi”.

“Derivate?”.

“Derivate e integrali, condite con il teorema di infinità dei numeri primi e compagnia bella, tra cui anche la formula più bella della matematica”.

“Uh”.

“Provo a darti un'idea di queste frazioni polinomiali che approssimano le funzioni”.

“Proviamo”.

“Hai presente l'idea che sta sotto alla formula di Taylor?”.

“Ehm”.

“Capirai. L'idea è questa: ogni funzione (che soddisfa determinate ipotesi ragionevoli, naturalmente), può essere approssimata bene quanto si vuole da un polinomio. Se vogliamo che l'approssimazione sia buona, il polinomio deve avere grado alto. Più alto è il grado, migliore è l'approssimazione”.

“Va bene, l'idea me la ricordavo”.

“Prendiamo per esempio la funzione y = ex, che ci servirà”.

“Ok”.

“Ecco un po' di polinomi approssimanti:”.

y = 1
y = 1 + x
y = 1 + x + x2/2
y = 1 + x + x2/2 + x3/6
y = 1 + x + x2/2 + x3/6 + x4/24

“Simpatici”.

“Te li metto anche in un disegno, eccoli qua. In rosso c'è la funzione y = ex, in verde le varie approssimazioni”.




“Non mi dirai che sono belle approssimazioni”.

“Capisco la tua obiezione: devi guardare vicino al punto (0,1). La retta orizzontale è la funzione costante uguale a 1, che approssima come può”.

“Una schifezza”.

“Sì. Poi però abbiamo una retta che approssima meglio, la tangente, e poi delle curve. Se osservi bene, vedi che andando verso destra approssimano sempre meglio la curva rossa”.

“Sì, capisco, ma a sinistra fanno pena”.

“E questo è il problema dei polinomi. La funzione esponenziale ha un asintoto orizzontale, ma i polinomi non ce l'hanno. O salgono sempre, o scendono sempre”.

“E quindi come si fa?”.

“Con queste approssimazioni, non facciamo molto. Ma Padé, che era un matematico francese, ha studiato approssimazioni con frazioni algebriche, cioè frazioni in cui sia il numeratore che il denominatore sono polinomi”.

“E queste approssimano meglio?”.

“Beh, con le frazioni puoi anche fare gli asintoti”.

“Ah”.

“Per esempio, la frazione che ha al numeratore 60 + 24x + 3x2 e al denominatore 60 − 36x + 9x2x3 ha questo grafico”.



“Ah, sembra identica, si vede sbordare un po' di rosso solo agli estremi”.

“Visto? Approssima molto meglio del singolo polinomio, anche se anche qua c'è un difetto”.

“Quale?”.

“Ti faccio vedere il grafico da un po' più lontano”.



“Ah, c'è una parte anche sotto!”.

“Già, non si può avere la perfezione, però questo tipo di approssimazione ci basta”.

“Ma cosa c'entra l'esponenziale con pi greco?”.

“C'entra, c'entra, colpa della formula più bella della matematica”.

martedì 9 gennaio 2018

Il numero di Liouville

“Insomma, come si fa a riconoscere se un numero è algebrico o trascendente?”.

“Prima di provare a rispondere, ecco un riassunto di quanto abbiamo detto finora:”.

Se x è un numero irrazionale, esistono infinite frazioni del tipo m/n, ridotte ai minimi termini, che approssimano x con un errore minore di 1/(√(5)×n2), e la radice di 5 è la più grande costante utilizzabile in questo denominatore.

“Ok, mi ricordo, e ricordo anche che se si prova a aumentare la costante √(5) non è più vero che esistono infinite frazioni con quella proprietà”.

“Bene. Se proviamo ad aumentare ulteriormente l'esponente al denominatore, succede che il teorema non è più vero in generale. Cioè: non è vero che per qualsiasi numero algebrico esistono infinite frazioni del tipo m/n che approssimano quel numero con un errore minore di 1/n3. Questa è una proprietà dei numeri algebrici: se consideriamo i numeri trascendenti, non possiamo più affermarla. Esistono numeri trascendenti che la rispettano, e invece altri numeri trascendenti che possono essere approssimati con infinite frazioni con un errore minore di 1/n3, o anche 1/n4, 1/n1000, eccetera”.

“Addirittura”.

“Sì, esiste una categoria di numeri che possono essere approssimati con un errore minore di 1/nk, per qualunque k ti possa venire in mente”.

“Ah”.

“Ti faccio un esempio, ma prima dobbiamo ricordarci cosa sia il fattoriale”.

“Me lo ricordo, il fattoriale di un numero n è il prodotto di tutti i numeri da 1 fino a n”.

“Sì. Puoi scrivere i fattoriali dei primi numeri?”.

“Ah, certo, eccoli: 1! = 1, 2! = 2, 3! = 6, 4! = 24, …”.

“Ok, fermati pure. Allora, costruiamo un numero decimale in cui le cifre siano 0 oppure 1”.

“Bene, come decidiamo quando mettere 0 e quando mettere 1?”.

“Mettiamo quasi sempre 0, mettiamo 1 solo nelle posizioni 1, 2, 6, 24, eccetera”.

“Nelle posizioni identificate dai fattoriali?”.

“Esattamente. Le prime cifre del numero sono queste:”.

0.1100010000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010…

“Capito. Cos'ha di speciale questo numero?”.

“Questo può essere approssimato bene quanto vuoi con frazioni del tipo m/n in cui l'errore è minore di 1/n elevato a qualunque esponente ti possa venire in mente”.

“Oh, quindi è impossibile che sia algebrico, no?”.

“Proprio così, nessun numero algebrico gode di quella proprietà”.

“E come faccio a approssimarlo così bene?”.

“Te lo spiego con un esempio. Scegli un esponente a cui elevare 1/n, non troppo grande altrimenti dobbiamo scrivere un'infinità di zeri”.

“Facciamo 4, allora. Tanto il teorema che mi hai raccontato dice che non posso superare 2, no?”.

“Esatto. Ok, prendiamo 4 allora. Consideriamo quindi le cifre dopo la virgola del nostro numero fino alla quarta cifra 1. Insomma, prendiamo questo numero razionale:”.

0.110001000000000000000001

“Bene”.

“A che frazione è uguale?”.

“Allora, il quarto 1 si trova in posizione 4!, cioè 24, quindi dovrebbe essere questa frazione: 110001000000000000000001/104!”.

“Giusto. Facciamo così: indichiamo con L l'intero numero, e con A questa approssimazione”.

“Va bene”.

“Calcoliamo quindi LA”.

“Ci sono un sacco di zeri, uhm. Abbiamo in pratica cancellato i primi quattro 1, tutto il resto è rimasto uguale”.

“Giusto. Ora ti scrivo una serie di stime per cercare di capire come sia fatto questa differenza LA, tu seguimi, ok?”.

“Proviamo”.

“Prima di tutto, LA è uguale a 1/105!+1/106!+1/107!+…”.

“Stai scrivendo tutti gli 1 che rimangono, insomma”.

“Esatto. Questo numero è certamente minore di 2/105!”.

“Uhm, d'accordo, hai sostituito la somma di tutte la frazioni da 1/106! in avanti con un altro termine 1/105!”.

“Sì. Ora, la frazione 2/105! è uguale a 2/105×4!”.

“Questo perché 5! è uguale a 5 moltiplicato 4!”.

“Certo. Possiamo anche scrivere che 2/105×4! è uguale a 2/10(4+1)×4!, cioè 2/[104×4!×104!]”.

“Mi pare che tu abbia usato una proprietà delle potenze”.

“Proprio così. Dato che 2/104! è certamente minore di 1, possiamo affermare che tutta la frazione è minore di 1/104×4!”.

“Sì, è chiaro”.

“Riassunto: LA < 1/104×4!”.

“E quindi?”.

“Ricordi chi è A?”.

“L'approssimazione di L che stiamo studiando, cioè 110001000000000000000001/104!”.

“E ricordi quello che vogliamo fare?”.

“Vogliamo mostrare che possiamo approssimare L con frazioni del tipo m/n con un errore minore di 1/n elevato all'esponente che voglio”.

“E tu hai scelto 4 come esponente”.

“Giusto”.

“Ebbene, abbiamo appena trovato una frazione del tipo m/n, dove m = 110001000000000000000001 e n = 104! che approssima A con un errore minore di 1/104×4!, cioè 1/n4”.

“Ah!”.

“E hai visto che l'esponente 4 l'hai scelto tu, potevi scegliere un qualunque numero naturale”.

“Esatto”.

“E quindi hai in realtà infinite frazioni che approssimano L con un errore minore di 1/n4, o minore di 1/n5, eccetera”.

“Bene! E quindi L non è un numero algebrico, ecco fatto”.

“E così abbiamo fatto vedere che esiste almeno un numero trascendente. Bello, eh?”.

“Bello, sì. E anche per pi greco si può fare lo stesso ragionamento?”.

“Eh, magari”.

domenica 10 dicembre 2017

Ma tu guarda questa radice di 5

“Ma quindi, questi numeri trascendenti possono essere approssimati con frazioni meglio di quanto si possa fare con i numeri algebrici?”.

“Eh, sì, se definiamo in maniera un po' rigorosa quel meglio”.

“Già, mi pareva che tutti i numeri irrazionali, sia quelli algebrici che quelli trascendenti, potessero essere approssimati bene quanto si vuole con le frazioni, no?”.

“Ed è così, infatti. Bisogna solo chiarire come sono fatte le frazioni. Se ricordi, ti ho mostrato un paio di tabelle in cui si riusciva a intuire che la radice quadrata di due poteva essere approssimata bene con frazioni sempre più precise, a patto di aumentare con regolarità il numero di cifre del numeratore e del denominatore”.

“Ricordo, e ricordo anche che, invece, per le frazioni che approssimano pi greco non c'è la stessa regolarità”.

“Proprio così. Ora cerchiamo di capire in cosa consiste questo diverso modo di comportarsi delle frazioni”.

“Ok, cominciamo”.

“Partiamo dal semplice: ogni numero irrazionale può essere approssimato da un numero intero con un errore di 1/2”.

“Ehh?”.

“Prendi pi greco: se lo approssimi con il numero 3 che errore commetti?”.

“Un errore pari a 0.141592654eccetera”.

“Minore di 1/2, cioè 0.5”.

“Ah, certo”.

“Stessa cosa per la radice di 2, no?”.

“Se la approssimo con 1 commetto un errore pari a 0.414213”.

“Quindi minore di 1/2”.

“Va bene, ho capito, prendo l'intero più vicino ed è fatta”.

“Esattamente, l'errore può essere per eccesso o per difetto, ma è comunque minore di 1/2”.

“Bene, ma un numero intero non è che sia questa gran approssimazione, eh”.

“Infatti, facciamo di meglio. Se vogliamo approssimare un numero irrazionale con una frazione del tipo m/n, allora possiamo farlo sempre con un errore minore di 1/(2n)”.

“Continua a essere nebuloso: credo di aver capito cosa vuoi dire, ma non saprei come dimostrarlo”.

“Riprendiamo l'esempio di prima, con la radice di 2. L'abbiamo approssimata con 1 che, volendo, è la frazione 1/1”.

“Vabbè. Mi pare di capire però che come denominatore si possa scegliere il numero che si vuole”.

“Esatto, scegline uno”.

“Boh, facciamo 42”.

“Bene, allora calcola il valore di 42 moltiplicato per la radice di 2”.

“Uhm, la calcolatrice dice 59.39697”.

“Quindi 59 è una approssimazione di quel numero a meno di un errore di 0.5, cioè 1/2”.

“Certo, l'abbiamo detto prima”.

“Perfetto: ora dividi tutto per 42 e ottieni l'approssimazione che volevi”.

“Come come?”.

“Se 59 approssima 42 moltiplicato per radice di 2 con un errore di 1/2, allora 59/42 approssima radice di 2 con un errore pari a 1/(2×42)”.

“Ah, ma era così semplice?”.

“Già. Giusto per la cronaca, 59/42 è uguale a 1.40476”.

“Funziona! E mi pare anche di aver capito la dimostrazione del teorema: se voglio avere una frazione che approssima con un errore minore di 1/(2n), allora mi basta moltiplicare il numero da approssimare per n e fare come abbiamo fatto adesso”.

“Esatto. Ora proviamo a fare di meglio”.

“Come?”.

“Possiamo approssimare con un errore minore di 1/(3n)? O 1/(4n)? 1/(5n)? Quanto possiamo diminuire l'errore?”.

“Ah, boh”.

“Qui le cose cominciano a complicarsi un po'”.

“Capirai”.

“Possiamo scegliere il coefficiente di n al denominatore grande quanto vogliamo, e cioè possiamo approssimare con un errore minore di 1/(3n), 1/(4n), 1/(1000n), ma non per tutti gli n che vogliamo. Si dimostra che almeno un n si trova, ma non tutti vanno bene, purché k sia maggiore o uguale di n”.

“Ah”.

“Ti faccio capire la dimostrazione come ho fatto prima, con un esempio. Prendiamo la radice di 3, e scegliamo = 8. Vogliamo far vedere che riusciamo a trovare un n tale che la frazione m/n è un'approssimazione di radice di 3 con un errore minore di 1/(8n)”.

“Ok”.

“Ti scrivo i numeri del tipo i per radice di 3, con i che va da 1 a 8:”.

1×√(3) =  1 + 0.732050807569
2×(3) =  3 + 0.464101615138
3×(3) =  5 + 0.196152422707
4×(3) =  6 + 0.928203230276
5×(3) =  8 + 0.660254037844
6×(3) = 10 + 0.392304845413
7×(3) = 12 + 0.124355652982
8×(3) = 13 + 0.856406460551


“Ok, e adesso?”.

“Adesso possiamo calcolare la parte decimale dei numeri elencati sopra in questo modo”.

1×(3)   1 = 0.732050807569
2×(3)   3 = 0.464101615138
3×(3)   5 = 0.196152422707
4×(3)   6 = 0.928203230276
5×(3)   8 = 0.660254037844
6×(3)  10 = 0.392304845413
7×(3)  12 = 0.124355652982
8×(3)  13 = 0.856406460551

“Ok, e, a costo di ripetermi, adesso?”.

“Ora immagina di prendere l'intervallo che va da 0 a 1 e di dividerlo in 8 parti. Una prima parte che va da 0 a 1/8, una seconda parte che va da 1/8 a 2/8, e così via, fino all'ultima parte che va da 7/8 a 8/8, cioè 1”.

“Va bene”.

“Ora inseriamo le otto parti decimali che abbiamo calcolato poco fa negli otto intervalli”.

“Ok, questo penso di saperlo fare: indico con Ik l'intervallo, con k che va da 1 a 8:”.

0.732050807569 I6
0.464101615138 I4
0.196152422707 I2
0.928203230276 I8
0.660254037844 I6
0.392304845413 I4
0.124355652982 I1
0.856406460551 I7

“Perfetto. Ora cerca quale di questi numeri si trova nel primo intervallo”.

“È 0.124355652982”.

“Che corrisponde a 7×√(3) − 12”.

“Già”.

“Quindi potremmo dire che 7×√(3) − 12 è approssimabile a 0 con un errore minore di 1/8”.

“Giusto, come abbiamo fatto prima”.

“E quindi, dividendo tutto per 7, √(3) − 12/7 è approssimabile a 0 con un errore minore di 1/(7×8)”.

“Ah, e quindi abbiamo trovato l'approssimazione che volevamo: √(3) è approssimabile dalla frazione 12/7 con un errore minore di 1/(7×8). Ma questo ha funzionato solo perché abbiamo trovato un numero nell'intervallo I1. E se non ci fosse nemmeno un numero in quell'intervallo?”.

“Ottima domanda. Se non cadesse nemmeno un numero nel primo intervallo, allora bisognerà che in uno dei restanti intervalli cadano almeno due numeri”.

“È un ragionamento che ho già sentito fare. Si chiama principio dei cassetti, vero?”.

“Ottimo! È proprio così: se hai 8 magliette da mettere in 7 cassetti, allora certamente almeno un cassetto dovrà contenere più di una maglietta”.

“Eh, sì, giusto. E adesso?”.

“Adesso per poter andare avanti non abbiamo nemmeno bisogno di fare un altro esempio: hai notato che anche nel nostro caso ci sono alcuni cassetti occupati due volte, vero?”.

“Sì: il quarto e il sesto”.

“Bene: considera i due occupanti nel cassetto 6, per esempio”.

“Ok. Che ci faccio?”.

“A che distanza sono?”.

“Devo fare il calcolo?”.

“No, non è necessario: stanno entrambi nello stesso intervallo, quindi quale sarà la loro distanza massima?”.

“Bé, al massimo saranno a distanza 1/8 uno dall'altro”.

“Esattamente. Uno dei due numeri è 5×√(3) − 8, e l'altro è invece √(3) − 1. Se calcoli la loro differenza…”.

“Ottengo 4×√(3) − 7”.

“Questo numero è approssimabile a 0 con un errore di 1/8, quindi dividendo tutto per 4…”.

“…ottengo un'approssimazione di √(3), cioè 7/4, con un errore di 1/(4×8)”.

“Ecco fatto, il teorema è dimostrato. Il caso generale è analogo a quello che abbiamo fatto adesso: se trovi una parte decimale che sta nel primo intervallo, sei a posto. Altrimenti vuol dire che uno degli altri intervalli conterrà almeno due parti decimali diverse”.

“E facendo la differenza, come abbiamo fatto adesso, arriviamo subito alla tesi del teorema”.

“Perfetto”.

“Quindi abbiamo finito?”.

“Certo che no. Possiamo migliorare ulteriormente la precisione delle nostre approssimazioni?”.

“E come sarebbe possibile? Abbiamo già preso in considerazione tutti i possibili multipli di n in quel denominatore!”.

“Chiediamoci allora se possiamo avere errori minori di 1/n2, o 1/n3, e così via”.

“Ah”.

“Ma non entro troppo nel tecnico: la risposta è che l'approssimazione con errore minore di 1/n2 si può sempre fare, ma non si può fare tanto di meglio”.

“Mi pare difficile da dimostrare, soprattutto per la parte di impossibilità”.

“Non è difficile, ma è un po' noioso. Bisogna annegare in un mare di disuguaglianze e stime, con poca soddisfazione”.

“Ah”.

“Quindi direi di fermarci qua, anche perché dobbiamo ancora vedere cosa rende i numeri algebrici diversi dai trascendenti”.

“Va bene”.

“Ti riassumo, quindi, quanto abbiamo detto finora, aggiungendo anche i teoremi che non abbiamo dimostrato:”.


  • Teorema 1: un qualsiasi numero irrazionale è approssimabile, con un errore minore di 1/2, da un unico numero intero.
  • Teorema 2: se x è un numero irrazionale e n un intero positivo, allora esiste una frazione m/n che approssima x con un errore minore di 1/(2n).
  • Teorema 3: se x è un numero irrazionale e k un intero positivo, allora esiste una frazione m/n il cui denominatore non supera k che approssima x con un errore minore di 1/(nk)
  • Teorema 4: se x è un numero irrazionale, esistono infinite frazioni del tipo m/n, ridotte ai minimi termini, che approssimano x con un errore minore di 1/n2.


“Benissimo”.

“Con qualche trucchetto le approssimazioni dei teoremi 3 e 4 possono essere migliorate un pochino, ma non entriamo troppo nel dettaglio. Una cosa interessante è invece questa:”.

  • Teorema 5: se x è un numero irrazionale, esistono infinite frazioni del tipo m/n, ridotte ai minimi termini, che approssimano x con un errore minore di 1/(√(5)×n2), e la radice di 5 è la più grande costante utilizzabile in questo denominatore.


“In che senso la più grande costante utilizzabile?”.

“Nel senso che se l'aumenti un po' il teorema diventa falso: non trovi più infinite frazioni con quella proprietà”.

“Ah. Ma questa radice di cinque compare nei posti più impensati”.

“Già”.

sabato 4 novembre 2017

Trascendenza

Qual è 'l geomètra che tutto s'affige
per misurar lo cerchio, e non ritrova,
pensando, quel principio ond'elli indige,

tal era io a quella vista nova:
veder voleva come si convenne
l'imago al cerchio e come vi s'indova;

ma non eran da ciò le proprie penne:
se non che la mia mente fu percossa
da un fulgore in che sua voglia venne.

“Uh, la Divina Commedia”.

“Già. La parte finale dell'ultimo canto del Paradiso, la fine del viaggio”.

“La visione di Dio, vero?”.

“Esatto. Dante arriva davanti a Dio, e cerca di comprendere il mistero della Trinità: gli appaiono tre cerchi, di uguale dimensione ma di colore diverso. Cerca di spiegare quello che ha visto, ma ammette il fatto che le sue parole non sono sufficienti per descrivere tutto. All'interno del secondo cerchio, poi, Dante scorge un'immagine umana”.

“Gesù”.

“Sì. Ed ecco che si affaccia alla sua mente un altro mistero: la coesistenza in un'unica persona della natura umana e di quella divina”.

“Questo è ancora meno comprensibile del precedente”.

“E infatti Dante fa un paragone molto particolare per descrivere l'incapacità della sua mente di comprendere questo mistero”.

“Mi pare che tu ne avessi già parlato”.

“Ah, bene, vedo che hai buona memoria! Sì, il paragone è quello dello studioso di geometria, che cerca di risolvere un problema molto difficile, quello della quadratura del cerchio”.

“A me questa cosa della quadratura del cerchio ha sempre fatto ridere. Mi immagino uno che a suon di martellate cerca di dare forma quadrata a una ruota”.

“Santo cielo. No, non si riferisce esattamente a questo il problema”.

“Lo sospettavo”.

“Ricorderai che i greci avevano delle regole molto precise per lo sviluppo della loro geometria”.

“Ricordo che volevano usare soltanto riga e compasso”.

“Esatto. Riga senza segni, compasso che si richiude dopo aver tracciato un cerchio. Insomma, una geometria senza numeri e poche regole di base”.

“I greci non erano normali”.

Ti ripeti, sai?”.

“Eh, pazienza. Ma quindi, possiamo usare un compasso ma non riusciamo a quadrare il cerchio. Cosa vuol puoi dire, quadrare il cerchio?”.

“Vuol dire costruire, utilizzando soltanto riga e compasso, un quadrato avente la stessa superficie di un cerchio dato”.

“Fammi capire, bisogna che provi con dei numeri”.

“L'area di un cerchio di raggio r è uguale a πr2”.

“Ok”.

“Quindi devi costruire un quadrato di lato r√π”.

“Bene”.

“Ora, r è solo un fattore di scala, prendila come unità di misura. Il problema è costruire, con riga e compasso, un segmento lungo √π”.

“Sì, giusto”.

“Se riesci a disegnare un segmento, riesci a disegnare anche la sua radice quadrata, e viceversa”.

“Ah sì?”.

“Sì, grazie ad esempio al secondo teorema di Euclide. Dato un triangolo rettangolo, il quadrato costruito sull'altezza relativa all'ipotenusa è equivalente al rettangolo che ha per dimensioni le due proiezioni dei cateti sull'ipotenusa”.

“Eh?”.

“Guarda questa figura:”.



“Ok”.

“Il quadrato di lato CD ha la stessa area del rettangolo di lati AC e CB”.

“Cioè x”.

“Esatto. E quindi se un quadrato ha area x, il suo lato sarà…”.

“Radice di x! Bene, ho capito”.

“Quindi costruire √π o costruire π è la stessa cosa: se sai costruire uno dei due sai costruire anche l'altro”.

“Va bene, quindi il problema della quadratura del cerchio si traduce nella costruzione di un segmento lungo pi greco”.

“Proprio così. Ora, con riga e compasso non si riesce a costruire proprio tutto quello che si vuole”.

“Ricordo”.

“Esiste una categoria di numeri costruibili”.

“Certo, esistono categorie per tutto”.

“Quella dei numeri costruibili contiene solo numeri che si possono ottenere a partire dai numeri razionali facendo un numero finito di somme, sottrazioni, moltiplicazioni, divisioni e radici quadrate”.

“Non si può fare di meglio, vero?”.

“No, il compasso ti permette di estrarre soltanto radici quadrate. Naturalmente puoi fare radici di radici, ottenere radici quarte, radici ottave, e così via. Non potrai mai ottenere radici cubiche, ad esempio”.

“E pi greco?”.

“Pi greco è stato un grossissimo problema”.

“Addirittura”.

“Eh sì. Abbiamo già raccontato un po' della sua storia: all'inizio non si sapeva nemmeno se fosse un numero razionale oppure no”.

“Ci aveva lavorato anche Archimede, vero?”.

“Giusto, lui ha studiato poligoni fino a 96 lati”.

Roba da matti”.

“C'è di peggio, Ludolph van Ceulen è arrivato a poligoni con 230 lati”.

“Santo cielo”.

“Ma nessuno, fino al 1761, è riuscito a scoprire se pi greco fosse razionale o irrazionale”.

“E che è successo nel 1761?”.

“Lambert, utilizzando concetti di analisi, arriva a dimostrare l'irrazionalità”.

“L'analisi?”.

“Sì, un teorema di teoria dei numeri dimostrato con l'analisi. Abbastanza inaudito: in teoria dei numeri si dimostrano cose molto complicate, eppure senza l'analisi non si riesce a studiare pi greco”.

“Che roba”.

“Eppure nemmeno questa dimostrazione era sufficiente per dimostrare l'impossibilità di quadrare il cerchio”.

“Ah, già, con riga e compasso si possono costruire numeri irrazionali, dato che si possono fare tutte le radici quadrate che si vuole”.

“Esatto. Bisogna dimostrare qualcosa di più”.

“E qualcuno c'è riuscito”.

“Sì, nel 1882 c'è riuscito Lindemann, dimostrando che pi greco è addirittura trascendente”.

“Trascendente?”.

“Sì. Significa che non può essere soluzione di nessuna equazione polinomiale a coefficienti interi”.

“Non capisco”.

“Allora, partiamo dall'inizio. I numeri naturali sono soluzioni di equazioni polinomiali di primo grado”.

“Continuo a non capire”.

“Per esempio, il numero 42”.

“E di quale equazione è soluzione?”.

x − 42 = 0”.

“Ah, ma certo”.

“Ma anche tutte le frazioni sono soluzioni di equazioni polinomiali di primo grado”.

“Mh, per esempio?”.

“Per esempio, 2/3 è soluzione dell'equazione 3x − 2 = 0”.

“Già, era ovvio anche questo”.

“Le radici quadrate sono invece soluzioni di equazioni di secondo grado. Per esempio, la radice di 2 è una delle soluzioni di x2 − 2 = 0”.

“Ok, sto capendo. Più aumenti il grado, più complicate sono le soluzioni”.

“Esatto. Esistono però alcuni numeri irrazionali che non possono essere soluzioni di nessuna equazione polinomiale, qualunque grado essa abbia”.

“Ma pensa. E pi greco è uno di questi numeri? Ce ne saranno pochi, suppongo”.

“Supponi male, in realtà i numeri irrazionali sono quasi tutti trascendenti”.

“Eh, ma com'è possibile?”.

“Beh, forse ricordi la differenza tra insieme infinito numerabile e insieme infinito non numerabile”.

Qualcosa ricordo”.

“In sostanza, l'infinito numerabile è quello dei numeri naturali. Puoi contare, metti un numero dopo l'altro, e via così. Anche i numeri interi e i numeri razionali sono un'infinità numerabile: si possono mettere in fila e li si possono contare, mettendoli in corrispondenza biunivoca con i numeri naturali”.

“I numeri reali invece no”.

“No, loro no, sono molti di più. Abbiamo dimostrato che è impossibile metterli in corrispondenza biunivoca con i numeri naturali”.

“E i numeri trascendenti?”.

“Allora, facciamo ordine. Tutti i numeri reali che non sono razionali si dicono irrazionali, ma questa divisione è ancora grossolana. I numeri costruibili con riga e compasso sono solo una parte degli irrazionali. Una piccola parte”.

“Piccola?”.

“Sì, sono ancora un'infinità numerabile. Ma addirittura tutti i numeri che sono soluzioni di equazioni polinomiali sono una piccola parte degli irrazionali”.

“Ma dai”.

“Sì, questi numeri si chiamano numeri algebrici”.

“Santo cielo, ma quante categorie ci sono?”.

“Eh, un po'. Ma lasciami spiegare perché i numeri algebrici sono pochi. Sai che un'equazione polinomiale ha, al massimo, tante soluzioni quanto è il suo grado”.

“Sì”.

“Quante equazioni polinomiali esistono?”.

“Infinite, naturalmente”.

“Certo, ma formano un'infinità numerabile o non numerabile?”.

“Non ne ho idea”.

“Beh, un'equazione polinomiale è identificata dai suoi coefficienti”.

“Sì, ci sarà un termine noto, un coefficiente del termine di primo grado, un coefficiente del termine di secondo grado, e così via”.

“Ottimo. Come vedi, stai contando i coefficienti”.

“Ah”.

“Li stai mettendo in corrispondenza biunivoca con i numeri naturali”.

“Già”.

“E quindi questi coefficienti costituiscono un'infinità numerabile. E allora anche tutte le equazioni polinomiali sono un'infinità numerabile, e così le loro soluzioni, che chiamiamo numeri algebrici”.

“Gulp”.

“Quindi i numeri irrazionali non algebrici, che vengono chiamati trascendenti, sono molti di più. Infinitamente di più”.

“Mamma mia. Comincio a pensare che la dimostrazione del fatto che pi greco è trascendente non sia proprio semplice semplice”.

“Pensi bene: se la dimostrazione è del 1882 significa che è difficile”.

“E non è che ora me la vuoi spiegare nel dettaglio, vero?”.

“No, è troppo difficile, bisogna mettersi d'impegno e studiarla in dettaglio. Col rischio di non capirne il senso, se non si cerca prima di avere un'idea di quello che si sta facendo. Bisogna capire, prima, qualche proprietà di questi numeri trascendenti, che non sappiamo nemmeno nominare”.

“In che senso?”.

“Beh, noi possiamo dare nomi solo a un'infinità numerabile di numeri”.

“Cosa?”.

“Esiste un numero finito di lettere dell'alfabeto. Con quelle puoi fare infinite parole, ma sono certamente un'infinità numerabile: puoi fare un gigantesco dizionario e mettere tutto in fila”.

“Come la biblioteca di Babele!”.

“Quasi. La biblioteca di Babele, pur enorme, contiene un numero finito di libri. Ogni libro ha 410 pagine, e pur considerando tutte le permutazioni di caratteri che esse possono contenere, si arriverà a un certo punto alla fine. Le parole che invece potremmo usare per definire i nostri numeri non hanno nessuna limitazione, e quindi potremmo costruirne un'infinità. Solo numerabile, però”.

“Quindi esistono numeri che non solo non potremo mai conoscere, ma che non potremo nemmeno chiamare per nome, come invece facciamo con pi greco?”.

“Ne esistono tantissimi, sì. Più delle parole che potremo mai inventare”.

“Mi gira la testa”.

“Capisco. Ma un po' ci vengono in aiuto le care frazioni: ogni numero irrazionale può essere approssimato, bene quanto si vuole, con delle frazioni”.

“Che è quello che facciamo in realtà quando facciamo calcoli con i numeri irrazionali, vero?”.

“Esatto: nessuna calcolatrice e nessun computer ha infinita memoria per poter contenere le infinite cifre di un numero irrazionale. Però i numeri algebrici e i numeri trascendenti si comportano in modi un po' diversi quando cerchiamo di approssimarli con le frazioni”.

“In che senso?”.

“Nel senso che i numeri algebrici possiamo approssimarli bene quanto vogliamo, ma non troppo”.

“Eh?”.

“Immagina di approssimare pi greco con delle frazioni: come puoi fare?”.

“Potrei scrivere 3/1, 31/10, 314/100, 3141/1000, e così via”.

“Giusto. Non è detto che questo sia il miglior modo di procedere, ma rende l'idea: se vuoi migliorare l'approssimazione, devi usare numeratori e denominatori sempre più grandi”.

“Certo, se voglio produrre più cifre decimali, mi sembra ovvio che devo aggiungere zeri al denominatore: è la notazione scientifica”.

“Ti sembra ovvio, ed è un bene, tieni presente però che la scelta di mettere al denominatore una potenza di 10 potrebbe non essere la scelta migliore. Si potrebbe fare meglio, insomma”.

“Ma cosa significa fare meglio di una approssimazione con un grado di precisione alto quanto vogliamo?”.

“Significa che, a parità di numero di cifre di numeratore e denominatore, esistono frazioni che approssimano pi greco meglio delle tue. Per esempio, Archimede, con i suoi poligoni di 96 lati, è arrivato a approssimare pi greco con le due frazioni 223/71 e 22/7, la prima per difetto e la seconda per eccesso”.

“Fammi fare i conti: 223/71 fa 3.1408 e 22/7 fa 3.1429. Le prime due cifre dopo la virgola sono esatte”.

“Mentre la tua frazione con due cifre al denominatore è 31/10 che approssima bene solo la prima cifra dopo la virgola”.

“Ah, ecco cosa intendevi. Io per approssimare bene anche la seconda cifra devo scrivere 314/100”.

“Pensa che con denominatori di tre cifre si possono approssimare bene le prime sei cifre dopo la virgola”.

“Cosa?”.

“Eh, sì. La frazione 355/113 è uguale a 3.14159204, le prime sei cifre dopo la virgola sono corrette”.

“Ma tu guarda. Bellina questa frazione”.

“Pensa che ha anche un nome: si chiama Milü, una parola cinese che significa più o meno frazione che approssima bene”.

“Eh eh, mi piace. Ma come mai cinese?”.

“Perché fu coniata dal matematico e astronomo cinese Zu Chongzhi nella seconda metà del quattrocento”.

“Ah, immagino quindi che abbia scoperto questa approssimazione più o meno quando l'hanno scoperta i matematici europei”.

“No, no, hai capito male. Parlo proprio del quattrocento, non del millequattrocento. Questo signore ha dato ai cinesi un'approssimazione straordinaria di pi greco mille anni prima che fosse conosciuta in Europa”.

“Gulp”.

“Quindi, per tornare alle buone approssimazioni dei numeri irrazionali: fissato un denominatore, come sono fatte le frazioni che meglio approssimano un numero irrazionale? Quanto bene si può approssimare un certo numero con una frazione che al denominatore ha due cifre? Tre cifre? n cifre?”.

“Ah, ecco cosa intendevi”.

“Già. Ecco una tabella delle migliori frazioni che approssimano pi greco, con, a fianco, l'errore”.

22/7            3.142857142857  0.00126448926735
355/113         3.141592920353  2.66764189405e-07
312689/99532    3.141592653618  2.91433543964e-11
146408/364913   3.141592653591  1.61071156413e-12
5419351/1725033 3.141592653589  2.22044604925e-14

“Ah, ecco 22/7 e 355/113. Come mai non hai elencato frazioni con quattro cifre al denominatore?”.

“Perché nessuna di loro approssima meglio pi greco di quanto non faccia 355/113.”.

“Ma tu guarda, non sapevo queste cose”.

“Ora ti mostro le migliori approssimazioni per radice di 2:”.

7/5             1.400000000000  0.0142135623731
99/70           1.414285714285  7.21519126192e-05
1393/985        1.414213197969  3.64403552e-07
8119/5741       1.414213551646  1.07270403671e-08
114243/80782    1.414213562427  5.41782174679e-11
665857/470832   1.414213562374  1.59472435257e-12
9369319/6625109 1.414213562373  8.21565038223e-15


“Compaiono denominatori di tutte le lunghezze, da 1 a 7”.

“Sì, anche se da un paio di esempi non si possono estrarre regole”.

“Ah, certo”.

“Però c'è qualcosa che si può dire, su queste approssimazioni”.

“Che cosa?”.

“Che i numeri algebrici rispettano certe regole, i trascendenti no”.

“Già, loro trascendono”.

lunedì 9 ottobre 2017

La quadratura del rettangolo babilonese, ovvero come verificare se un numero è un quadrato perfetto

Giocherellando sul Project Euler mi sono imbattuto in un problema interessante dal punto di vista della programmazione: come si verifica che un numero (naturale, naturalmente) è un quadrato perfetto?

Non sempre la cosa più ovvia funziona quando si ha a che fare con un computer. La prima idea che può venire in mente è: prendo il numero, faccio la radice, butto via i decimali, elevo al quadrato: se sono ritornato al numero di partenza vuol dire che quello era un quadrato perfetto. Ma i computer fanno fatica a lavorare con i numeri decimali, soprattutto se le cifre dopo la virgola sono tante. O, anche, se le cifre prima della virgola sono tante, perché di solito si usa un certo numero di bit per memorizzare un numero decimale: o c'è spazio per le cifre dopo la virgola, o c'è spazio per le cifre prima della virgola. La coperta è corta, e il rischio che le approssimazioni possano portare a fare errori c'è.

Per esempio, se chiedo alla calcolatrice del mio cellulare di calcolare la radice di 1026354952677384900, ottengo 1013091779.00. Quindi quel numerone è un quadrato perfetto? Cosa c'è dopo la virgola? Un ingegnere direbbe:

“Ma cosa ti importa della terza cifra dopo la virgola di numero di 19 cifre? La NASA usa 15 cifre decimali per pi greco, e ci manda foto da Plutone. Tu cosa devi farci con quel numero?”.

E avrebbe anche ragione. Quel numero è sufficientemente quadrato per quasi tutti gli scopi pratici che mi possono venire in mente, ma in realtà non è davvero un quadrato: 1013091779= 1026354952677384841 e, quindi, esiste almeno un'applicazione pratica che non funzionerebbe: non sarei in grado di rispondere correttamente a un quesito del Project Euler.

Come si può risolvere, allora, questo problema?

Esiste un metodo veloce per calcolare le radici quadrate, che risale ai babilonesi, e che può essere visto come caso particolare di un metodo che usa idee matematiche più avanzate e che si chiama metodo di Newton (esistono metodi ancora più veloci da implementare su un computer, che è in grado di fare le moltiplicazioni più velocemente di quanto non riesca a fare le divisioni, ma pazienza).

Funziona così.

Abbiamo un numero, per esempio 81, e vogliamo calcolarne la radice quadrata. Cioè vogliamo conoscere il lato di un quadrato di area 81. Detto in altri termini, tra tutti i rettangoli aventi area 81 vogliamo trovare quello che ha due lati uguali.

Allora consideriamo uno di questi rettangoli. Supponiamo di essere scarsi come un computer e di non riuscire a indovinare il rettangolo giusto, e quindi partiamo stupidamente dal rettangolo di dimensioni 1×81.

Ora l'idea geniale dei babilonesi: prendiamo i due lati e facciamone la media, ottenendo (1 + 81)/2 = 41. Questo numero sta dentro all'intervallo che va da 1 a 81 e, quindi, può essere usato come nuovo lato di un rettangolo che ha area 81 ma che è meno rettangolo di quello di prima (il nostro amico ingegnere, che nel frattempo sta decodificando un segnale proveniente dalla Voyager 1, sta sorridendo).

Quale sarà l'altezza di questo nuovo rettangolo che possiede meno rettangolicità del precedente? Basta fare la divisione 81/41 = 1.976. Ora abbiamo un rettangolo di dimensioni 41 × 1.976, che vorremmo fare diventare ancora meno rettangolo: possiamo ripetere il procedimento di prima.

Calcoliamo la media tra questi due numeri: (41 + 1.976)/2 = 21.488, ed ecco un nuovo lato ancora più corto. La nuova altezza sarà 41/21.488 = 1.908, e andiamo avanti così. Il procedimento dovrebbe essere chiaro: facendo la media tra base e altezza, ogni volta accorciamo un po' il lato lungo del rettangolo e allunghiamo quello corto, approssimando sempre di più la nostra figura a un quadrato. Quando abbiamo raggiunto abbastanza decimali ci fermiamo, e quella è la radice quadrata.

“Ma questo non risolve il tuo problema da matematico! Anzi, se tu avessi studiato le tabelline sapresti che 81 è un quadrato perfetto, mentre questo metodo trova sempre approssimazioni più precise, ma non è detto che finisca mai esattamente sul 9”, direbbe il nostro amico ingegnere, dopo aver fatto atterrare una sonda su una cometa.

E avrebbe ancora ragione, ma questa era solo un'introduzione al metodo che serve per verificare se un numero è un quadrato perfetto. L'idea, ora, è quella di usare solo numeri interi, e costruire rettangoli con lati interi che meglio approssimano un quadrato. E poi vedere che succede: o arrivo a un quadrato vero, oppure non ci riesco.

Vediamo l'esempio dell'81.


  • Parto da un rettangolo 1×81.
  • Faccio la media dei lati: (1 + 81)/2 = 41.
  • Calcolo la nuova altezza, buttando via eventuali decimali: 81/41 = 1.
  • Il rettangolo 1×41 è un quadrato? No. Continuo.
  • Faccio la media dei lati: (1 + 41)/2 = 21.
  • Calcolo la nuova altezza, buttando via eventuali decimali: 81/21 = 3.
  • Il rettangolo 3×21 è un quadrato? No. Continuo.
  • Faccio la media dei lati: (3 + 21)/2 = 12.
  • Calcolo la nuova altezza, buttando via eventuali decimali: 81/12 = 6.
  • Il rettangolo 6×12 è un quadrato? No. Continuo.
  • Faccio la media dei lati: (6 + 12)/2 = 9.
  • Calcolo la nuova altezza, buttando via eventuali decimali: 81/9 = 9.
  • Il rettangolo 9×9 è un quadrato? Sì. Fine.


Funziona.

Cosa succede nel caso in cui, invece, il numero non sia un quadrato?
Ripetiamo il procedimento applicandolo a 80.


  • Rettangolo 1×80.
  • Media dei lati: (1 + 80)/2 = 40.
  • Nuova altezza: 80/40 = 2.
  • Rettangolo 2×40.
  • Media dei lati (2 + 40)/2 = 21.
  • Nuova altezza: 80/21 = 3.
  • Rettangolo 3×21.
  • Media dei lati: (3 + 21)/2 = 12.
  • Nuova altezza: 80/12 = 6.
  • Rettangolo 6×12.
  • Media dei lati (6 + 12)/2 = 9.
  • Nuova altezza: 80/9 = 8.
  • Rettangolo 8×9.
  • Media dei lati (8 + 9)/2 = 8.
  • Nuova altezza: 80/8 = 10.
  • Rettangolo 10×8.
  • Media dei lati (8 + 10)/2 = 9.
  • Nuova altezza: 80/9 = 8.
  • Rettangolo 8×9.

Ehi, ma questo rettangolo l'ho già visto: la forma del rettangolo non si stabilizza verso un quadrato. 80 non è un quadrato perfetto.

Quindi il metodo funziona in questo modo: o arrivo a un quadrato perfetto, o arrivo a un rettangolo che ho già incontrato prima, e quindi mi fermo. Fatto.

Ed ecco un pezzetto di codice in python:



Grazie a stackoverflow e a Alex Martelli, che già sapeva cose ai tempi di Fidonet.