martedì 31 maggio 2011

A volte i computer non ce la fanno — 2

Anche se noi pensiamo di utilizzare una calcolatrice con tanta memoria, o un computer che memorizza i numeri reali utilizzando molto spazio, potremmo sempre incappare in qualche problema.

Per esempio, consideriamo l'equazione seguente:

(x-1)(x-2)(x-3)…(x-19)(x-20) = 0.

Non è difficile capire che ha venti soluzioni, i numeri naturali da 1 a 20. Basta sostituirli per vedere che risulta sempre 0.

Se noi svolgiamo quelle 19 moltiplicazioni tra binomi, otteniamo questa espressione:

x20 - 210x19 + 20615x18 - 1256850x17 + 53327946x16 -
1672280820x15 + 40171771630x14 - 756111184500x13 +
11310276995381x12 - 135585182899530x11 + 1307535010540395x10 -
10142299865511450x9 + 63030812099294896x8 -
311333643161390640x7 + 1206647803780373360x6 -
3599979517947607200x5 + 8037811822645051776x4 -
12870931245150988800x3 + 13803759753640704000x2 -
8752948036761600000x + 2432902008176640000.

Un po' meno bella della precedente, ma è sempre lei.

Ora, supponiamo che un errore di approssimazione modifichi leggermente una delle cifre di questo lungo polinomio. Immaginiamo, ad esempio, che il computer che stiamo utilizzando abbia a disposizione 30 bit per memorizzare le cifre significative.

Diamo un'occhiata al coefficiente di x19, cioè -210; servono 8 bit per memorizzarlo, e ci rimangono così 22 bit per la parte decimale, che è tutta a zero.

Modifichiamo quel coefficiente di un'inezia: lo diminuiamo di 2-23, un numero molto piccolo. Ora è diventato uguale a circa -210.0000001192: ci aspettiamo che le soluzioni dell'equazione così perturbata non siano molto diverse da quelle dell'equazione iniziale. Il nostro computer con 30 cifre significative, in effetti, non è in grado di distinguere tra -210 e -210-2-23, perché questi due numeri sono diversi a partire dal trentunesimo bit. Per lui l'equazione perturbata e quella iniziale sono uguali.

Vediamo invece che succede: se nell'equazione perturbata sostituiamo 20 al posto di x, invece di ottenere 0 abbiamo la bellezza di −6.25×1017, un numero grandicello. Le venti soluzioni dell'equazione iniziale sono ora queste (approssimate alla quinta cifra dopo la virgola):

1.00000, 2.00000, 3.00000, 4.00000, 5.00000,
6.00001, 6.99970, 8.00727, 8.91725, 20.84691.

Se le contate, non sono venti, ma solo dieci! Le altre dieci spariscono (o diventano complesse coniugate, se ci mettiamo nei numeri complessi).

Dunque una piccola modifica in un coefficiente produce un errore gigantesco nelle soluzioni. E questo, per uno che si affida ai computer per risolvere le equazioni, è Male.

Si può pensare che sui polinomi non ci sia più nulla da scoprire, ma il comportamento imprevedibile di questo particolare polinomio è stato scoperto solo nel 1984, in un un articolo dal meraviglioso titolo The perfidious polynomial.

In cui Wilkinson, l'autore, scrive:

Speaking for myself I regard it as the most traumatic experience in my career as a numerical analyst.

lunedì 30 maggio 2011

A volte i computer non ce la fanno — 1

Spesso si pensa che i computer abbiano risolto tutti i nostri problemi di calcolo. Se i numeri sono troppo grandi, ci pensa lui (o la calcolatrice). Non è proprio così.

Ogni tanto faccio notare agli studenti che, quando calcolano 1/3 e poi rimoltiplicano il risultato per 3, ottengono come risultato 1 perché la calcolatrice sbaglia due volte.

Sbaglia una prima volta perché 1/3 dovrebbe dare, come risultato, 0 seguito da infinite cifre 3, mentre il display ne mostra solo un certo numero. Sbaglia una seconda volta perché se moltiplichiamo quel risultato per 3, il risultato dovrebbe essere uno 0 seguito da un certo numero di 9.

Qualche calcolatrice moderna potrebbe, in effetti, memorizzare le frazioni in modo esatto (almeno frazioni semplici come 1/3), ma lo stesso problema si presenta quando si digita 2, poi si fa la radice quadrata, e successivamente il quadrato. Il risultato non dovrebbe essere 2, a rigore.

Come mai allora otteniamo il risultato giusto? Si tratta di un trucco: la calcolatrice ha una memoria capace di memorizzare n cifre, ma ce ne fa vedere meno, diciamo n-3. Allora quando calcoliamo 1/3 il risultato è 0 seguito da n-1 cifre 3 (diciamo n-1 perché una di queste cifre è occupata dallo 0 iniziale, poi potrebbe non essere così, ma facciamo finta), ma il sistema approssima il risultato facendoci vedere solo n-4 cifre uguali a 3.

Quando rimoltiplichiamo per 3, il risultato sarebbe 0 seguito da n-1 cifre 9, che, approssimato a n-4 cifre, diventa 1. Due approssimazioni producono il risultato giusto.

Non funziona sempre, però.

sabato 28 maggio 2011

Doppio pendolo inverso

Un pendolo inverso l'avevo già visto, ma un doppio pendolo inverso ancora no. Eccolo qua.

(Via smoot)

martedì 24 maggio 2011

Game of Thrones

Se vi siete appassionati di Game of Thrones, non avete letto i libri, e volete ritrovarvi tra i mille personaggi, qua c'è un bel sito con una infografica riassuntiva per ogni episodio. Spoiler free.

Tiffany

A me piacciono i romanzi per ragazzi (almeno quelli intelligenti). Sarà perché ho tre figli, o per via della sindrome di Peter Pan, fatto sta che li leggo volentieri.

Bene, questa volta ho letto qualcosa di Terry Pratchett: si tratta del ciclo di Tiffany, di cui finora sono stati tradotti in italiano soltanto tre volumi.

More about L'intrepida Tiffany e i piccoli uomini liberi

Nel primo (L'intrepida Tiffany e i Piccoli Uomini Liberi, Oscar bestsellers, 9€) Tiffany è una bambina di nove anni che scopre pian piano di essere una strega, come sua nonna. Nel mondo di Terry Pratchett le streghe non sono proprio come noi ce le immaginiamo: non è detto che abbiano verruche sulla faccia, bitorzoli sul naso, rughe (anche se questo, a volte, aiuta). Non devono obbligatoriamente essere vecchie e brutte. Non sono cattive, ma sono lì per aiutare, o per lo meno per fare andare le cose come dovrebbero andare. E, soprattutto, non sanno assolutamente nulla della faccenda di ballare senza mutande nelle notti d'estate.

Le streghe vivono sulle montagne, e dalla solida roccia traggono il loro potere. Tiffany è un po' anomala, perché vive su colline di gesso, e il gesso non è una roccia molto stabile e solida. Eppure…

Fanno compagnia a Tiffany i piccoli ometti blu detti Nac Mac Feegle, fatine-maschio (ma ci sono anche le femmine) puzzolenti, sbevazzoni, dediti a risse, furti, schiamazzi. L'antitesi dei Puffi, in sostanza. Meravigliosi.

More about Un cappello pieno di stelle

Nel secondo (Un cappello pieno di stelle) Tiffany ha undici anni, e sta cominciando a prendere coscienza delle sue capacità. E il vero potere di una strega è capire gli altri, sapere quello che gli altri non sanno, e non usare la magia.

Nel descrivere le colline di Tiffany, chiamate Il Gesso, Terry Pratchett ha in mente una particolare zona dell'Inghilterra, i dintorni di Uffington. Leggete il libro per scoprire il perché.

More about La corona di ghiaccio


Nel terzo (La corona di ghiaccio, Mondadori, 17€) Tiffany ha tredici anni, è più consapevole dei suoi poteri, e comincia a rendersi conto dell'esistenza dell'altra metà del mondo. Ha bisogno di una guida e, perciò, frequenta altre streghe più anziane e, quindi, più esperte. E come non citare Nonnina Wheatherwax e Nonna Ogg, quando si parla di streghe anziane ed esperte?

Le storie sono un po' più lineari e con qualche livello di lettura in meno, rispetto a quelle per adulti di Pratchett, ma sono comunque gradevoli e per niente noiose. Anche per un adulto.

mercoledì 11 maggio 2011

Snumeratezza



Beata gioventù che non paga la benzina. Ben tre virgola tre chilometri.

venerdì 6 maggio 2011

Ormai sono passati 17 anni…

…e posso anche raccontarlo.

Ero un giovane e ingenuo insegnante alle prime armi, in una scuola che non specificherò. E incontro uno studente di quinta.

«Oh, prof, sa cos'è successo ieri?».

«No, cosa hai combinato?».

«Ma no, niente, ho salvato la scuola».

«Eh, sì, certo».

«Sì, eh. Ieri pomeriggio avevo lasciato qua il motorino, nel cortile. Allora ieri sera sono passato a riprenderlo, e ho visto che c'erano le porte aperte».

«Che porte?».

«Le porte della scuola! Non le avevano chiuse bene, si poteva entrare».

«E allora?».

«Eh, allora ho dato un'occhiata, era tutto buio, però non mi sembrava il caso di andare via così».

«E quindi?».

«E quindi ho telefonato al numero della sorveglianza. Sa che c'è un adesivo della sorveglianza sulla porta?».

«Sì».

«Ecco, li ho chiamati dicendo che ero davanti a scuola e qualcuno ha lasciato le porte aperte».

«E loro cos'hanno detto?».

«Mi hanno ringraziato, mi hanno chiesto se potevo aspettare un momento che sarebbero arrivati subito».

«Tu hai aspettato?».

«Eh, sì».

«Bé, bene, bravo».

«…».

«Cosa c'è?».

«Oh, prof, glielo devo dire».

«Ma cosa?».

«Senta, io ero lì, non c'era nessuno, tutto vuoto, tutto buio».

«E allora?».

«Oh, prof, io ho preso il motorino, l'ho acceso, e ho fatto qualche sgommata lungo tutto il corridoio. E quando mi ricapitava un'occasione così? Era bellissimo, ero sempre di traverso».

giovedì 5 maggio 2011

«è composta da cinque parole» è composta da cinque parole


def quina(s):
  quote='"'*3
  print s + '(' + quote + s + quote + ')'

quina("""def quina(s):
  quote='"'*3
  print s + '(' + quote + s + quote + ')'

quina""")


Questo programma (in python) definisce una funzione quina(s) tale che, se invocata, produce una stampa di s("""s"""). Poi chiama la funzione quina passandole il codice scritto fino a quel momento, cioè chiama quina("""codice scritto fino a quel momento""") che produce una stampa di codice scritto fino a quel momento quina("""codice scritto fino a quel momento"""). Che è il programma stesso…

(Ho trovato un nuovo blog da seguire)