Quindi per adesso mettiamo da parte per un po' i logaritmi e concentriamoci sul problema del calcolo di seno e coseno di un angolo. Partendo da questa specie di ventaglio.
È una figura composta da triangoli rettangoli costruiti in questo modo: BC è perpendicolare a AB ed è anche uguale a AB. Prendiamo questa lunghezza come unitaria.
CD è perpendicolare a AC e lunga AC/2,
DE è perpendicolare a AD e lunga AD/4,
EF è perpendicolare a AE e lunga AE/8,
FG è perpendicolare a AF e lunga AF/16.
Nella figura ci siamo fermati a cinque triangoli, ma si potrebbe andare avanti all'infinito. Un primo fatto interessante è questo: se anche facciamo un ventaglio composto da infinite parti, e se continuiamo con la regola che si può intuire dalle prime cinque costruzioni, l'angolo totale che si viene a formare in A è finito, pari a circa 1.74 radianti, cioè poco meno di 100 gradi. Nel programma che costruiremo tra poco prenderemo un ventaglio composto da 24 settori (sono sempre poco meno di 100 gradi, rispetto al ventaglio infinito i due angoli in radianti sono uguali fino alla settima cifra dopo la virgola).
Ora diciamo che il nostro problema sia quello di calcolare il seno di 70 gradi. L'idea è quello di approssimare l'angolo utilizzando il ventaglio, i cui pezzi però possono essere piegati sia in senso antiorario, come in figura, sia in senso orario. Possiamo cioè tornare indietro. Con una figura si capisce meglio:
La semiretta rossa rappresenta l'angolo di 70 gradi (misurato rispetto al segmento orizzontale). Come si vede, i primi due settori del ventaglio sono stati spiegati in senso antiorario, ma così facendo abbiamo superato i 70 gradi. Allora il terzo settore viene spiegato in senso orario, cioè tornando indietro. Così facendo siamo tornati al di sotto dei 70 gradi. I successivi due settori, allora sono stati spiegati in senso antiorario, in modo da avvicinarsi il più possibile a 70.
Rispondo subito alla prima domanda: non potevamo fermarci dopo due passi? Eravamo già molto vicini, e se avessimo avuto un ventaglio di soli tre settori, aggiungendo il terzo avremmo peggiorato l'avvicinamento. La risposta è no, il ventaglio viene sempre usato tutto. Si può dimostrare che l'errore che si ottiene utilizzando questo metodo è minore o uguale all'ampiezza dell'ultimo angolo utilizzato nella costruzione del ventaglio.
Quindi col nostro ventaglio a 24 settori possiamo raggiungere esattamente 223 = 8388608 posizioni, e rimanere vicino a tutte le rimanenti per meno dell'ampiezza dell'ultimo angolo (ammesso che rimaniamo entro l'ampiezza di quasi 100 gradi di cui abbiamo parlato prima — ma ai fini del calcolo di seno e coseno questa non è una limitazione, ci bastano ampiezze minori).
Bene, ora rimane da studiare l'ampiezza dei vari settori del ventaglio. Dato che abbiamo costruito triangoli rettangoli, ogni angolo risulta essere uguale all'arcotangente del rapporto tra i cateti. E quindi abbiamo che il primo angolo è l'arcotangente di 1 (cioè 45 gradi), il secondo è l'arcotangente di 1/2, e cioè 26.57 gradi, il terzo l'arcotangente di 1/4, e così via fino all'ultimo, che è l'arcotangente di 1/223, cioè 0.00000683 gradi. Questa è la precisione che riusciamo a raggiungere con questo metodo.
Ecco come procede l'algoritmo per l'avvicinamento a 70 gradi, utilizzando il nostro ventaglio a 24 settori. In prima colonna l'ampiezza del settore (preceduta da un segno positivo se stiamo andando in senso antiorario, cioè stiamo aggiungendo angoli, e da un segno negativo se stiamo invece andando in senso orario), in seconda colonna il risultato parziale. Alla fine arriviamo a 70 gradi con un errore sulla sesta cifra.
+ 45.0000000000 45.0000000000 + 26.5650511771 71.5650511771 - 14.0362434679 57.5288077092 + 7.1250163489 64.6538240581 + 3.5763343750 68.2301584331 + 1.7899106082 70.0200690413 - 0.8951737102 69.1248953311 + 0.4476141709 69.5725095019 + 0.2238105004 69.7963200023 + 0.1119056771 69.9082256794 + 0.0559528919 69.9641785713 + 0.0279764526 69.9921550239 + 0.0139882271 70.0061432510 - 0.0069941137 69.9991491374 + 0.0034970569 70.0026461942 - 0.0017485284 70.0008976658 - 0.0008742642 70.0000234016 - 0.0004371321 69.9995862695 + 0.0002185661 69.9998048355 + 0.0001092830 69.9999141185 + 0.0000546415 69.9999687601 + 0.0000273208 69.9999960808 + 0.0000136604 70.0000097412 - 0.0000068302 70.0000029110
Ora dobbiamo solo ricordarci le formule di somma e sottrazione di seno e coseno, ed è fatta. Eccole:
cos(x±y) = cos(x)cos(y)∓sin(x)sin(y),
sin(x±y) = sin(x)cos(y)±cos(x)sin(y).
In pratica, ogni volta che aggiungiamo o togliamo un settore del ventaglio per avvicinarci all'angolo, possiamo calcolare seno e coseno della nuova approssimazione a partire da seno e coseno della vecchia. Naturalmente dobbiamo essere in grado di calcolare seno e coseno di ognuno degli angoli di cui è composto il ventaglio; ma dato che sono solo 24 li possiamo calcolare una volta per tutte e poi memorizzarli in una tabella.
Ecco un programmino che esegue il calcolo (notate che calcola simultaneamente seno e coseno; alla fine restituisce solo il seno, contenuto nella variabile st0, ma potrebbe anche restituire il coseno, che si trova memorizzato in ct0) :
from math import atan,sin,cos,pi
ango={}
seni={}
cosi={}
# costruisce le tabelle
for i in xrange(24): ango[i]=atan(1./2**i) seni[i]=sin(ango[i]) cosi[i]=cos(ango[i]) def seno1(x): s=0 ca0=cosi[0] sa0=seni[0] ct0=1 st0=0 for i in xrange(24): if s>x: s-=ango[i] ct1=ct0*cosi[i]+st0*seni[i] st1=st0*cosi[i]-ct0*seni[i] else: s+=ango[i] ct1=ct0*cosi[i]-st0*seni[i] st1=st0*cosi[i]+ct0*seni[i] ct0=ct1 st0=st1 return st0 v1 = seno1(70./180*pi) v2 = sin(70./180*pi) print v1,v2,abs(v1-v2)
All'inizio vengono calcolate le tre tabelle che contengono rispettivamente i valori degli angoli che formano il ventaglio, i loro seni e i loro coseni. Poi parte il ciclo che aggiunge (o sottrae) un angolo ad ogni passo e ricalcola coseno e seno con le opportune formule. Alla fine vengono stampati il risultato, il valore vero (che poi è calcolato dal programma con un altro algoritmo, ma ci capiamo) e l'errore. Ecco l'output:
0.939692638163 0.939692620786 1.73768638367e-08
Naturalmente si può migliorare la precisione semplicemente aumentando le dimensioni delle tabelle.
Ma nella realtà non si può fare così: stiamo immaginando di avere poche risorse, cioè processori poco potenti, e tutte quelle moltiplicazioni tra seni e coseni non ci piacciono molto. Vorremmo evitarle e, incredibilmente, si può. La prossima volta vediamo come.
Nessun commento:
Posta un commento