lunedì 6 agosto 2018

CORDIC

Quando a scuola mi hanno spiegato le serie di Taylor hanno aggiunto che le calcolatrici elettroniche usavano questo sistema per calcolare il valore delle funzioni trigonometriche...ho scoperto solo in questi giorni che l'algoritmo realmente impiegato e' CORDIC . Il metodo e' preferito alle serie di potenze perche', con la giusta formulazione, puo' essere sviluppato solo con "shift and add" binari e quindi implementabile anche su microprocessori/microcontrollori di bassa potenza di calcolo

Una delle pagine piu' esaurienti per il metodo si trova a questo indirizzo. Di fatto si tratta di eseguire una rotazione di un vettore

Per una implementazione del metodo si puo' usare il seguente codice in Python 3

La tabella di lookup serve solo per capire dopo quante iterazioni di i si puo' terminare il calcolo e quindi puo' essere omessa nel caso si sappia a priori il valore. In ogni caso la tabella di lookup si puo' ricavare da
------------
import math

for i in range(20):
print (i)
print (math.atan(2**(-i)))
print ("--------")
------------

in z si deve mettere il valore in radianti dell'angolo di rotazione desiderato (in questo caso 70°)
in x,y si trovano le proiezioni del vettore e quindi anche i valori del coseno e del seno della rotazione

in generale si puo' usare una base della potenza diversa da 2. L'utilizzo della base 2 e' utile perche' permette in un calcolatore binario di evitare le moltiplicazioni potendo effettuare dei semplici shift bit

importanti sono anche i valori di inizializzazione dell'algoritmo. Con x=1,y=0 si ottengono come risultati tangente,seno e coseno ma con altre impostazioni si possono calcolare funzioni iperboliche e
----------------------------
import math

lookup = [0.7853981633974483,
0.46364760900080615,
0.24497866312686414,
0.12435499454676144,
0.06241880999595735,
0.031239833430268277,
0.015623728620476831,
0.007812341060101111,
0.0039062301319669718,
0.0019531225164788188,
0.0009765621895593195,
0.0004882812111948983,
0.00024414062014936177,
0.00012207031189367021,
6.103515617420877e-05,
3.0517578115526096e-05,
1.5258789061315762e-05,
7.62939453110197e-06,
3.814697265606496e-06,
1.907348632810187e-06]

K = 0.6072529350088812561694

z = 1.22173 # 70° cos(70°)=0.342 sin(70°)=0.9396
x = 1
y = 0
k = 1

for i in range(19):
if z <= 0:
di = -1.0
else:
di = 1.0
k = k*math.cos(math.atan(di * 2.0**(-i)))
newx = x - (y * di * 2.0**(-i)) 
newy = y + (x * di * 2.0**(-i))
x = newx
y = newy
z = z - (di * lookup[i])
print("{0:2d}".format(i),end=' ')

print("{0:f}".format(x),end=' ')
print("{0:f}".format(y),end=' ')
print("{0:f}".format(k),end=' ')

print("{0:f}".format(z))

print ()
print ("Tangente : " + str(y/x))
print ("Coseno   : " + str(x*K))
print ("Seno       : " + str(y*K))
----------------------------
Per calcolare la tangente e' sufficiente dividere y per x
i valori di x ed y, devono essere invece moltiplicati per un valore che deriva da

k = k*math.cos(math.atan(di * 2.0**(-i)))

e converge abbastanza rapidamente al valore di 0.6072529350088812561694
Visto che tale valore e' costante ed indipendente dalla rotazione lo si puo' inserire come una costante senza necessariamente ricalcolarlo ogni volta 

Di seguito l'output del programma

----------------------------
 n      x         y         k        z
 0 1.000000 1.000000 0.707107 0.436332
 1 0.500000 1.500000 0.632456 -0.027316
 2 0.875000 1.375000 0.613572 0.217663
 3 0.703125 1.484375 0.608834 0.093308
 4 0.610352 1.528320 0.607648 0.030889
 5 0.562592 1.547394 0.607352 -0.000351
 6 0.586770 1.538603 0.607278 0.015273
 7 0.574749 1.543187 0.607259 0.007461
 8 0.568721 1.545433 0.607254 0.003554
 9 0.565703 1.546543 0.607253 0.001601
10 0.564192 1.547096 0.607253 0.000625
11 0.563437 1.547371 0.607253 0.000136
12 0.563059 1.547509 0.607253 -0.000108
13 0.563248 1.547440 0.607253 0.000014
14 0.563154 1.547474 0.607253 -0.000047
15 0.563201 1.547457 0.607253 -0.000016
16 0.563225 1.547449 0.607253 -0.000001
17 0.563236 1.547444 0.607253 0.000007
18 0.563230 1.547447 0.607253 0.000003

Tangente : 2.7474483008390256

Coseno   : 0.3420233441629116
Seno     : 0.9396914557676728
----------------------------

Per concludere l'algoritmo dovrebbe riscritto in matematica intera per avere i massimi benefici in termini di velocita'

Nessun commento:

Posta un commento

Alpine Linux 2024 su IBM A31

Ho provato a far resuscitare un IBM A31 destinato alla discarica. La macchina ha processore P4, 256 Mb di RAM, la batteria CMOS morta ed e&#...