Alla scoperta di algoritmi antichi e curiosi

Algoritmi antichi e curiosi
Tempo di lettura: 3 minuti

Se hai a che fare con la matematica frequentemente, la dimestichezza con gli algoritmi certo non ti manca 😉 Tuttavia, per mettere tutti i lettori di questo articolo su un punto di partenza più o meno equo, ho pensato di iniziare il tutto con una “definizione” di algoritmo.

Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari.

Questa non è una vera e propria definizione, in quanto per essere completa dovrebbe fornire anche un bell’elenco di proprietà di cui deve godere un algoritmo. Tuttavia ritengo che, per quello che andrai a leggere nelle prossime righe, questa breve introduzione al concetto di algoritmo sia più che sufficiente.

Di algoritmi noti ve ne sono un’infinità e, ogni giorno, programmatori, matematici, fisici e ingegneri di tutto il mondo ne inventano di nuovi per risolvere i problemi che si trovano ad affrontare quotidianamente al lavoro.

algoritmi antichi e curiosi

Nonostante molti algoritmi siano noti ai più, ritengo che ve ne siano alcuni davvero curiosi, intriganti e per lo più finiti nel dimenticatoio.

Certamente se alcuni di questi sono stati col tempo tralasciati c’è un motivo, il principale è senz’altro la loro inefficienza (ossia incapacità di arrivare ad un risultato in pochi passi).

Tuttavia li trovo curiosi da un punto di vista teorico e metodologico.

Partiamo quindi con un semplice elenco dei 4 algoritmi antichi e curiosi che ti andrò a presentare, seppur brevemente (non escludo di trattarli in modo approfondito e esteso in articoli dedicati in futuro), nelle seguenti righe.

Lista dei 4 algoritmi antichi e curiosi trattati di seguito:

  • Moltiplicazione egizia
  • Algoritmo di Euclide per il calcolo dell’MCD
  • Algoritmo babilonese calcolo radice quadrata
  • Moltiplicazione alla russa

Andiamo ora a trattarli brevemente uno per uno 🙂

Algoritmo moltiplicazione egizia

Questo algoritmo è molto antico e anche intrigante, infatti permette di fare la moltiplicazione di due numeri naturali in una maniera che apparentemente può sembrare davvero misteriosa.

Prima di spiegare come funziona l’algoritmo, ti faccio vedere un procedimento svolto, vediamo se ti è subito chiaro 😉

algoritmo moltiplicazione egizia

Ora ti scrivo l’algoritmo in un linguaggio comprensibile (pseudocodifica):

a,b interi

z = 0

finchè (a>0):

se a dispari -> z=z+b

a=a//z (divisione intera)

b=b*2

risultato z

Se provi a tracciare o comunque ad eseguire manualmente questo algoritmo, probabilmente riesci ad accorgerti che si basa sulla notazione in base 2. Tuttavia preferisco non dimenticare informazioni importati per scrivere poco, quindi a questo, come ai seguenti algoritmi, dedicherò un intero articolo in futuro. Per ora quindi accontentati di queste informazioni, oppure ti basta digitare ‘moltiplicazione egizia’ su Google e troverai le risposte alle tue domande 😉

Algoritmo di Euclide per il calcolo dell’MCD

Questo non è per nulla un algoritmo inefficiente, infatti permette di trovare l’MCD tra due numeri in molti meno passi rispetto al comune procedimento. Infatti invece di trovare prima i divisori di un numero, trovare i divisori del secondo e cercare il più grande divisore in comune, l’algoritmo che ti sto per presentare utilizza solo somme e differenze 🙂

Partiamo, questa volta, con la pseudocodifica:

a,b naturali

finchè a!=b (!= significa diverso):

se a>b allora a=a-b

altrimenti b=b-a

risultato a

Provare per credere 😉 con questi semplici conti arriverai a trovare facilmente l’MCD tra due numeri. E’ certamente meno intuitivo del procedimento che comunemente fai per trovare il massimo comune divisore tra due numeri, tuttavia nella scrittura di codici (programmazione) questo algoritmo risulta spesso molto utile.

Prova a capire come fa a ‘funzionare’ e scrivilo nei commenti! Comunque nelle prossime settimane pubblicherò un articolo dedicato a questo specifico algoritmo.

Algoritmo babilonese calcolo radice quadrata

Ora però te ne illustro un altro, più banale da apprendere, facile da applicare e molto efficiente ma sostanzialmente in disuso. Fu introdotto dai babilonesi, pensa che storia che ha questo algoritmo alle spalle! 😉 Perchè dimenticarlo?

Ecco la sua pseudocodifica:

x,a naturali (x è il numero di cui si vuole estrarre la radice, a un’approssimazione per difetto                    che si intuisce, in caso non se ne abbia idea a=1 )

finchè non è abbastanza preciso il risultato:

t=x

r=(t+a)/2 (media aritmetica)

s=x/r (media armonica)

t=r

a=s

risultato s

Le operazioni dopo il finchè puoi anche decidere a priori di eseguire 3-4 volte, tanto la velocità con cui s converge alla radice effettiva di x è davvero elevata. Prova per esempio con la radice di 2, vedrai che già dopo 3 iterazioni avrai una precisione di 5-6 cifre dopo la virgola.

Moltiplicazione alla russa

Un algoritmo relativo alla moltiplicazione, te l’ho già presentato, tuttavia trovo interessante ed intuitivo anche un secondo algoritmo per eseguire i prodotti tra due numeri naturali. Sto parlando della moltiplicazione alla russa. Sostanzialmente il metodo si basa sul raddoppiare il primo fattore e dimezzare il secondo, finchè questo non diventa 1. In caso di numero dispari, ad essere diviso sarà n-1. Il risultato del prodotto è infine la somma dei numeri disposti sotto il primo fattore, corrispondenti ai numeri  dispari della seconda colonna.

Moltiplicazione alla russa
Immagine presa da http://www.aliperlamente.it/ED/Moltiplicazioni/Molt.russa.pdf

Bene, spero di averti incuriosito ed interessato con questi cenni a 4 algoritmi antichi e curiosi.

Spero possano nascere discussioni interessanti 😉

2 risposte a “Alla scoperta di algoritmi antichi e curiosi”

  1. Avatar Denise Quarles
    Denise Quarles

    Ciao Davide,

    Ecco un’altro algoritmo relativo alla moltiplicazione che ho imparato in un corso di matematica per insegnanti:

    https://www.khanacademy.org/math/arithmetic-home/multiply-divide/place-value-area-models/v/lattice-multiplication

    Complimenti per il sito!

    Denise (e Michele) da Seattle!

    1. Avatar Dadeslam
      Dadeslam

      Grazie per l’algoritmo, appena ho un po’ di tempo lo guardo.
      Ciao 🙂

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.