Tesi Robotica Un coprocessore per Visual Search: Keypoint... | Page 78

4.2. SOLUZIONE ALLE PROBLEMATICHE DELL’ARCHITETTURA LUT

78

uest— oper—zione può essere eseguit— —n—log—lmente se i v—lori interi sono
r—ppresent—ti in sistem— ˜in—rio enzi™hé in sistem— de™im—leF

011011 ∗ 110110 = 000000 + 0110110 + 01101100 + 000000000 + 0110110000 +
01101100000 = 10110110010
€er g—r—ntire l9in™olonn—mento ™i si—mo serviti di zeri —ggiuntivi nell— r—ppE
resent—zioneF
†olendo e'ettu—re un— —n—lisi ™omput—zion—le dell9—lgoritmo proposto ™onE
sider—ndo l— moltipli™—zione tr— due ™ifre ˜in—rie ™ome un oper—zione element—re
™i rendi—mo ™onto ™he in tot—le —vremo un— ™omplessità tempor—le O(n2 ) ove n
è il numero di ™ifre ˜in—rie ™he ™ompongono i due numeriF
ƒem˜rere˜˜e super)uo ™er™—re di individu—re qu—l™he elemento ™he ™i permeE
tt— di ottimizz—re quest9—lgoritmoF sn fondo risult— essere un— re—ltà —ssod—t—
del9—ritmeti™—F
„utt—vi— possi—mo pens—re di ™ondurre le seguenti osserv—zioniF ƒuddividiE
—mo l— r—ppresent—zione ˜in—ri— dei numeri interi in due p—rtiF ƒpezzeremo ™osì
l— string— ˜in—ri— in ˜it di ordine —lto e in ˜it di ordine ˜—ssoF v— generi™—
string— s—rà ™osì ris™ritt—X

x = x1 ·2n/2 + x0
ed esempio

x = 1100111000111001 = 1100111000000000 + 0000000000111001
€ensi—mo di f—re l— stess— ™os— ™on —m˜edue gli interi d— moltipli™—re x e yF
†olendo — questo punto moltipli™—re tr— loro i due interi e tenendo ™onto
delle nostre osserv—zioni npossi—mo s™rivereX
n

x·y = (x12 + x0 )·(y12 + y0 ) = (x1 ·y1 )2n + (x1 ·y0 + x0 ·y1 )
2

2

2n
2

+ x0 ·y0

· y di
due numeri di n ˜it ™i—s™unoD nel pro˜lem— di ™—l™ol—re qu—ttro prodotti @xI ·
yID xI · yHD xH · yID xH · yHA di numeri di nGP ˜it ™i—s™unoF
v9 ugu—gli—nz— ridu™e il pro˜lem— di ™—l™ol—re un singolo prodotto x

eppli™—re ingenu—mente quest9—ppro™™io non ™ondurre˜˜e ™omunque —d un
miglior—mentoF iseguire i R prodotti fr— stringhe di ˜it di lunghezz— dimezz—t—
™ondurre˜˜e nuov—mente —d un— ™omplessità ™omput—zion—le O(n2 )F ymettiE
—mo l— dimostr—zione di quest— —'erm—zione in qu—nto ess— esul— d—i nostri