# Algoritmo di prostaferesi

L'algoritmo di prostaferesi è stato usato a cavallo tra il XVI e il XVII secolo per determinare in modo approssimato il risultato di una moltiplicazione sfruttando alcune relazioni trigonometriche. Per un quarto di secolo, fino al 1614 con l'introduzione dei logaritmi, fu l'unico metodo noto e applicabile su larga scala per eseguire rapidamente il calcolo manuale di moltiplicazioni. La parola prostaferesi deriva dalla giustapposizione di due parole di origine greca, prosthesis (πρόσθεσις) e aphaeresis (ὰφαίρεσις), che significano rispettivamente somma e sottrazione, due passaggi fondamentali dell'algoritmo.

## Storia
### La necessità pratica

Nel XVI secolo le flotte europee che solcavano i mari con lunghe traversate oceaniche utilizzavano per l'orientamento la navigazione astronomica che faceva uso delle effemeridi preparate dagli astronomi. Determinare la propria posizione rispetto a quella che le effemeridi davano per gli oggetti celesti osservabili comportava la risoluzione di equazioni di trigonometria sferica. Infatti considerando un triangolo sferico come quello in figura, valgono le seguenti relazioni:
    ${\begin{cases}\sin a\ \sin \beta =\sin b\ \sin \alpha \\\cos a=\cos b\ \cos c+\sin b\ \sin c\ \cos \alpha \end{cases}}$
Noto dalle effemeridi un numero sufficiente di variabili, le altre possono essere determinate risolvendo le equazioni, il che inevitabilmente comporta delle moltiplicazioni. Gli astronomi, a loro volta, per redigere le effemeridi dovevano effettuare complicati calcoli sulla traiettoria degli oggetti celesti. Affrontare questi calcoli armati solo del metodo scolastico per il calcolo delle moltiplicazioni significava spendere la maggior parte del tempo a effettuare moltiplicazioni.

### Contributi nella definizione

I matematici, in particolare coloro che erano anche astronomi, si impegnarono nella ricerca di un metodo per eseguire le moltiplicazioni più semplice di quello scolastico e una delle discipline a loro più familiari era la trigonometria. L'algoritmo di prostaferesi fece la propria comparsa negli anni 80 del '500, ma non è accertato chi ne fu l'autore. Sicuramente tra coloro che contribuirono devono essere citati Paul Wittich, Ibn Yunis, Joost Bürgi, Johann Werner, Christophorus Clavius e François Viète. In particolare Wittich, Yunis e Clavius sono gli astronomi a cui fonti diverse attribuiscono l'onore della definizione dell'algoritmo. Tra i più noti propugnatori bisogna menzionare Tycho Brahe, che lo usò diffusamente per i propri calcoli in astronomia. Anche Nepero, che è ricordato per l'introduzione dei logaritmi che resero obsoleto questo algoritmo, ne fece grande uso.

### Curiosità

Mentre il regolo calcolatore, basato sull'algoritmo di moltiplicazione con logaritmi, fu progettato pochi anni dopo la definizione dell'algoritmo, uno strumento simile ispirato al metodo della prostaferesi non fu mai concepito se non recentemente, quando la sua fattibilità fu presentata in un articolo di ricerca, dandogli il nome di regolo calcolatore prostaferico.

## L'algoritmo
### Le relazioni trigonometriche sfruttate

L'algoritmo non sfrutta le formule di prostaferesi (come viene talvolta erroneamente riportato) ma le relazioni trigonometriche oggi note come formule di Werner (per amor di precisione, la terza e la quarta sono due modi diversi di scrivere la prima formula di Werner):
    $\sin \alpha \sin \beta ={\frac {1}{2}}[\cos(\alpha -\beta )-\cos(\alpha +\beta )]$
    $\cos \alpha \cos \beta ={\frac {1}{2}}[\cos(\alpha -\beta )+\cos(\alpha +\beta )]$
    $\sin \alpha \cos \beta ={\frac {1}{2}}[\sin(\alpha +\beta )+\sin(\alpha -\beta )]$
    $\cos \alpha \sin \beta ={\frac {1}{2}}[\sin(\alpha +\beta )-\sin(\alpha -\beta )]$
Si ritiene che le prime due siano state ottenute per primo da Bürgi.

### Il procedimento

