mercoledì 8 agosto 2018
martedì 7 agosto 2018
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
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
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)))
Di seguito l'output del programma
----------------------------
n x y k z
0 1.000000 1.000000 0.707107 0.436332
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'
venerdì 3 agosto 2018
Roccia lunare Milano "Goodwill Moon Rock"
Questo e' l'esemplare di roccia lunare donata da Nixon all'Italia all'interno del programma Goodwill Moon Rock (pietra dell'amicizia)
Dopo aver visto questa, il campione di Milano e' ridicolo, e' talmente piccolo che non si osserva nessuna struttura
Dopo aver visto questa, il campione di Milano e' ridicolo, e' talmente piccolo che non si osserva nessuna struttura
mercoledì 1 agosto 2018
Moltiplicazioni binarie solo con addizioni e bit shift
Una delle cose che mi ha piu' spiazzato nell'imparare l'assembler per C64 e' l'assenza nel set di istruzione del 6502/6510 di un opcode per moltiplicare. anche i soli interi
La soluzione per fare una moltiplicazione con soli addizioni e bit shift e' in realta' molto semplice usando la matematica binaria
Si parte da un esempio semplice 9 (1001b) x 8 (1000b). Se si usa la regola della moltiplicazione in colonna che si impara alle elementari
1001x
1000=
------
0000
0000
0000
1001
------------
1001000 (72d)
Come si vede quando si ha un bit zero e' inutile effettuare la moltiplicazione, se si ha un bit 1 basta ripetere il valore dell'altro moltiplicando con lo shift bit di tante posizioni quanto e' il bit del primo moltiplicatore. Un algoritmo ritrovato a questo sito riporta una variante....invece di spostare l'indice del bit di test viene effettuato sempre il testo sul bit alla posizione 0 (quella piu' sinistra) ma ogni volta viene fatto un bit shift a destra per scorrete tutto il numero. Se il bit in posizione zero e' nullo si fa uno shift a sinistra dell'altro operatore ed uno shift a destra del moltiplicatore. Se il bit alla posizione zero e' 1 allora il valore viene sommato ad una variabile accumulatore
La soluzione per fare una moltiplicazione con soli addizioni e bit shift e' in realta' molto semplice usando la matematica binaria
Si parte da un esempio semplice 9 (1001b) x 8 (1000b). Se si usa la regola della moltiplicazione in colonna che si impara alle elementari
1001x
1000=
------
0000
0000
0000
1001
------------
1001000 (72d)
Come si vede quando si ha un bit zero e' inutile effettuare la moltiplicazione, se si ha un bit 1 basta ripetere il valore dell'altro moltiplicando con lo shift bit di tante posizioni quanto e' il bit del primo moltiplicatore. Un algoritmo ritrovato a questo sito riporta una variante....invece di spostare l'indice del bit di test viene effettuato sempre il testo sul bit alla posizione 0 (quella piu' sinistra) ma ogni volta viene fatto un bit shift a destra per scorrete tutto il numero. Se il bit in posizione zero e' nullo si fa uno shift a sinistra dell'altro operatore ed uno shift a destra del moltiplicatore. Se il bit alla posizione zero e' 1 allora il valore viene sommato ad una variabile accumulatore
martedì 31 luglio 2018
Troubleshooting Kim UNO
Era un po' di tempo che ci pensavo ed alla fine mi sono comprato il kit Kim Uno, un emulatore del MOS KIM-1, microcomputer del 1975 basato sul 6502
L'emulazione viene gestita da una Arduino e non e' necessario comprare il kit.....ma la sensazione d'uso di un oggetto fisico e' sostanzialmente impossibile da ripetere solo via software
Per farmi del male (ma soprattutto per costringermi ad imparare a saldare) ho comprato il kit smontato..un PCB, 24 pulsanti (96 saldature), 11 resistenze (22 saldature), 2 moduli 3461BS (20 saldature) ed una Arduino (52 saldature)
Ovviamente le cose non potevano andare bene. L'Arduino funziona e risponde in modo coerente con all'input da tastiera ma cose si vede si sono problemi sui due moduli 3461BS
La prima cosa che risulta chiara e' che lo stesso errore viene riportato su tutti led..bisogna tirare fuori il manuale. Il modulo 3461BS effettua multiplex per poter mostrare 4 numeri con un numero minimo di collegamenti. In pratica viene scritto ed illuminato il primo numero, poi si refresha con il secondo, con il terzo e quindi con il quarto ...ad una velocita' tale che l'occhio umano non se ne rende conto. Quindi se c'e' un problema per esempio sulla barra "b" (vedi schema sottostante) questo sara' presente su tutti e quattro i digiti
Il sito riporta lo schema completo di Kim Uno
In questo modo e' stato possibile risalire quali saldature erano state fatte in modo non corretto
L'emulazione viene gestita da una Arduino e non e' necessario comprare il kit.....ma la sensazione d'uso di un oggetto fisico e' sostanzialmente impossibile da ripetere solo via software
Per farmi del male (ma soprattutto per costringermi ad imparare a saldare) ho comprato il kit smontato..un PCB, 24 pulsanti (96 saldature), 11 resistenze (22 saldature), 2 moduli 3461BS (20 saldature) ed una Arduino (52 saldature)
 |
| Test 1 |
 |
| Test 2. Come si vede risolto un problema ho fatto un danno in un altro posto |
Ovviamente le cose non potevano andare bene. L'Arduino funziona e risponde in modo coerente con all'input da tastiera ma cose si vede si sono problemi sui due moduli 3461BS
La prima cosa che risulta chiara e' che lo stesso errore viene riportato su tutti led..bisogna tirare fuori il manuale. Il modulo 3461BS effettua multiplex per poter mostrare 4 numeri con un numero minimo di collegamenti. In pratica viene scritto ed illuminato il primo numero, poi si refresha con il secondo, con il terzo e quindi con il quarto ...ad una velocita' tale che l'occhio umano non se ne rende conto. Quindi se c'e' un problema per esempio sulla barra "b" (vedi schema sottostante) questo sara' presente su tutti e quattro i digiti
Il sito riporta lo schema completo di Kim Uno
In questo modo e' stato possibile risalire quali saldature erano state fatte in modo non corretto
Iscriviti a:
Post (Atom)
Change Detection with structural similarity
L'idea di base e' quella di cercare le differenze tra le due immagini sottostanti Non e' immediatamente visibile ma ci sono dei ...
-
In questo post viene indicato come creare uno scatterplot dinamico basato da dati ripresi da un file csv (nel dettaglio il file csv e' c... -
La scheda ESP32-2432S028R monta un Esp Dev Module con uno schermo TFT a driver ILI9341 di 320x240 pixels 16 bit colore.Il sito di riferiment... -
Questo post e' a seguito di quanto gia' visto nella precedente prova Lo scopo e' sempre il solito: creare un sistema che permet...