MateNatale 4a, alberi palline e pacchi

Risparmiare effettuando il minor numero di operazioni. Un problema che vale la pena di porsi, affrontabile anche da chi è alle prime armi!
aula di matematica
Dato x, xn  è per definizione: x·x·x……·x , n fattori tutti uguali ad x.
Calcolare x4 significa dunque, in base alla definizione, effettuare: x · x = x2;      x2 · x = x3;    x3 · x = x4In totale, tre moltiplicazioni. Più rapidamente, con due sole moltiplicazioni:  x · x = x2;      x2 · x2 = x4
Per x16 , invece delle 15 moltiplicazioni suggerite dalla definizione, basta fare:
x · x = x2;      x2 · x2 = x4;      x4 · x4 = x8;      x8 · x8 = x16
solo 4 moltiplicazioni; con una economia non indifferente di calcolo.
Riflettere sul numero di operazioni è un problema di aritmetica computazionale ma è anche un modo per fare matematica mettendo a frutto le proprietà delle potenze e delle altre operazioni fondamentali.
Ad esempio poiché 6=2·3 è:  x6= (x3)2 = x3 · x3 ; ma anche: x6= (x2)3 = x2 · x2 · x2Quindi:
x · x una moltiplicazione
x2 · x due moltiplicazioni
x3 · x3  tre moltiplicazioni
o anche: x · x ; x2 · x2 ;  x4 · x2;   sempre tre moltiplicazioni.
Se si sta operando con una calcolatrice, la differenza tra le due procedure consiste nel fatto che, per la prima occorre memorizzare la x in ingresso, nella seconda la x2 .
A questo punto, ci si potrebbe chiedere se esiste un metodo che dia subito il numero più piccolo di moltiplicazioni per valutare una potenza xn.
Problema matematico di indubbio rilievo! In effetti esistono più metodi ma nessuno di essi dà sempre il numero minimo di operazioni da effettuare. Uno di questi metodi è appunto quello della fattorizzazione dell’esponente.
Metodo dei fattori
Il metodo dei fattori si basa sulla fattorizzazione dell’esponente n.Se n = p·q dove p è il più piccolo fattore primo di n e q > 1, si può calcolare xn calcolando prima xp ed elevando poi questa quantità alla q-esima potenza. Se n è primo si calcola xn-1 e si moltiplica per x. L’applicazione ripetuta di queste regole dà una procedura per valutare xn per ogni dato n.Sia ad esempio da calcolare x15. Poiché 15 = 3·5 occorre calcolare y = x3  e  x15 = y5 = (x3) 5:
x3 = x2 · x    due moltiplicazioniy5 = ( y2)2·y   tre moltiplicazioni
In totale cinque moltiplicazioni.
Metodo binario
Un metodo molto più antico e semplice, che Donald E. Knuth[i] attribuisce addirittura alla matematica indù, si basa sulla scrittura binaria del numero n che è una sequenza di “1” e di “0”.Il metodo consiste nel sostituire QX alla cifra “1”, e Q alla cifra “0”, e cancellando il primo QX.Il risultato è una regola per calcolare xn se si interpreta “Q” come “quadrato” e X come “moltiplicazione per x”.Consideriamo la potenza x15; poiché 15 = 1111 si ha:
QX    QX    QX    QX
e cancellando il primo QX a sinistra
QX    QX    QX
ovvero:quadrare – moltiplicare per x – quadrare – moltiplicare per x – quadrare – moltiplicare per x : sei moltiplicazioni.
Per x15 operando con il metodo binario occorre una moltiplicazione in più che operando con il metodo dei fattori.
C’è da osservare che 15 è il più piccolo esponente per cui ciò capita e che per tutti gli n < 15 i due metodi forniscono lo stesso numero di operazioni. Per n = 33 però la situazione si inverte; è il metodo dei fattori a richiedere una operazione in più e 33 è il minimo intero per cui ciò accade.Infatti, con il metodo dei fattori x33 = (x3)11 ; per valutare y= x3 = x2 · x  due moltiplicazioni y11= (y2)5·y  cinque moltiplicazioni in quanto: z = y2 = y·y   una moltiplicazione z5 = (z2)2 ·z   tre moltiplicazioni z5 · z    una moltiplicazione In totale 7 moltiplicazioni.Con il metodo binario 33=100001 quindi: QX    Q       Q       Q       Q       QX     ovvero Q        Q       Q      Q       QX cioè solo 6 operazioni. E’ opinione di più autori che il metodo dei fattori, in media, funzioni meglio, ma il metodo binario è molto più facile e rapido. Didatticamente poi si rivela ancor più incisivo perché fornisce un’applicazione della stessa scrittura binaria dei numeri. L’albero delle potenze Un altro modo per economizzare sul numero di moltiplicazioni occorrenti per calcolare una potenza è quello di far riferimento all’albero potenza riportato in figura: Per calcolare xn , basta trovare n sull’albero; il numero di passi dall’origine ad n, dà il numero necessario di moltiplicazioni e i numeri che si incontrano nei successivi “nodi” rappresentano la sequenza di esponenti di cui bisogna tener conto nel calcolo. L’albero potenza non risulta comodo da utilizzare specie per valori non piccoli di n e ciò soprattutto per la sua costruzione. Comunque può riuscire certamente utile, se non addirittura un divertente esercizio, conoscere ed applicare la regola di formazione dei successivi nodi fino ad un certo punto della arborescenza. Per la costruzione della linea (k+1)-esima si procede da sinistra a destra come segue: al primo nodo n della riga k-esima si congiungono, nell’ordine, i nodi n+1, n+a1 , …., n+ak =2n dove 1, a1, a2, …., ak sono i nodi che si intercettano nel cammino dalla radice dell’albero ad n. Non si riportano, però, come nodi, quei numeri che già compaiono nell’albero. Per la costruzione ad esempio della sesta riga dell’albero riportato in figura si parte dal numero 7. Si ottengono: 7+1, 7+2, 7+3, 7+5, 7+7 Poiché 8, 9, 10 e 12 già figurano nell’albero, l’unica filiazione di 7 è il nodo 14. Per il nodo successivo a destra, 10, si ottengono: 10+1, 10+2, 10+3, 10+5, 10+10 Escluso 12, si hanno i nodi, nell’ordine, 11, 13, 15, 20. L’albero fino all’ottava riga è quello della figura seguente: In molti casi comunque l’albero potenza dà risultati migliori sia del metodo binario sia del metodo dei fattori e n=23 è il più piccolo n per cui ciò accade. Il calcolo di una potenza è patrimonio dei primi anni di scolarità ed il fatto che non esista una risposta univoca alla determinazione del numero minimo di operazioni da compiere ma che questo dipenda dal metodo utilizzato ha certamente una grossa rilevanza didattica e formativa. Rilevanza che diviene ancor più incisiva se si nota che una tale risposta esiste per l’analogo problema del calcolo del valore di un polinomio P(x) per un dato x. In questo caso la risposta è determinata dall’algoritmo di Ruffini-Horner [ii] che consiste nello scrivere il polinomio: nella forma: che, vale la pena di notarlo, richiede, esattamente n moltiplicazioni ed n addizioni (una addizione in meno per ogni coefficiente nullo) per valutare P(x) per un determinato valore di x. Anzi, E.G. Belaga (nel 1958) e V. Ya Pan (nel 1962) dimostrarono, rispettivamente, che n è il numero minimo di addizioni e di moltiplicazioni necessario per calcolare P(x) di grado n e con coefficienti generali.[iii]. È da osservare, infine, che il problema di risparmiare sulle operazioni da compiere è divenuto attuale negli ultimi decenni del secolo scorso in connessione alla sviluppo della computer science, quando si trattava di programmare le istruzioni di calcolo da affidare ad una macchina, ma è molto più antico. Ciò vuol dire che nella matematica ha un valore etico notevole: è stato avvertito sia quando lo schiavo-calcolatore era umano sia quando si trattava solo di una macchina. NOTE [i]Donald E. Knuth, The Art of Computer programming, Addison-Wesley 1969, vol.2, pagg.398 e seguenti. [ii]Paolo Ruffini pubblicò la regola nel 1804 (nelle Memorie della Società Italiana delle Scienze, Modena) e G.W. Horner successivamente nel 1819 negli atti della Royal Society of London utilizzò la regola nella discussione di un metodo per valutare P(x+c). Essa è ora universalmente nota come algoritmo di Ruffini-Horner (la priorità di Ruffini fu riconosciuta esplicitamente da F. Cajori solo nel 1911) anche se più di cento anni prima di Ruffini era stata data da I. Newton e addirittura, secondo J.L. Coolidge, era probabilmente già patrimonio della matematica cinese del tredicesimo secolo. [iii]Giuseppe Geymonat, Lezioni di Matematica, Levrotto & Bella 1981, vol.1, pag.216. Un inserimento del problema nei testi scolastici lo si deve a Carlo Sbordone nella sua Algebra per il biennio superiore, ed. Loffredo, Napoli 1988. L’articolo riproduce, a parte lievi ritocchi, l’articolo: Emilio Ambrisi, Economizzare nelle operazioni, Periodico di Matematiche, 1/1992 Laureato in matematica, docente e preside e, per un quarto di secolo, ispettore ministeriale. Responsabile, per il settore della matematica e della fisica, della Struttura Tecnica del Ministero dell'Istruzione. Segretario, Vice-Presidente e Presidente Nazionale della Mathesis dal 1980 in poi e dal 2009 al 2019, direttore del Periodico di Matematiche. Visualizza tutti gli articoli