I passi dell'algoritmo, supponendo di volersi avvalere della seconda delle relazioni indicate, sono:
* Scalare: si sposta la virgola decimale a destra o sinistra di tante posizioni quante sono necessarie per trasformare i due fattori della moltiplicazione in numeri compresi tra -1 e 1.
* Trovare l'arcocoseno: si determinano, con l'uso di una tavola trigonometrica, i due angoli il cui coseno corrisponde ai valori trovati al passo precedente.
* Sommare e sottrarre: si calcola la somma e la differenza dei due angoli trovati al passo precedente.
* Fare la media dei coseni: si calcola la media, ovvero la semisomma, del valore dei coseni dei due angoli individuati al passo precedente (tali coseni individuati con l'uso della tavola trigonometrica).
* Riscalare: preso il risultato del passo precedente, si sposta la virgola decimale verso destra o sinistra per un numero di posizioni pari allo spostamento verso sinistra o destra effettuato al primo passo per ciascuno dei fattori.
Le versioni dell'algoritmo che fanno uso delle altre relazioni sono simili, differendo nella tipologia di tavole trigonometriche coinvolte nel secondo e quarto passo. Tuttavia la seconda è la versione più pratica in quanto al secondo e quarto passaggio si può utilizzare la stessa tavola con il semplice stratagemma di usare la colonna risultato come indice e quella indice come risultato.

### Esempio d'uso

Supponiamo di voler moltiplicare 105314 per 0,0720114 avendo a disposizione una tabella trigonometrica del coseno con dettaglio di un grado e precisione fino alla quarta cifra significativa:
* Scalare: per il primo fattore si sposta la virgola a sinistra di 6 posizioni ottenendo 0,105314; per il secondo fattore a destra di 1 posizione ottenendo 0,720114.
* Trovare l'arcocoseno: poiché le migliori approssimazioni disponibili sulla tabella utilizzata sono cos(84°) (che vale 0,1045) e cos(44°) (che vale 0,7193), i due angoli individuati in questo passo sono 84° e 44°.
* Sommare e sottrarre: 84° + 44° = 128°, 84° - 44° = 40°.
* Fare la media dei coseni: dalla tabella utilizzata si ha che cos(128°) è -0,6157 e cos(40°) è 0,7660, per cui la semi somma fa 0,07515.
* Riscalare: spostando la virgola a destra di 6 posizioni e poi a sinistra di 1 si ottiene 7515.
Il risultato corretto sarebbe stato 7583,8085796. Si è pertanto commesso un errore inferiore all'1%, pur utilizzando una tavola trigonometrica molto grezza. A supporto di questo algoritmo furono definite tavole con dettaglio pari al grado secondo e precisione fino alla 14ª cifra.

## Strategie per il contenimento dell'errore

La precisione del risultato finale si può migliorare a piacere aumentando la precisione nell'esecuzione dei calcoli per i passi intermedi. I passi che richiedono il calcolo di somme, differenze e medie sono eseguibili, anche manualmente, in modo semplice e con altissima precisione. Le funzioni trigonometriche, in particolare quelle inverse (arcoseno e arcocoseno), sono invece molto più ostiche per il calcolo manuale e richiedono pertanto il ricorso alle già citate tavole trigonometriche. Ne deriva che la precisione del risultato dipende direttamente dalla precisione delle tavole di cui si può disporre e dagli accorgimenti che si possono adottare nel loro uso.

### Tavole con maggior dettaglio

Una tavola con un dettaglio di un grado, come quella ipotizzata per l'esempio, può comportare, dovendo scegliere il valore angolare disponibile più prossimo, l'introduzione di una approssimazione di circa 0,008726 sul valore del coseno nel caso pessimo (angolo di 89,5°). Il valore della massima approssimazione viene dimezzato raddoppiando il dettaglio, ovvero passando a un dettaglio di 1/2 grado. Cosa che avviene per ogni raddoppio del dettaglio: le tavole con dettaglio al grado secondo (ovvero 1/3600 di grado) danno un'approssimazione massima di circa 0,0000024241.

### Scalare di una posizione in più

Le funzioni trigonometriche inverse sono problematiche in prossimità dei valori estremi +1 e -1 in quanto matematicamente tendono a un punto a tangente verticale e praticamente rendono controintuitiva l'individuazione, tramite tavole trigonometriche, dell'angolo più corretto. Ad esempio, supponendo di disporre di una tavola dell'arcocoseno con precisione alla quarta cifra decimale, dovendo cercare l'arcocoseno di 0,999867 si commetterebbe un errore inferiore scegliendo l'angolo indicato da 0,9998 (1,14°) piuttosto che quello di 0,9999 (0,81°) in quanto il valore effettivo è 0,93°. Se non si dispone di tavole con più decimali, un valido accorgimento è quello di restringere la finestra di validità a -0,9 +0,9, richiedendo lo slittamento di un'ulteriore posizione per i numeri prossimi agli estremi. Ad esempio 980 diverrebbe 0,098 anziché 0,98. La posizione scalata in più va anch'essa recuperata durante l'ultimo passo dell'algoritmo.

### Interpolazione

Un metodo efficace per aumentare la precisione è l'interpolazione lineare, in virtù della quale si sceglie un valore intermedio tra quelli corrispondenti ai due più prossimi. Ad esempio, dovendo determinare il seno di 45,7° e sapendo che il seno di 45° è circa 0,707 mentre quello di 46° è circa 0,719, con l'interpolazione lineare si ottiene:
    0,707 + [(0,719 - 0,707) × (45,7 - 45) / (46 - 45)] = 0,707 + [0,012 × 0,7] = 0,7154.
che è molto prossimo al valore corretto (0,7157). Il vantaggio dell'uso dell'interpolazione lineare è paragonabile a un aumento di dettaglio di 250 volte, ovvero usare l'interpolazione lineare con una tabella dei coseni a 180 valori equivale a usare una tabella con 45000 valori.
Tuttavia mentre l'interpolazione lineare è sicuramente un metodo facilmente implementabile oggigiorno con un programma che volesse emulare l'algoritmo, agli occhi di chi lo doveva usare nel XVI secolo, questo metodo era poco gradito perché riconduceva al problema iniziale di dover fare una moltiplicazione (seppure in genere più semplice). Un metodo efficace nel bilanciare la necessità di precisione con l'esigenza di procedere velocemente è quindi quello di effettuare una stima del valore interpolato.
Ad esempio, per il caso precedente, si sarebbe potuto dire che 0,7 è circa 2/3, pertanto essendo l'intervallo di 0,012 avremmo stimato:
    0,707 + 2/3 × 0,012 = 0,715
che è comunque più accurato che prendere il valore direttamente dalla tabella.

### Esempio d'uso con interpolazione

Ripetiamo il calcolo dell'esempio precedente sfruttando anche l'interpolazione in modo stimato:
* Scalare: per il primo fattore si sposta la virgola a sinistra di 6 posizioni ottenendo 0,105314; per il secondo fattore a destra di 1 posizione ottenendo 0,720114
* Trovare l'arcocoseno: questo è il primo passo in cui l'interpolazione può essere d'aiuto:
          per 0,105314
             dalla tavola vediamo che cos(84°) vale 0,1045) e cos(83°) vale 0,1218
             0,105314 si pone a circa 1/20 dell'intervallo (0,000814 su 0,0173 è circa 8 su 160)
             l'arcocoseno può quindi essere stimato a 84° - 0,05° = 83,95°
          per 0,720114
             dalla tavola vediamo che cos(44°) vale 0,7193 e cos(43°) vale 0,7313
             0,720114 si pone a circa 1/15 dell'intervallo (0,000814 su 0,0120 è circa 8 su 120)
             l'arcocoseno può quindi essere stimato a 44° - 0,07° = 43,93°
