ASM cilere kafa sorusu 'isaretli bolme' islemi

[z]

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1951 while doing research on crystallography at Birkbeck College in Bloomsbury, London. Booth used desk calculators that were faster at shifting than adding and created the algorithm to increase their speed. Booth's algorithm is of interest in the study of computer architecture.

Ayrıca
http://opencourseware.kfupm.edu.sa/colleges/ccse/ics/ics233/files/2_Unit5.ppt

Sunumda tüm sorularınızın cevapları mevcut bölme ve çarpma dahil gayet basit anlatmışlar. Dediğiniz unsigned dönüşümü dahil.

Nerde hocam bu signed div algoritması. Ben mi göremiyorum?

Verilen liklerde hep unsigned div anlatılmış. İşaretli sayıların için bölmede sayılar önce pozitife çevrilmiş.

[z]

Ben mi goremiyorum?

Sayfa 27

Simplest way is to remember the signs
Convert the dividend and divisor to positive
Obtain the 2's complement if they are negative
Do the unsigned division
Compute the signs of the quotient and remainder
Quotient sign = Dividend sign XOR Divisor sign
Remainder sign = Dividend sign
Negate the quotient and remainder if their sign is negative
Obtain the 2's complement to convert them to negative

Sayfa 28

Positive Dividend and Positive Divisor
Example: +17 / +3   Quotient = +5   Remainder = +2
Positive Dividend and Negative Divisor
Example: +17 / –3    Quotient = –5   Remainder = +2
Negative Dividend and Positive Divisor
Example: –17 / +3   Quotient = –5   Remainder = –2
Negative Dividend and Negative Divisor
Example: –17 / –3   Quotient = +5   Remainder = –2
The following equation must always hold:
Dividend = Quotient × Divisor + Remainder

[Tagli]

Neden özellikle işaret değiştirmeden bölme işlemi yapılmak isteniyor?

[z]

Amaç kıllık yapmak.

İşaretli sayıları çarparken işaret değiştirmeden çarpabiliyoruz. Fakat istersek sayıları pozitif yapıp çarpıp ardından sonucun işaretini belirleyebiliyoruz.
O halde bölmede de doğrudan işaretli sayıları bölebilmeliyiz.

[z]

Hala cevap cikmadi.

Mikrolarla calismaya basladigim donemde (derleyicilerin daha dogrusu PC nin olmadigi donemden bahsediyoruz) carpma ve bolme islemi ocu gibi islemlerdi.
Kutuphanelerde bulabildigim her kitapdan carpma ve bolme algoritmalari toplayip istiflemeye basladim.

Hic birini anlamasam da hepsini ezberlemistim. Tik tik tik istedigim bit uzunlugunda carpma yada bolme icin kodlarimi yazar hale gelmistim.

Yillar sonra bu ne ayak nedir bu algoritmalarin sirri diye merak ettigimde aci gercekle karsilastim. Kafayi  kullanmamak.

Ilk okulda 10 lu sistemde carpma ve bolmeyi yapan cocuk buyuyecek universite bitirecek ama 10 lu sistemden cok ama cok daha basit 2 li sistemde carpma ve bolmeyi yapan algoritmayi anlamayacak.

Eger bu algoritmalarin nasil calistigini merak ediyorsaniz isaretsiz carpma algoritmasinin mantigini hemencecik anlatayim.


10 sayi sisteminde 123 sayisi (1x10^2)  + (2 * 10^1) + (3*10^0) yano 100+20+3 demektir yazilir.
ikili sistemde 101 sayisi (1*2^2) + (0*2^1) + (1*2^0) yani 4 + 0 + 1 = 5 demektir.

Simdi 101 sayisini 3 ile carpmak isteyelim.

uzun uzun 101+101+101 yapabilirim ama bu hos bir sey olmaz.

3=(2+1) olduguna gore  ikili sayi olani 101 ile (2+1) i carpalim.

2 ile carpmak demek 101 i bir kere sola kaydirmak demektir. 1010 oldu. Buna 101 ekleyelim 1111 oldu. yani 15  gercekten de 5*3=15 dir

Peki simdi de 101 ikili sayisini 7 ile carpalim. 7=3+4=(1+2)+4  =  101 + 1010 + 10100 = 35

