Quater square multiplication

Un metodo per effettuare moltiplicazioni usando somme e sotttrazioni ed una tabella di lookup

La tabella di lookup e' formata dalla parte intera della divisione per 4 di quadrati dei numeri interi

---------------------------------
for i in range (20):
print (int(i*i/4))
-----------------------------------------

lookup = [0,0,1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,90]

si usa la seguente identita'

per esempio se si vuole moltiplicare x=7 per y=5 si calcola la differenza (2) e la somma (12). Si guarda nella tabella di lookup le posizioni 2 e 12 che corrispondono ai valori 1 e 36 (in pratica dalla tabella si ricavano (x +y)^2/4 e (x -y)^2/4 . A questo punto basta effettuare la sottrazione (36-1) per avere il risultato della moltiplicazione

---------------------------------
lookup = [0,0,1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,90]

m1 = 7
m2 = 5
diff = m1 - m2
somma = m1 + m2
a1 = lookup[diff]
a2 = lookup[somma]

risultato = a2 - a1
print (risultato)
---------------------------------

Una accortezza: i valori dei moltiplicatori devono essere ordinati con m1>m2

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'