Risparmiare effettuando il minor numero di operazioni. Un problema che vale la pena di porsi, affrontabile anche da chi è alle prime armi!
aula di matematica
Dato x, xn  è per definizione: x·x·x……·x , n fattori tutti uguali ad x.
Calcolare x4 significa dunque, in base alla definizione, effettuare: x · x = x2;      x2 · x = x3;    x3 · x = x4In totale, tre moltiplicazioni. Più rapidamente, con due sole moltiplicazioni:  x · x = x2;      x2 · x2 = x4
Per x16 , invece delle 15 moltiplicazioni suggerite dalla definizione, basta fare:
x · x = x2;      x2 · x2 = x4;      x4 · x4 = x8;      x8 · x8 = x16
solo 4 moltiplicazioni; con una economia non indifferente di calcolo.
Riflettere sul numero di operazioni è un problema di aritmetica computazionale ma è anche un modo per fare matematica mettendo a frutto le proprietà delle potenze e delle altre operazioni fondamentali.
Ad esempio poiché 6=2·3 è:  x6= (x3)2 = x3 · x3 ; ma anche: x6= (x2)3 = x2 · x2 · x2Quindi:
x · x una moltiplicazione
x2 · x due moltiplicazioni
x3 · x3  tre moltiplicazioni
o anche: x · x ; x2 · x2 ;  x4 · x2;   sempre tre moltiplicazioni.
Se si sta operando con una calcolatrice, la differenza tra le due procedure consiste nel fatto che, per la prima occorre memorizzare la x in ingresso, nella seconda la x2 .
A questo punto, ci si potrebbe chiedere se esiste un metodo che dia subito il numero più piccolo di moltiplicazioni per valutare una potenza xn.
Problema matematico di indubbio rilievo! In effetti esistono più metodi ma nessuno di essi dà sempre il numero minimo di operazioni da effettuare. Uno di questi metodi è appunto quello della fattorizzazione dell’esponente.
Metodo dei fattori
Il metodo dei fattori si basa sulla fattorizzazione dell’esponente n.Se n = p·q dove p è il più piccolo fattore primo di n e q > 1, si può calcolare xn calcolando prima xp ed elevando poi questa quantità alla q-esima potenza. Se n è primo si calcola xn-1 e si moltiplica per x. L’applicazione ripetuta di queste regole dà una procedura per valutare xn per ogni dato n.Sia ad esempio da calcolare x15. Poiché 15 = 3·5 occorre calcolare y = x3  e  x15 = y5 = (x3) 5:
x3 = x2 · x    due moltiplicazioniy5 = ( y2)2·y   tre moltiplicazioni
In totale cinque moltiplicazioni.
Metodo binario
Un metodo molto più antico e semplice, che Donald E. Knuth[i] attribuisce addirittura alla matematica indù, si basa sulla scrittura binaria del numero n che è una sequenza di “1” e di “0”.Il metodo consiste nel sostituire QX alla cifra “1”, e Q alla cifra “0”, e cancellando il primo QX.Il risultato è una regola per calcolare xn se si interpreta “Q” come “quadrato” e X come “moltiplicazione per x”.Consideriamo la potenza x15; poiché 15 = 1111 si ha:
QX    QX    QX    QX
e cancellando il primo QX a sinistra
QX    QX    QX
ovvero:quadrare – moltiplicare per x – quadrare – moltiplicare per x – quadrare – moltiplicare per x : sei moltiplicazioni.
Per x15 operando con il metodo binario occorre una moltiplicazione in più che operando con il metodo dei fattori.
C’è da osservare che 15 è il più piccolo esponente per cui ciò capita e che per tutti gli n < 15 i due metodi forniscono lo stesso numero di operazioni. Per n = 33 però la situazione si inverte; è il metodo dei fattori a richiedere una operazione in più e 33 è il minimo intero per cui ciò accade.Infatti, con il metodo dei fattori x33 = (x3)11 ; per valutare y= x3 = x2 · x  due moltiplicazioni y11= (y2)5·y  cinque moltiplicazioni in quanto: z = y2 = y·y   una moltiplicazione z5 = (z2)2 ·z   tre moltiplicazioni z5 · z    una moltiplicazione In totale 7 moltiplicazioni.Con il metodo binario 33=100001 quindi: QX    Q       Q       Q       Q       QX     ovvero Q        Q       Q      Q       QX cioè solo 6 operazioni. E’ opinione di più autori che il metodo dei fattori, in media, funzioni meglio, ma il metodo binario è molto più facile e rapido. Didatticamente poi si rivela ancor più incisivo perché fornisce un’applicazione della stessa scrittura binaria dei numeri. L’albero delle potenze Un altro modo per economizzare sul numero di moltiplicazioni occorrenti per calcolare una potenza è quello di far riferimento all’albero potenza riportato in figura: Per calcolare xn , basta trovare n sull’albero; il numero di passi dall’origine ad n, dà il numero necessario di moltiplicazioni e i numeri che si incontrano nei successivi “nodi” rappresentano la sequenza di esponenti di cui bisogna tener conto nel calcolo. L’albero potenza non risulta comodo da utilizzare specie per valori non piccoli di n e ciò soprattutto per la sua costruzione. Comunque può riuscire certamente utile, se non addirittura un divertente esercizio, conoscere ed applicare la regola di formazione dei successivi nodi fino ad un certo punto della arborescenza. Per la costruzione della linea (k+1)-esima si procede da sinistra a destra come segue: al primo nodo n della riga k-esima si congiungono, nell’ordine, i nodi n+1, n+a1 , …., n+ak =2n dove 1, a1, a2, …., ak sono i nodi che si intercettano nel cammino dalla radice dell’albero ad n. Non si riportano, però, come nodi, quei numeri che già compaiono nell’albero. Per la costruzione ad esempio della sesta riga dell’albero riportato in figura si parte dal numero 7. Si ottengono: 7+1, 7+2, 7+3, 7+5, 7+7 Poiché 8, 9, 10 e 12 già figurano nell’albero, l’unica filiazione di 7 è il nodo 14. Per il nodo successivo a destra, 10, si ottengono: 10+1, 10+2, 10+3, 10+5, 10+10 Escluso 12, si hanno i nodi, nell’ordine, 11, 13, 15, 20. L’albero fino all’ottava riga è quello della figura seguente: In molti casi comunque l’albero potenza dà risultati migliori sia del metodo binario sia del metodo dei fattori e n=23 è il più piccolo n per cui ciò accade. Il calcolo di una potenza è patrimonio dei primi anni di scolarità ed il fatto che non esista una risposta univoca alla determinazione del numero minimo di operazioni da compiere ma che questo dipenda dal metodo utilizzato ha certamente una grossa rilevanza didattica e formativa. Rilevanza che diviene ancor più incisiva se si nota che una tale risposta esiste per l’analogo problema del calcolo del valore di un polinomio P(x) per un dato x. In questo caso la risposta è determinata dall’algoritmo di Ruffini-Horner [ii] che consiste nello scrivere il polinomio: nella forma: che, vale la pena di notarlo, richiede, esattamente n moltiplicazioni ed n addizioni (una addizione in meno per ogni coefficiente nullo) per valutare P(x) per un determinato valore di x. Anzi, E.G. Belaga (nel 1958) e V. Ya Pan (nel 1962) dimostrarono, rispettivamente, che n è il numero minimo di addizioni e di moltiplicazioni necessario per calcolare P(x) di grado n e con coefficienti generali.[iii]. È da osservare, infine, che il problema di risparmiare sulle operazioni da compiere è divenuto attuale negli ultimi decenni del secolo scorso in connessione alla sviluppo della computer science, quando si trattava di programmare le istruzioni di calcolo da affidare ad una macchina, ma è molto più antico. Ciò vuol dire che nella matematica ha un valore etico notevole: è stato avvertito sia quando lo schiavo-calcolatore era umano sia quando si trattava solo di una macchina. NOTE [i]Donald E. Knuth, The Art of Computer programming, Addison-Wesley 1969, vol.2, pagg.398 e seguenti. [ii]Paolo Ruffini pubblicò la regola nel 1804 (nelle Memorie della Società Italiana delle Scienze, Modena) e G.W. Horner successivamente nel 1819 negli atti della Royal Society of London utilizzò la regola nella discussione di un metodo per valutare P(x+c). Essa è ora universalmente nota come algoritmo di Ruffini-Horner (la priorità di Ruffini fu riconosciuta esplicitamente da F. Cajori solo nel 1911) anche se più di cento anni prima di Ruffini era stata data da I. Newton e addirittura, secondo J.L. Coolidge, era probabilmente già patrimonio della matematica cinese del tredicesimo secolo. [iii]Giuseppe Geymonat, Lezioni di Matematica, Levrotto & Bella 1981, vol.1, pag.216. Un inserimento del problema nei testi scolastici lo si deve a Carlo Sbordone nella sua Algebra per il biennio superiore, ed. Loffredo, Napoli 1988. L’articolo riproduce, a parte lievi ritocchi, l’articolo: Emilio Ambrisi, Economizzare nelle operazioni, Periodico di Matematiche, 1/1992 Laureato in matematica, docente e preside e, per un quarto di secolo, ispettore ministeriale. Responsabile, per il settore della matematica e della fisica, della Struttura Tecnica del Ministero dell'Istruzione. Segretario, Vice-Presidente e Presidente Nazionale della Mathesis dal 1980 in poi e dal 2009 al 2019, direttore del Periodico di Matematiche. Visualizza tutti gli articoli