Calcolatrici! - Massimo Comun Divisore

Il Massimo Comun Divisore (MCD) è il maggiore intero positivo che divide due numeri senza resto. Se prendete i due termini di una frazione e li dividete per il massimo comun divisore ottenete la frazione semplificata.

Personalmente nel fare conti, anche semplici, ero una vera frana e quindi, appena ho imparato a programmare, ho subito pensato al problema di semplificare le frazioni. Ho quindi inventato il mio primo algoritmo serio proprio per calcolare l'MCD. Peccato che qualche mese dopo io abbia scoperto che un certo Euclide mi aveva preceduto!

Comunque il programma che semplifica una frazione utilizzando un sottoprogramma per il calcolo dell'MCD per anni è stato molto usato sulle mie HP 34C e HP 32S. Era diventato un po' il mio metro di valutazione della bontà delle calcolatrici. In effetti utilizza subroutine, loop, istruzioni condizionali, registri di memoria, stack (se esiste) e semplici funzioni di calcolo. Era un benchmark sulle funzionalità abbastanza completo. E in effetti nel corso del tempo ho prodotto implementazioni per altre calcolatrici. Oggi non ha più molto senso perché quasi tutte le calcolatrici hanno funzioni di calcolo per le frazioni. Nel frattempo, grazie all'uso assiduo di queste macchinette, ho anche imparato a fare i conti.

Per la mia HP 34C il programma era più o meno questo (ho scritto alcune varianti nel corso del tempo):

Subroutine A (routine di semplificazione)	Subroutine 9 (routine di calcolo del MCD)
`LBL A STO 1 x↔y STO 0 GSB 9 RCL 2 STO ÷ 0 STO ÷ 1 RCL 0 PSE RCL 1 RTN`	`LBL 9 RCL 1 ABS RCL 0 ABS x>y x↔y STO 2 R↓ STO 3 LBL 8 RCL 3 x=0 RTN RCL 2 RCL 2 RCL 3 ÷ INT RCL 3 STO 2 × - STO 3 GTO 8`

Per usarlo si inserivano i numeratore e denominatore nello stack (catasta nel manuale in italiano) e si premeva il tasto A. Dopo qualche tempo compariva il nuovo numeratore e dopo una pausa il denominatore. Nel registro 2 si trovava il massimo comun divisore.

Comprata la HP 32S l'ho riscritto:

Subroutine S (routine di semplificazione)	Subroutine M (routine di calcolo del MCD)
`LBL S INPUT N INPUT D XEQ M RCL Z STO ÷ N STO ÷ D VIEW N VIEW D RTN`	`LBL M RCL N ABS RCL D ABS x<y? x↔y STO Z R↓ STO W LBL V RCL W x=0? RTN RCL Z RCL Z RCL ÷ W IP RCL W STO Z × - STO W GTO V`

Come si può notare il programma è molto simile. In effetti è il motivo fondamentale per cui ho acquistato la HP 32S: un grande livello di compatibilità con la vecchia calcolatrice. In questo caso ho sfruttato le variabili. Si premono i tasti XEQ S e il sistema chiede il numeratore (variabile N) e il denominatore (variabile D). Dopo qualche tempo vengono visualizzati il numeratore e il denominatore semplificati.

Rimanendo nel mondo HP, si può pensare ad una calcolatrice come la HP 50g e a come si può utilizzare il linguaggio RPL per realizzare lo stesso algoritmo. Ho utilizzato la solita struttura: un programma che mostra una semplice interfaccia utente che chiede i due termini della frazione e che semplifica la frazione utilizzando un programma che calcola l'MCD.

Semplifica (programma per la semplificazione)	MCD (programma di calcolo del MCD)
`« "Semplificazione" { "Numeratore" "Numeratore della frazione" 0 } { "Denominatore" "Denominatore della frazione" 0 } } 1 { } { } INFORM IF 0 ‹ THEN OBJ→ DROP 0 → n d m « n d MCD 'm' STO n m / "Numeratore" →TAG d m / "Denominatore" →TAG » END » 'Semplifica' STO`	`« ABS SWAP ABS DUP2 MIN SWAP ROT MAX → w z « WHILE w ≠ 0 REPEAT z DUP w / IP w DUP 'z' STO * - 'w' STO END z » » 'MCD' STO`

Ecco come appare il programma:

Si potrebbe ottimizzare ma con la HP 50g questo algoritmo è assolutamente inutile: la calcolatrice esegue calcoli frazionari. E ha incorporata una funzione per calcolare il massimo comun divisore. In effetti va più oltre grazie al CAS incorporato. Se ad esempio scrivete una cosa del tipo:

'(45*(x^2-a))/(15*(x^6-12*x^4+48*x^2 -64)' 'a=4' SUBST FACTOR

otterrete

'3/((x+2)^2*(x-2)^2'

Da notare che, nonostante la calcolatrice possa essere usata anche in modo algebrico, io ovviamente uso il modo RPN. Inoltre la calcolatrice utilizza una rappresentazione più vicina a quella che utilizzereste con la carta e quella che ho usato io è la rappresentazione testuale usata internamente dai programmi. Una serie di immagini rendono ancora di più l'idea:

Un bel salto dalla vecchia HP 34C!

Con la HP Prime si utilizza invece il linguaggio HP-PPL, una sorta di linguaggio strutturato che ricorda il BASIC o il PASCAL.

Nell'HP Prime l'RPN è un mondo abbastanza separato dal CAS e dall'HP-PPL. Quindi per restituire parametri multipli da un programma si può utilizzare una lista, vista la difficoltà di accedere allo stack RPN. In questo caso ho utilizzato la lista predefinita L0 che ho richiamato poi dalla schermata principale della calcolatrice (qui in modalità TextBook).

I vari sistemi CAS permettono di definire funzioni. In questo somigliano a linguaggi funzionali come LISP o F#. E quindi possibile sfruttare queste caratteristiche per scrivere un programma per l'MCD funzionale. Tenendo presente che i loop si sostituiscono con l'uso di funzioni ricorsive e che queste si possono combinare ho definito alcune funzioni per il CAS di HP Prime in grado di effettuare il calcolo dell'MCD:

Per usare questo codice basta chiamare la funzione mgcd passando i due valori. Le funzioni possono essere adattate facilmente ad altri CAS. Nel caso dell'HP Prime si può utilizzare anche la sintassi nativa:

Funzione SEMPLIFICA (interfaccia utente)	Funzione MCD (calcolo del MCD)
`EXPORT SEMPLIFICA() BEGIN LOCAL n,d,m; INPUT({n,d},"Semplificazione", {"Numeratore","Denominatore"}); m:=MCD(n,d); n:=n/m; d:=d/m; L0:={}; L0(1):=n; L0(2):=d; RETURN "Risultato: "+n+"/"+d; END;`	`// calcola il massimo comun divisore // tra due numeri EXPORT MCD(n,d) BEGIN LOCAL z,w,t; z:=MAX(ABS(n),ABS(d)); w:=MIN(ABS(n),ABS(d)); WHILE w≠0 DO t:=z; z:=w; w:=t-w*IP(t/w); END; RETURN z; END;`