1 le carpmak sayinin kendisi.
2 ile carpmak sayiyi bir kere sola kaydirmak.
4 ile carpmak sayiyi iki kere sola kaydirmak.

Amac carpani 2 nin kuvvetlerinin toplamlari seklinde yapip carpilani kuvvetler kadar kaydirmak sonrada bunlari toplamak.

Simdi carpanin A gibi bir degiskende oldugunu varsayalim. (A, 8 bit olsun)

Bu durumda A=(A7*2^7) + (A6*2^6) + (A5*2^5) + (A4*2^4) + (A3*2^3) + (A2*2^2) + (A1*2^1) + (A0*2^0) sayisini saklar.

Buradaki A7...A0 A nin bitleridir.

An,  n'inci siradaki bitin degeri olsun.

Bu durumda B sayisi ile A sayisini carpmak demek

B *  [(A7*2^7) + (A6*2^6) + (A5*2^5) + (A4*2^4) + (A3*2^3) + (A2*2^2) + (A1*2^1) + (A0*2^0)] islemin yapmak demektir.

Eger An=1 ise B sayisini n kere sola kaydir demektir.
Eger An=0 ise bir sey yapma demektir. Cunku 0*B sifirdir.

B *  (A7*2^7)
B *  (A6*2^6)
B *  (A5*2^5)
B *  (A4*2^4)
B *  (A3*2^3)
B *  (A2*2^2)
B *  (A1*2^1)
B *  (A0*2^0)

Bunlari toplarsak A*B sonucunu bulmus oluruz.

B *  A7<<7    //  A7, 1 se B yi 7 kez  kaydir 0 sa bosu bosuna ugrasma
B *  A6<<6    //  A6, 1 se B yi 6 kez  kaydir 0 sa bosu bosuna ugrasma
B *  A5<<5    //  A5, 1 se B yi 5 kez  kaydir 0 sa bosu bosuna ugrasma
B *  A4<<4    //  A4, 1 se B yi 4 kez  kaydir 0 sa bosu bosuna ugrasma
B *  A3<<3    //  A3, 1 se B yi 3 kez  kaydir 0 sa bosu bosuna ugrasma
B *  A2<<2    //  A2, 1 se B yi 2 kez  kaydir 0 sa bosu bosuna ugrasma
B *  A1<<1    //  A1, 1 se B yi 1 kez  kaydir 0 sa bosu bosuna ugrasma
B *  A0

Gordugunuz gibi cocuk oyuncagi.

Fakat yukaridaki mantigi algoritmaya donusturur yada akis diyagrami cizerseniz ve incelemesi  icin birisine verirseniz ocu gormus gibi olur.

Eger carpma algoritmasinin mantigi hosunuza gittiyse sorumdaki isaretli bolme algoritmasina lutfen kafa yorun.....

Bana da bilmem ne firmasinin bilmem ne uygulama notunu iste bu diye vermeyin. (isterlerse ben onlara yollayayim)

[z]

B *  A7<<7    //  A7, 1 se B yi 7 kez  kaydir 0 sa bosu bosuna ugrasma
B *  A6<<6    //  A6, 1 se B yi 6 kez  kaydir 0 sa bosu bosuna ugrasma
B *  A5<<5    //  A5, 1 se B yi 5 kez  kaydir 0 sa bosu bosuna ugrasma
B *  A4<<4    //  A4, 1 se B yi 4 kez  kaydir 0 sa bosu bosuna ugrasma
B *  A3<<3    //  A3, 1 se B yi 3 kez  kaydir 0 sa bosu bosuna ugrasma
B *  A2<<2    //  A2, 1 se B yi 2 kez  kaydir 0 sa bosu bosuna ugrasma
B *  A1<<1    //  A1, 1 se B yi 1 kez  kaydir 0 sa bosu bosuna ugrasma
B *  A0


Bu algoritmada A nin tum bitleri 1 ise toplamda 7+6+5+4+3+2+1 kere yani 28 kere kaydirma yapmak gerekir.

Halbuki ayni carpma islemi sadece max 8 kaydirma ile yapilabilir. Nasil ?