Picproje Elektronik Sitesi

SERBEST BÖLGE => Programlama ve Algoritma => Konuyu başlatan: z - 31 Mayıs 2011, 01:21:02

Başlık: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: z - 31 Mayıs 2011, 01:21:02
Negatif sayilari, isaret degistirip pozitife cevirmeden bolebilirmisiniz?

Peki a ve b nin isaretli sayi oldugu durumlarda, a/b yi isaret degistirmeden bolebilirmisiniz?







Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: z - 31 Mayıs 2011, 02:15:16
Sanal ve bolme komutu olmayan bir islemci icin.
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: z - 31 Mayıs 2011, 02:43:39
Library kullanmadiysa bravo. Bu algoritmayi eskiden heryerde bulamazdik.

Processor ureticilerine bilgi paylastikca eksilmez desem yerler mi?
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: Burak B - 31 Mayıs 2011, 10:47:25
@bunalmis hocam siz sanırsam çarpmayla bölme ve sihirli numalar mevzundan bahsediyorsunuz. ;)

'Division via Multiplication' ve 'Computing Magic Numbers' konuları sizin isteidğinizi temin eder gibi geliyor. Basitce

x değeri için y değerine bölme yapılacaksa y değeri için belirlenen sihirli rakamlar sayesinde (Özellikle y sabit bir sayı ise) bölme kullanmadan çarpma ve sola kaydırma yaparak bu işlemi gerçekleştirebilirsiniz.

Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: z - 31 Mayıs 2011, 11:36:43
Yok oyle hazır çarpma işlemini kullanmak.

Algoritma sorusu bu.

İşaretsiz bölme algoritmasını kendi kendine oluşturamayan, ben algoritmadan anlarım algoritma yazarım demesin.

Y=A/B = (A* (2^n/B))*2^-n  zaten bilinen bir şey değilmi?
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: Burak B - 31 Mayıs 2011, 13:01:24
Hocam sorduğunuz sorularda kriterleri daha iyi belirtmelisiniz. :)

Bölme işlemi Bölenin Bölünenden sürekli çıkarılması işlemidir. Çarpmada aynı şekilde toplamadır.

17/3 işlemini 17 den 5 kez 3 çıkararak elde ederiz ve elimizde kalanımız olan 2 de bulunur ve bu negatif sayılar içinde uygulanabilir bir işlemdir.
Yine çarpma içinde aynı durum söz konusudur. 3*5 demek 5 sayısının 3 kez kendisiyle toplanması demektir.

Malum kriptolojide 1024-2048 bitlik sayılar kullanıldığı ve normalde PC'lerde  kullandığımız işlemcilerdeki yapının buna izin vermediği (istisnalar kaideyi bozmaz) düşünülürse. Büyük sayıları kullanan kütüphanelerin bunu birşekilde başarmış olmaları da incelenebilir.

Mesela çarpma için Booth abimiz ne yapmış;
http://en.wikipedia.org/wiki/Booth_encoding (http://en.wikipedia.org/wiki/Booth_encoding)




Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: z - 31 Mayıs 2011, 13:30:56
Bolme işlemini ardışıl çıkartma ile yapacaksak yandık. Mesela 1 trilyonu 3 e bölmek istesem?

2 li sistemde bölme işlemi 10 lu sistemdekinin aksine oldukça kolay fakat zaman alıcı bir işlemdir.

Ancak, sorun unsigned sayıların bölünmesi değil, signed (2's complement) sayılarda bölme işlemi.

İşin üçkağıdı;

Sayılar negatif ise pozitife çevir. İşaretsiz bölme yap. Sonra sonucu girdi işaretlerinin durumuna göre negatife çevir.

Ben harbi harbi unsigned bölme algoritmasını soruyorum.
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: The Gariban - 31 Mayıs 2011, 13:56:16
http://www.virag.si/nic/?p=10
Ayrıca kodların sonundaki "source site" linkinde daha fazla detaylar var
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: The Gariban - 31 Mayıs 2011, 14:07:34
iyide adam orada ben ARM7 için daha hızlı bir algoritma geliştirdim diyor hocam. ::)
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: Burak B - 31 Mayıs 2011, 14:20:48
Hocam size kolay gelsin;
Ayrıca verdiğim linkteki algoritmayı incelediğinize eminmisiniz ?

Etmediyseniz;
http://people.ee.duke.edu/~sorin/prior-courses/ece152-spring2009/lectures/3.3-arith.pdf (http://people.ee.duke.edu/~sorin/prior-courses/ece152-spring2009/lectures/3.3-arith.pdf)
http://www.academic.marist.edu/~jzbv/architecture/Projects/S2002/MultDiv/ComputerArch.ppt (http://www.academic.marist.edu/~jzbv/architecture/Projects/S2002/MultDiv/ComputerArch.ppt)

Bildiğiniz birşeyse aç karnınayım zaten hafif sinirli olurum ona yok buna yok benim zamanımı harcatmayın boşuna. :)
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: The Gariban - 31 Mayıs 2011, 14:22:02
Sanırım aradığınız bu
http://www.info.uni-karlsruhe.de/lehre/2003SS/asm/material/arm/arm-intro.pdf
bölme için bir işlem yapmadığını söylüyor (3.sayfanın son satırı)
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: mufitsozen - 31 Mayıs 2011, 15:05:55
bakiniz: http://focus.ti.com.cn/cn/lit/an/spra707/spra707.pdf

Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: Tagli - 31 Mayıs 2011, 15:07:47
Microchip AN526 (http://www.microchip.com/stellent/idcplg?IdcService=SS_GET_PAGE&nodeId=1824&appnote=en011000)
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: z - 31 Mayıs 2011, 15:31:28
Verilen algoritmaların alayı unsigned div.

Signed div işlemi de bahsettiğim 3 kağıtla yapılmış.
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: Burak B - 31 Mayıs 2011, 15:47:07
Alıntı Yap
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 (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.
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: z - 31 Mayıs 2011, 21:08:01
Alıntı yapılan: ByteMaster - 31 Mayıs 2011, 15:47:07
Alıntı Yap
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 (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ş.
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: z - 31 Mayıs 2011, 23:37:20
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
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: Tagli - 31 Mayıs 2011, 23:56:16
Neden özellikle işaret değiştirmeden bölme işlemi yapılmak isteniyor?
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: z - 01 Haziran 2011, 00:02:19
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.


Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: z - 09 Haziran 2011, 02:07:13
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)
Başlık: Ynt: ASM cilere kafa sorusu 'isaretli bolme' islemi
Gönderen: z - 09 Haziran 2011, 02:25:01
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 ?