 |
 |
 |
| Il ritorno di Euclide | ||||||||||||||||||||||||||||||||||||||||
| Avrete notato che nella pagina precedente, ho tralasciato
l'implementazione di alcune funzioni membro, inserendo un commento /*...*/
nei corpi. Questo perchè volevo fare una prima bozza della struttura
della classe, senza preoccuparmi troppo di alcuni dettagli. Dopo che avete
scelto un buon posto sul fiume (o al mare) e avete piazzato l'attrezzatura
da pesca (compreso l'attrezzo più importante di tutti, lo sgabello
per stare comodo :), e solo dopo, aprite la scatola dei vermi e cominciate
a pescare. Meglio rimandare quello che è difficile, fino a quando
non si ha la necessità di scriverlo, anche perchè in generale
potrebbe non essere chiaro esattamente quello che serve e si rischia di
lavorare su qualcosa che poi non potrà essere utilizzato così
com'è. Meglio pensare prima alla struttura generale più conveniente
del software e solo dopo occuparsi dei dettagli. In molti casi conviene
passare dal generale al particolare e non viceversa.
Ovviamenti queste sono solo consigli generali e ci sono delle eccezioni: ad es. si potrebbe decidere di sviluppare completamente prima dei componenti, perchè servono al testing di tutti gli altri. Il consiglio è comunque sempre di spezzare le difficoltà e non cercare mai di affrontarle tutte in una volta (ad es. tutte nello stesso giorno) e di pensare molto prima di mettersi a scrivere del codice. Spesso purtroppo quando si produce software commerciale si hanno dei tempi ristretti. Occorre allora molta esperienza per fare tutto bene e in fretta. Inoltre la documentazione ha molta importanza. Non sto parlando qui della documentazione dell'utente che può essere prodotta agevolmente alla fine, ma della documentazione per sè stessi, dei commenti. Uso riportare all'inizio di un file di programma o in un file di testo a parte, un elenco riassuntivo delle soluzioni software principali impiegate nel programma e dei loro vantaggi e svantaggi. In questo modo quando vado a rimette mano al prg. dopo molto tempo leggendo quelle note posso farmi una buona idea di come feci quella «cosa». E' arrivato il momento di aprire la scatola dei vermi. Come si fa la riduzione ai minimi termini? Questa operazione serve in tre punti (in ogni posto dove abbiamo messo il commento /*...*/). Quindi facciamo una funzione che fa la riduzione. Siccome per semplicità abbiamo deciso che la nostra classe fraction memorizzerà sempre lo stato in forma canonica (ossia la frazione in forma ridotta ai minimi termini), l'utente non avrà mai bisogno di chiamare esplicitamente questa funzione di riduzione, perciò essa sarà protetta all'interno della classe. Comunque questa funzione sarà chiamata molto dai metodi della classe, quindi sarà bene che la scriviamo in modo efficiente. Ne va dell'efficienza di tutti i calcoli che implementeremo sui numeri razionali! Avremmo potuto anche scegliere di ridurre la frazione ai minimi termini ogni volta che si accede al suo valore e non già in costruzione, ma questa mi sembra una soluzione innaturale e inefficiente. Inefficiente perchè ogni volta che si utilizza una frazione si deve controllare se è ridotta ai minimi termini, oppure si deve inserire una variabile membro di stato che lo dice, complicando inutilmente le cose. Da notare che l'utente della classe non sa se la riduzione avviene in fase di costruzione oppure in fase di utilizzazione. E nemmeno gli importa, così come per usare i float non occorre conoscerne la rappresentazione di macchina (anche se è un argomento molto interessante). Per ridurre ai minimi termini occorre calcolare il M.C.D. (Massimo Comun Divisore), ossia il massimo intero che divide esattamente sia numeratore che denominatore. Poi si divide sia il numeratore che il denominatore per questo MCD. Ho già affrontato questo problema in C. Ecco il programma da cui copierò: /* three different ways to compute MCD:
#define TEST typedef unsigned long ulong;
ulong MCD1(ulong N, ulong M)
if (M == 0)
ulong MCD2(ulong N, ulong M)
if (M > N)
ulong MCD3(ulong N, ulong M)
while (M != N)
/* see in how many ways a problem can be solved?
#ifdef TEST
int main()
readlong(n);
printmcd(1, n, m);
return 0;
Gli algoritmi possibili sono fondamentalmente due: quello delle divisioni ripetute (o meglio dei resti ripetuti) e quello delle differenze ripetute. Il primo fa meno iterazioni quando sono in gioco grossi numeri, perciò ho scelto questo. MCD1 e MCD2 sono due possibili versioni, tra cui ho scelto la prima che mi pare più compatta. Rinominiamo M con D (D per Denominatore) ed eccolo qui, direttamente dal passato (più di 2200 anni fa) e dal più grande matematico dell'antichità: long MCD(long N, long D)
if (D == 0)
Ma ci sono alcuni interrogativi. Primo dobbiamo fare il test D==0 o possiamo risparmiarcelo? Secondo: ho cambiato ulong con long, ma cosa succede se i numeri sono negativi? La prima questione ci fa ricordare che la nostra classe deve gestire in qualche modo l'errore di "divisione per zero" che si ha quando si tenta di creare una frazione con denominatore nullo. E' chiaro quindi che il costruttore fraction(long,long) e il metodo set_denom devono essere modificati per gestire questo caso. Le soluzioni sono tre:
Ho scritto la classe in modo che potete scegliere tra queste 3 alternative. Per approfondire questo dettaglio riferitevi al codice della seconda versione mostrato alla fine di questa pagina (per ora però consiglio di ignorarlo, più rilassante continuare a leggere, no?). A questo punto è immediato scrivere la funzione reduce, inglobando la funzione MCD vista prima: // precondition: _denom != 0
while ((R = N % D)) //
!= 0
if (D!=1) // optional test
Resta da chiarire cosa accade nel caso di numeri negativi. Dovete sapere che nel caso di numeri relativi (cioè interi anche negativi) la definizione di resto è controversa. In alcuni casi si definisce il resto della divisione tra due interi a e b di Z col vincolo che sia 0<=r<|b|, cioè che sia positivo e minore del valore assoluto (o modulo) di b. Altri invece preferiscono la definizione che impone che |r|<|b| ed r<=0. Per la prima definizione il resto è una quantita sempre positiva, mentre per la seconda è sempre negativa. In entrambi i casi viene garantito che |r|<|b|. Es.
1) secondo la prima definizione si ha: 13=(-4)*(-3) + 1 e il resto è
1
Lo standard C dice che per numeri negativi il segno del risultato di % dipende dalla macchina: se uno o entrambi gli operandi sono negativi, viene garantito soltanto che il valore assoluto del resto sia inferiore al valore assoluto del divisore, appunto solo che |r|<|b|, oltre che naturalmente che (a/b)*b+a%b=a ed entrambe sono vere con le due definizioni di sopra, come è facile verificare. Nota: per i numeri negativi osservate che non solo il segno del risultato di % dipende dalla macchina, ma anche la direzione di troncamento per /, come esemplifica il fatto che 13/(-4) può dare -3 o -4 a seconda della definizione adottata. Ecco cosa accade tentanto di calcolare l'MCD tra 13 e -4 secondo l'algoritmo precedente se % segue la prima definizione (il primo resto è 1, come già calcolato): R=1 N=13 D=-4
Con la seconda definizione: R=-3 N=13 D=-4
Anche in questo caso l'algoritmo è corretto, solo che scambia i segni sia di _num che di _denom. Questo è innocuo comunque: il valore della frazione resta lo stesso. Né la prima né la seconda definizione di % è comunque quella che si ha solitamente su macchine Intel. Questo perchè esistono altre definizioni ancora, e in generale (su qualsiasi macchina) sono garantite solo queste due proprietà della definizione (sia r=a%b):
#include <stdio.h> int main()
exit(0);
L'output su una macchina Intel (Pentium e vecchie) è: -10%3=-1
Secondo la prima definizione avremmo dovuto avere: -10%3=2 (infatti -10=-3*4+2)
Per quanto riguarda -3%10, se trovate difficile calcolarlo a mente scrivete il sistema 0<=r<10
questo si risolve per tentativi, ad es. provando tutti i possibili valori di r: -3=q*10+0; nessuna soluzione nell'insieme dei numeri relativi Z
(dove q è il quoziente e vengono considerati i resti da 0 a 9). Questa prima definizione è un po' strana, perchè ad es. -3/10 è uguale a -1 e non a zero, e difatti questo viene detto "quoziente modulo", per distinguerlo dall'usuale quoziente come operazione inversa del prodotto (stiamo parlando ovviamente della divisione intera in Z, ossia di una divisione "per difetto"), definito con la nota regola dei segni per una pura (ma comoda) convenzione. Ad es. il quoziente di -5/3 secondo la definizione di divisione intera è -1, secondo quella associata a questo modulo (cioè il quoziente modulo) è -2 (infatti -5=-2*3+1). Con la seconda definizione abbiamo invece: -10%3=-1 (infatti -10=-3*3-1)
Quindi la definizione adottata dalla Intel qual è? E' facile
capirlo guardando questa tabella che riassume tutti i calcoli fatti:
Qui non sono rappresentati tutti i casi possibili: manca il caso di numeri entrambi positivi, che però è noto: il resto è positivo e minore del divisore. Nel caso in cui almento un numero sia negativo si vede che la definizione della Intel coincide in parte con quella di modulo positivo e in parte con quella di modulo sempre negativo. La prima si ha nei casi in cui solo il denominatore è negativo. La definizione della Intel, essendo un misto delle due, soddisfa ancora quelle due proprietà definite nello standard del C. Dopo tutta questa analisi di varii tipi di funzioni modulo (ben 3 tipi ne abbiamo visto), ecco la dimostrazione che il nostro algoritmo di riduzione funziona correttamente. Iniziamo prima col dimostrare che termina, non va mai in loop infinito, qualunque sia la definizione di modulo. Scriviamo l'espressione dei valori assunti successivamente da R in funzione di N e D, "srotolando" le iterazioni del while: R=N%D
Notate poi che valgono ad ogni passo le seguenti catene di disuguaglianze strette, in virtù di quella proprietà |r|<|b|: |R|<|D|
Non cambiate pagina, non c'è niente di complicato: la dimostrazione consiste nel seguente ragionamento: |R| per definizione è sempre un numero intero (positivo). per le disuguaglianze di prima |R| ad ogni passo deve diventare sempre più piccolo e non può rimanere uguale (non c'è il <=, ma c'è un minore stretto). questo implica che |R| deve per forza diventare zero e il ciclo deve terminare. Infatti un numero intero che deve diventare in modulo sempre più piccolo ad un certo punto deve diventare zero e dopodichè non può più cambiare. Insomma è assicurato, per definizione di modulo che quel while termina, che ad un certo punto R diventa 0 e la condizione del while falsa. Il numero di quelle disuguaglianze vere deve essere per forza finito, qualunque sia R e la definizione di modulo che soddisfa quelle proprietà. Abbiamo solo dimostrato che in ogni caso e su ogni macchina l'algoritmo termina. Non abbiamo però ancora dimostrato completamente che l'algoritmo è corretto. Un algoritmo può terminare ma non essere corretto, nel senso che può non risolvere il problema assegnato. Si dice che la terminazione è condizione necessaria ma non sufficiente per la correttezza di un algoritmo, con ovvio significato. Quindi quello che facciamo adesso è una continuazione della dimostrazione predente, non un secondo passo. La dimostrazione infatti è unica: dobbiamo dimostrare che l'algoritmo di riduzione si comporta bene in tutti i casi. Dobbiamo dimostrare una cosa sola: la correttezza dell'algoritmo. La questione è molto sottile: come vedete, anche per scrivere una sola linea di codice occorre pensarci molto. In compenso però il codice scritto è breve ed efficiente. Adesso ripeteremo un ragionamento che fece Euclide più di 2200 anni fa. "Una macchina meravigliosa" direbbe forse Euclide se potesse vedere il calcolatore che state usando. Io dico: quali saranno le meraviglie del futuro? Non vivremo abbastanza per vederle. Ma una cosa è certa: il futuro sarà una continuazione del presente. Alcune cose del presente sopravviveranno e saranno ancora utili. Ad es. chi 2200 anni fa avrebbe scommesso che nel 2000 le galline sono ancora utili? Le galline sono utilissime e lo saranno ancora per molto credo. Infatti altrimenti chi farebbe le uova? :) In questo contesto ci è utile un teorema di Euclide, su cui l'algoritmo è basato, che afferma: se un numero è sottomultiplo contemporaneamente di due altri numeri, allora è sottomultiplo anche del dividendo e del resto della divisione di questi due numeri, con il resto diverso da 0. Prendete 3. 3 è sottomultiplo ad es. di 6 e 15. 15 diviso 6 fa 2 col resto di 3. 3 è sottomultiplo di 6 e di 3. Cosa accade se avessi fatto 6 diviso 15? Fa 0, con il resto di 6 e la proprietà è ancora valida per 15 e 6 (si sono solo scambiati!). Questa proprietà è un teorema. Potete affannarvi per ore a sperimentarne la validità, senza mai trovare due numeri che lo contraddicano, ma la sua validità deve essere provata in generale per poter affermare che è "vera". Ecco la dimostrazione: si prendono due numeri, diciamoli N e D. Per ipotesi ho che k è sottomultiplo di entrambi e quindi esistono altri due numeri interi, diciamoli q e s tali che: k*q=N
Calcolo poi R=N%D (si suppone che D sia non nullo). Per la prima proprietà del modulo ho che R è tale che: (N/D)*D+R=N dove / denota la divisione intera (quella col troncamento). Ho anche che |R|<|D|, ma non la utilizzeremo per dimostrare questo teorema. Quello che vogliamo dimostrare a partire dalle precedenti ipotesi e conseguenze è che esiste un intero t tale che R=k*t, che equivale a dire che k è anche multiplo di R. Dimostreremo questo per costruzione, mostrando come t dipende da q e da s che abbiamo messo in gioco prima. Basta semplicemente utilizzare la proprietà del modulo (N/D)*D+R=N, sostituendo in questa k*q al posto di N, k*s al posto di D: ((k*q)/(k*s))*k*s + R = k*q si ha (banale proprietà della divisione intera): (q/s)*k*s + R =k*q ricavando R e mettendo in evidenza k: R = k*(q-(q/s)*s) (q-(q/s)*s) è il t che cerchiamo. Teorema dimostrato! Dove abbiamo usato il fatto che il resto è diverso da zero? Da nessuna parte. Se il resto è zero, l'espressione di R di prima è giusta, perchè si ha che la divisione N/D, ovvero q/s, è esatta e t viene uguale a zero. Secondo la definizione usata di sottomultiplo, qualsiasi numero è sottomultiplo di 0, e i multipli di 0 sono tutti zero. Lo zero è un caso degenere spesso volutamente escluso dalla discussione. Cosa centra questa proprietà con l'algoritmo di prima? L'algoritmo si basa su questa proprietà. Se devo cercare il MCD tra N e D, devo cercare il massimo dei sottomultipli comuni di N e D. Ebbene se faccio N/D e consideremo il suo resto R=N%D, ho che un qualsiasi sottomultiplo comune a N e D è anche comune a R, in particolare comune a D e R e in particolare anche il massimo di questi sottomultipli gode di questa proprietà. Allora mi riduco a cercare il MCD tra D e R con la stessa tecnica (infatti l'algoritmo si dice del tipo "ricorsivo"). Nota bene che se all'inizio N<D quando si prende D e R in realtà si prendono i numeri in ordine scambiato, come abbiamo visto. Quando mi fermo? Quando R=0 per noi la proprietà non vale più (e non serve più): se N è divisibile per D, ovviamente è D il MCD tra N e D. R sarà sicuramente zero ad un certo punto? L'abbiamo dimostrato, usando l'altra proprietà del modulo. Abbiamo complessivamente usato le due proprietà del modulo assicurate dallo standard del C (e del C++). Abbiamo dimostrato che l'algoritmo (termina e che) produce in D il risultato voluto. Abbiamo dimostrato che l'algoritmo è corretto, qualunque sia la definizione del modulo adottata sulla macchina locale. Anche l'algoritmo di riduzione è corretto. In generale non si riesce a dimostrare con tecniche matematiche la correttezza di un algoritmo come abbiamo fatto qui. E' stato possibile perchè il problema era semplice. Eppure vedete quante energie ho sprecato su questo punto. La dimostrazione anche di questo problema semplice infatti è non banale. Per chi non è abituato a ragionare matematicamente è tutt'altro che banale. Immaginate come sia complessa per problemi più complessi. Umanamente impossibile. E nemmeno per una macchina. E' stato dimostrato matematicamente da Alan Turing che non esiste e non potrà presumibilmente mai esistere un algoritmo in grado di provare la correttezza in generale di ogni altro algoritmo. E nemmeno potete pensare di scrivere un algoritmo per provare la correttezza di un altro particolare algoritmo. In questo caso chi proverebbe la correttezza del primo? Avrete una catena infinita di algoritmi di cui provare la correttezza. Nemmeno potete pensare di scrivere un algoritmo in grado di provare la correttezza di un altro a "forza bruta", provandolo per tutti i casi d'input possibile, perchè potrebbe essere difficile generare i casi d'input o potrebbero essere molto numerosi che l'algoritmo anche se esistesse sarebbe impraticabile. E soprattutto l'algoritmo dovrebbe essere in grado di valutare se l'output dell'algoritmo di cui sta cercando di provare la correttezza è corretto. Ma come fa? Dovrebbe per forza conoscere tutti i casi possibili di ingresso e uscita corretti. Morale: all'atto pratico non c'è modo di provare manualmente la correttezza di algoritmi complicati; all'atto teorico non c'è modo di provare la correttezza di algoritmi con un algoritmo, cioè automaticamente. Ci si deve accontentare in questi casi del cosiddetto testing manuale, che non prova la correttezza, ma solo la correttezza di comportamento in un numero finito di casi possibili, scelti tra quelli più significativi. Ciò nonostante le tecniche matematiche anche se praticabili solo
su piccoli algoritmi, possono essere utili. Ne abbiamo appena visto un
esempio pratico provando la correttezza di reduce( ) su tutte le macchine.
Fatto questo non resta che chiamare reduce in fraction(long,long) e set_denom( ) dopo aver verificato che _denom sia diverso da zero, perchè reduce( ) non lo fa e chiamarla poi nel corpo di set_num( ). Ecco tutto il codice scritto finora. Notate il test in reduce( ) che assicura che i segni di _num e _denom non siano mai alterati. Almeno per ora abbiamo deciso di tenere i segni specificati in input. // frac.h
// choose from: ASSERT_YES (default), NOERROR_TRAP,
EXCEPTION
#include <iostream.h>
class fraction;
class fraction
public:
// constructors //
// accessors //
protected:
void ExceptionIfDenom0()
void reduce();
#endif
// frac.cc
// this algorithm doesn't alter _num and _denom
signs
while ((R = N % D)) // != 0
if (D!=1 && D!=-1)
ostream& operator<<(ostream&
os, const fraction& f)
istream& operator>>(istream& is, fraction&
f)
// test.cc //
#include <iostream.h>
int main()
{ fraction f(1,3); // pone f=1/3
{ fraction f(-6); // pone f=-6/1,
cioč -6
{ f=3; // crea fraction(3) e
lo assegna ad f
{ f=fraction(2,3); // f diventa
2/3
{ fraction f(20,30); // deve
essere memorizzato 2/3
{ fraction f(8,7);
f.set_num(4);
return 0;
// test2.cc //
int main()
cin >> f; cout << f << endl; exit(0);
Per poterlo testare ho subito aggiunto operator<<,>>. Queste due versioni sono corrette ma molto "grezze", le miglioreremo in seguito. Ad es. se _num=13 e _denom=-4, << stampa "13/-4". Brutto, molto meglio avere sempre il segno a numeratore: -13/4 o meglio ancora avere un formato di visualizzazione tipo: 13
ma di questi miglioramenti ci occuperemo dopo. |
|
|
|