* Sommare e sottrarre: 83,95° + 43,93° = 127,88°, 83,95° - 43,93° = 40,02°
* Fare la media dei coseni: questo è il secondo passo in cui l'interpolazione può essere d'aiuto:
          per 127,88°
             dalla tavola vediamo che cos(127°) vale -0,6018 e cos(128°) vale -0,6157
             127,88° si pone a circa 1/10 dell'intervallo (0,12 su 1 è circa 10 su 100)
             poiché l'intervallo è 0,0139 (≈ 0,0140), la correzione apportabile vale circa 0,0014
             il coseno può quindi essere stimato a -0,6157 + 0,0014 = -0,6143
          per 40,02°
             dalla tavola vediamo che cos(40°) vale 0,7660 e cos(41°) vale 0,7547
             40,02° si pone a circa 1/50 dell'intervallo (0,02 su 1 è circa 2 su 100)
             poiché l'intervallo è 0,0113 (≈ 0,0100), la correzione apportabile vale circa 0,0002
             il coseno può quindi essere stimato a 0,7660 - 0,0002 = 0,7658
          per cui la semi somma fa 0,07575
* Riscalare: spostando la virgola a destra di 6 posizioni e poi a sinistra di 1 si ottiene 7575
Il risultato corretto sarebbe stato 7583,8085796. Si è pertanto commesso un errore prossimo allo 0,1%. L'uso della interpolazione, seppure in modo stimato, ha quindi permesso di aumentare la precisione di un ordine di grandezza.