Gabriele Lami
Co-founder @ Elif Lab : www.eliflab.com
Scrivo questo breve post per il piacere di scriverlo,
il mio obiettivo non è di raggiungere un obiettivo.
La parola algoritmo è spesso usata, abusata e misconosciuta.
Non voglio qui disquisire circa la definizione di algoritmo ma voglio mostrare micro programma, implementazione di un algoritmo classico (il concetto di algoritmo è molto classico).
(.5×⊢+÷)⍣≡
Tutto qui.
Cosa c’è scritto? In che linguaggio? Perché è l’implementazione di un algoritmo?
L’algoritmo serve a trovare la radice quadrata di un numero, viene definito metodo Babilonese.
Il linguaggio di programmazione è APL (l’implementazione cui faccio riferimento è https://www.dyalog.com/): la sintassi di APL è molto insolita e efficace rispetto all’implementazione di metodi matematici.
APL possiede diversi caratteri speciali che permettono di esprimere un programma limitando l’utilizzo di strumenti sintattici che non sono legati alla rappresentazione dell’algoritmo.
Mi ha sempre affascinato la rappresentazione dei concetti.
Se si è fortunati, la rappresentazione di un concetto aiuta a rendere più immediata la sua rappresentazione mentale.
Prendiamo una semplice definizione di algoritmo: “Qualsiasi schema o procedimento sistematico di calcolo”.
Qual è il procedimento sistematico rappresentato da (.5×⊢+÷)⍣≡ ?
L’obiettivo del metodo Babilonese è di calcolare la radice di un numero N.
Il metodo (sistematico di calcolo) ci dice:
- Parti da un valore iniziale che per te è vicino alla radice, R.
- Calcola: 0.5 * ( R + N/R) = R_n
- Ripeti il processo prendendo come nuovo valore di R il valore R_n
Questo procedimento converge al valore corretto della radice. Cioè più volte lo ripetiamo, più ci avviciniamo al valore cercato.
Ma quindi in (.5×⊢+÷)⍣≡ c’è scritto tutto il procedimento?
La risposta è affermativa. La rappresentazione in APL è molto più compatta di quella scritta a parole.
Ora viene la parte difficile, il tentativo di spiegare il mistico codice.
Una premessa: in APL le funzioni possono avere un parametro a destra e/o uno a sinistra.
I parametri vengono indicati con ⍺ (parametro sinistro) e ⍵ (parametro destro).
Dividiamo il programma in due parti:
- (.5×⊢+÷)
- ⍣≡
La prima parte rappresenta il singolo passo spiegato precedentemente:
0.5 * ( R + N/R) = R_n
La seconda parte dice “itera la prima parte fino a che l’elemento calcolato non risulta uguale al precedente”.
Siamo sicuri che per merito del fatto che l’algoritmo converge, ad un certo punto la differenza tra un passo e il successivo sarà inferiore alla precisione del calcolatore, quindi da un certo step in poi si otterrà sempre lo stesso valore.
Cerchiamo di tradurre la prima parte:
(.5×⊢+÷) può essere visto come la composizione di 4 funzioni
- .5× (moltiplicazione per .5 del valore a destra)
- ⊢ (selezione del valore a destra: es. 3 ⊢ 2 = 2 )
- + ( somma del valore sinistro e destro)
- ÷ ( valore sinistro diviso valore destro)
Le funzioni giustapposte in questo modo senza variabili seguono delle precise regole di composizione.
Per quattro funzioni le seguenti formulazioni sono equivalenti:
F G H I
F( (⍺ G ⍵) H (⍺ I ⍵) )
La funzione viene quindi interpretata come:
.5×( ( ⍺ ⊢ ⍵) + (⍺÷⍵) )
Applicando ⊢
.5×( ⍵ + (⍺÷⍵) )
Se sostituiamo ⍺ con N e ⍵ con R otteniamo lo step dell’algoritmo 0.5 * ( R + N/R).
Quindi
(.5×⊢+÷)⍣≡ è equivalente a “.5 * ( R + N/R) fino a che il risultato è uguale allo step precedente”.
Ti incuriosiscono APL e gli algoritmi? Contattaci a info@eliflab.com