Boothov algoritam je algoritam množenja koji nam omogućuje množenje dva binarna cijela broja s predznakom u komplementu 2, redom. Također se koristi za ubrzavanje izvedbe procesa množenja. Također je vrlo učinkovit. Radi na bitovima niza 0 u množitelju koji ne zahtijeva dodatni bit samo pomiče krajnje desne bitove niza i niz 1 u težini bita 2 množitelja^kna težinu 2^mkoji se može smatrati 2^{k+ 1}- 2^m .

Slijedi slikovni prikaz Boothovog algoritma:

U gornjem dijagramu toka, u početku, AC i Q_{n + 1} bitovi su postavljeni na 0, a SC je brojač sekvenci koji predstavlja ukupni skup bitova n, koji je jednak broju bitova u množitelju. Tamo su BR koji predstavljaju množenici bitovi, a QR predstavlja bitovi množitelja . Nakon toga, naišli smo na dva bita množitelja kao Q_ni Q_{n + 1}, gdje Qn predstavlja zadnji bit QR, a Q_{n + 1}predstavlja inkrementirani bit od Qn za 1. Pretpostavimo da su dva bita množitelja jednaka 10; to znači da moramo oduzeti množitelj od parcijalnog umnoška u akumulatoru AC i zatim izvršiti operaciju aritmetičkog pomaka (ashr). Ako su dva množitelja jednaka 01, to znači da trebamo izvršiti zbrajanje množenika djelomičnom umnošku u akumulatoru AC i zatim izvršiti operaciju aritmetičkog pomaka ( Ashr ), uključujući Q_{n + 1} . Operacija aritmetičkog pomaka koristi se u Boothovom algoritmu za pomak AC i QR bitova udesno za jedan, a bit predznaka u AC ostaje nepromijenjen. Brojač sekvenci se kontinuirano smanjuje dok se računska petlja ne ponovi, jednako broju bitova (n).

Rad na Booth algoritmu

1. Postavite binarne bitove množitelja i množitelja kao M odnosno Q.
2. U početku postavljamo AC i Q_{n + 1}registrira vrijednost na 0.
3. SC predstavlja broj bitova množitelja (Q) i to je brojač sekvenci koji se kontinuirano smanjuje dok ne bude jednak broju bitova (n) ili dosegne 0.
4. Qn predstavlja posljednji bit Q, a Q_n+1pokazuje povećani bit Qn za 1.
5. U svakom ciklusu algoritma kabine, Q_ni Q_{n + 1}Bitovi će se provjeravati na sljedećim parametrima kako slijedi:
   1. Kada dva bita Q_ni Q_{n + 1}su 00 ili 11, jednostavno izvodimo operaciju aritmetičkog pomaka udesno (ashr) na djelomični produkt AC. I bitovi Qn i Q_{n + 1}se povećava za 1 bit.
   2. Ako su bitovi Q_ni Q_{n + 1}Ako se prikazuje na 01, bitovi množenika (M) bit će dodani u AC (registar akumulatora). Nakon toga izvodimo desnu operaciju pomaka na AC i QR bitove za 1.
   3. Ako su bitovi Q_ni Q_{n + 1}ako je prikazano na 10, bitovi množenika (M) bit će oduzeti od AC (registra akumulatora). Nakon toga izvodimo desnu operaciju pomaka na AC i QR bitove za 1.
6. Operacija kontinuirano radi dok ne dosegnemo n - 1 bit u algoritmu kabine.
7. Rezultati binarnih bitova množenja bit će pohranjeni u registrima AC i QR.

U Boothovom algoritmu koriste se dvije metode:

redatelj Karan Johar

1. RSC (Kružni desni pomak)

Pomiče krajnji desni bit binarnog broja, a zatim se dodaje na početak binarnih bitova.

2. RSA (aritmetika desnog pomaka)

Dodaje dva binarna bita i zatim pomiče rezultat udesno za 1-bitnu poziciju.

niz u int u Javi

Primjer : 0100 + 0110 => 1010, nakon zbrajanja binarnog broja pomaknite svaki bit za 1 udesno i stavite prvi bit rezultante na početak novog bita.

Primjer: Pomnožite dva broja 7 i 3 koristeći Boothov algoritam množenja.

Godine . Ovdje imamo dva broja, 7 i 3. Prije svega, trebamo pretvoriti 7 i 3 u binarne brojeve poput 7 = (0111) i 3 = (0011). Sada postavite 7 (u binarnom 0111) kao množitelj (M) i 3 (u binarnom 0011) kao množitelj (Q). A SC (Sequence Count) predstavlja broj bitova, a ovdje imamo 4 bita, pa postavite SC = 4. Također, prikazuje broj ciklusa ponavljanja algoritama kabine i zatim se ciklusi pokreću SC = SC - 1 put.

Numerički primjer Boothovog algoritma množenja je 7 x 3 = 21, a binarni prikaz broja 21 je 10101. Ovdje dobivamo rezultantu u binarnom obliku 00010101. Sada ga pretvaramo u decimalni, kao (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

java referentni tipovi

Primjer: Pomnožite dva broja 23 i -9 koristeći Boothov algoritam množenja.

Ovdje je M = 23 = (010111) i Q = -9 = (110111)

Q_{n + 1} = 1, znači da je izlaz negativan.

Dakle, 23 * -9 = komplement 2 od 111100110001 => (00001100111)