sabato 10 settembre 2011

I logaritmi come li fanno i computer — parte 3

Vediamo come fanno i sistemi dotati di poche risorse a calcolare i logaritmi. Però per capire bene come funziona questo algoritmo è meglio partire dal calcolo di seno e coseno.

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: