Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Çarpma algoritmaları, çarpma işlemi için gereken sonlu işlemler kümesidir. Çarpma işlemi, aritmetik işlemlerinde sık kullanılan ve bilimsel uygulamalarda önemli rolü olan, temeli aslında toplama ve kaydırma işlemlerine dayanan aritmetiksel bir işlemdir. Toplama işleminden daha karmaşıktır ve daha çok zaman alır aynı zamanda daha çok alan gerektirir.
Bilimsel programdaki komutların hemen hemen %9’u çarpma işlemi gerektirmektedir. Çarpma işlemi bir işlemcide 2 ile 8 saat çevrimi arası kadar bir zamanda yapılabilir. Bu yüzden, bir işlemcinin başarımını belirleyen en kritik ve önemli faktörlerden biri de çarpma algoritmalarının iyileştirilmesiyle birlikte bunların donanımda hızlı ve etkin uygulamasıdır.
Çarpma yöntemleri
Sıralı toplama/Kaydırma çarpma algoritması
Sıralı toplama/kaydırma algoritmasının temelinde çarpan sayısının en anlamsız basamağının bitinin değerine bakılır.
Çarpma algoritması 1. yol
Çarpma algoritmalarından ilkinin yapılabilmesi için 64-bit çarpılan yazmacı, 64-bit AMB, 64-bit çarpım yazmacı, 32-bit çarpan yazmacı gerekmektedir. Bu algoritmanın çalışması için sağ taraftaki gibi bir donanıma ihtiyacı vardır. Algoritma genel olarak şu şekilde çalışmaktadır (n değeri 32 olarak alınmıştır): Her bir saat çevriminde çarpan bir bit sağa kaydırılır ve bu bitin değeri dikkate alınır. Son bit eğer '1' ise çarpılan değer çarpıma eklenir ve sonuç çarpım yazmacına yazılır. Bu işlemden sonra çarpılan yazmacı sola 1 bit kaydırılırken, çarpan yazmacını da sağa 1 bit kaydırılır. Çarpılan kaydırılırken sağına sıfırlar eklemeyi de unutmamak gerekir. Ancak ilk aşamada kontrol edilen çarpan yazmacının son biti '0' ise o zaman sadece çarpılan yazmacı sola 1 bit kaydırılırken, çarpan yazmacını da sağa 1 bit kaydırılır. Aşağıdaki kısa örnek algoritmanın nasıl işlediği hakkında bilgi vermektedir.
Yukarıdaki örnekte de görüldüğü gibi çarpan sayısının son biti 1'dir. Bu sebepten algoritma sol taraftaki yolu izler ve çarpılan sayı (0000 0010) çarpıma eklenir, böylece ikinci satırdaki çarpım sonucu bulunur, daha sonra çarpılan yazmacı 1 bit sola kaydırılır ve 2. satırdaki sonuç (0000 0100) elde edilmiş olur. Aynı şekilde algoritmayı takip edecek olursak çarpan yazmacı da sağa 1 bit kaydırılır ve ikinci satırdaki 0001 sonucu elde edilir. Yine aynı şekilde ikinci satırda da çarpan değerinin son biti 1 olduğu için aynı yöntem uygulanır; böylece üçüncü satırı elde etmiş oluruz. Üçüncü satırda çarpan bitinin 0 olduğu görülmektedir bu sebepten algoritmayı uygularken, algoritmanın sol kolu takip edilir ve çarpım yazmacına herhangi bir değer eklemeyeceğimizden bu sonucu değiştirmez ve aynen kalır; dolayısıyla çarpan yazmacı sürekli 0000 lardan oluşacağı için yani her defasında son biti 0 olacağı için sonuç aynı kalır.
Çarpma algoritması 2. yol
Bu algoritmalarda ikincisinin yapılabilmesi için ise 32-bit çarpılan yazmacı, 32-bit AMB, 64-bit sonuç yazmacı, 32-bit çarpan yazmacı gerekmektedir. Algoritmanın işleyişi aşağıdaki gibidir: İlk yolda olduğu gibi yine çarpan yazmacının son bitine bakılır. Son bit eğer '1' ise çarpılanla çarpımın sol yarısı toplanır ve sonuç çarpım yazmacının sol yarısına yazılır. Bu işlemden sonra çarpım yazmacı sağa 1 bit kaydırılırken çarpan yazmacı da sağa 1 bit kaydırılır. Son bit '0' ise herhangi bir işlem yapılmaksızın yine çarpım yazmacı sağa 1 bit kaydırılırken çarpan yazmacı da sağa 1 bit kaydırılır. Sonuç olarak çarpım yazmacı çarpanın boyutu kadar bir alanı israf eder. Çarpım yazmacının israf edilen alanı azaldıkça çarpandaki geri kalan bitlerin sayısı da azalır. Daha sonrasında ise n değeri kontrol edilir ve eğer 32'den küçükse döngü devam eder, değilse döngüden çıkar. Kısacası algoritmada n değeri 32 alındığı için bu algoritma 32 kez tekrarlanacaktır.
Çarpma algoritması 3. yol
Çarpma algoritmalarının 3. yolunda 32-bit çarpılan yazmacı, 32 -bit AMB, 64-bit çarpım yazmacı, (0-bit çarpan yazmacı) gerekmektedir. Algoritmanın işleyişi ise şu şekilde çalışmaktadır: Her bir saat çevriminde çarpım bir bit sağa kaydırılır ve bu bitin değeri test edilir. Çarpım yazmacının son bitinin değeri '0' ise sadece kaydırma işlemi gerçekleşirken, bitin değeri '1' ise çarpılan sayının değeri çarpımın sol yarısına eklenir ve sonuç çarpım yazmacının sol yarısına yazıldıktan sonra değeri bir bit sağa kaydırılır. Çarpan sayının tüm bitleri test edildikten sonra 2n uzunluğunda sonuç elde edilir. Burada gecikme değeri en fazla n çevrim zamanı kadar olur.
Resim galerisi
-
![image]()
Çarpma algoritması 1. yol -
![image]()
Çarpma algoritması 1. yol -
![image]()
Çarpma algoritması 2. yol -
![image]()
Çarpma algoritması 2. yol -
![image]()
Çarpma algoritması 3. yol -
![image]()
Çarpma algoritması 3. yol
Kaynakça
- ^ "Strassen algorithm for polynomial multiplication". everything2. 10 Ağustos 2016 tarihinde kaynağından . Erişim tarihi: 10 Eylül 2013.
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Carpma algoritmalari carpma islemi icin gereken sonlu islemler kumesidir Carpma islemi aritmetik islemlerinde sik kullanilan ve bilimsel uygulamalarda onemli rolu olan temeli aslinda toplama ve kaydirma islemlerine dayanan aritmetiksel bir islemdir Toplama isleminden daha karmasiktir ve daha cok zaman alir ayni zamanda daha cok alan gerektirir Bilimsel programdaki komutlarin hemen hemen 9 u carpma islemi gerektirmektedir Carpma islemi bir islemcide 2 ile 8 saat cevrimi arasi kadar bir zamanda yapilabilir Bu yuzden bir islemcinin basarimini belirleyen en kritik ve onemli faktorlerden biri de carpma algoritmalarinin iyilestirilmesiyle birlikte bunlarin donanimda hizli ve etkin uygulamasidir Carpma yontemleriSirali toplama Kaydirma carpma algoritmasi Sirali toplama kaydirma algoritmasinin temelinde carpan sayisinin en anlamsiz basamaginin bitinin degerine bakilir Carpma algoritmasi 1 yol Carpma algoritmasi 1 yol Carpma algoritmalarindan ilkinin yapilabilmesi icin 64 bit carpilan yazmaci 64 bit AMB 64 bit carpim yazmaci 32 bit carpan yazmaci gerekmektedir Bu algoritmanin calismasi icin sag taraftaki gibi bir donanima ihtiyaci vardir Algoritma genel olarak su sekilde calismaktadir n degeri 32 olarak alinmistir Her bir saat cevriminde carpan bir bit saga kaydirilir ve bu bitin degeri dikkate alinir Son bit eger 1 ise carpilan deger carpima eklenir ve sonuc carpim yazmacina yazilir Bu islemden sonra carpilan yazmaci sola 1 bit kaydirilirken carpan yazmacini da saga 1 bit kaydirilir Carpilan kaydirilirken sagina sifirlar eklemeyi de unutmamak gerekir Ancak ilk asamada kontrol edilen carpan yazmacinin son biti 0 ise o zaman sadece carpilan yazmaci sola 1 bit kaydirilirken carpan yazmacini da saga 1 bit kaydirilir Asagidaki kisa ornek algoritmanin nasil isledigi hakkinda bilgi vermektedir Yukaridaki ornekte de goruldugu gibi carpan sayisinin son biti 1 dir Bu sebepten algoritma sol taraftaki yolu izler ve carpilan sayi 0000 0010 carpima eklenir boylece ikinci satirdaki carpim sonucu bulunur daha sonra carpilan yazmaci 1 bit sola kaydirilir ve 2 satirdaki sonuc 0000 0100 elde edilmis olur Ayni sekilde algoritmayi takip edecek olursak carpan yazmaci da saga 1 bit kaydirilir ve ikinci satirdaki 0001 sonucu elde edilir Yine ayni sekilde ikinci satirda da carpan degerinin son biti 1 oldugu icin ayni yontem uygulanir boylece ucuncu satiri elde etmis oluruz Ucuncu satirda carpan bitinin 0 oldugu gorulmektedir bu sebepten algoritmayi uygularken algoritmanin sol kolu takip edilir ve carpim yazmacina herhangi bir deger eklemeyecegimizden bu sonucu degistirmez ve aynen kalir dolayisiyla carpan yazmaci surekli 0000 lardan olusacagi icin yani her defasinda son biti 0 olacagi icin sonuc ayni kalir Carpma algoritmasi 2 yol Carpma algoritmasi 2 yol Bu algoritmalarda ikincisinin yapilabilmesi icin ise 32 bit carpilan yazmaci 32 bit AMB 64 bit sonuc yazmaci 32 bit carpan yazmaci gerekmektedir Algoritmanin isleyisi asagidaki gibidir Ilk yolda oldugu gibi yine carpan yazmacinin son bitine bakilir Son bit eger 1 ise carpilanla carpimin sol yarisi toplanir ve sonuc carpim yazmacinin sol yarisina yazilir Bu islemden sonra carpim yazmaci saga 1 bit kaydirilirken carpan yazmaci da saga 1 bit kaydirilir Son bit 0 ise herhangi bir islem yapilmaksizin yine carpim yazmaci saga 1 bit kaydirilirken carpan yazmaci da saga 1 bit kaydirilir Sonuc olarak carpim yazmaci carpanin boyutu kadar bir alani israf eder Carpim yazmacinin israf edilen alani azaldikca carpandaki geri kalan bitlerin sayisi da azalir Daha sonrasinda ise n degeri kontrol edilir ve eger 32 den kucukse dongu devam eder degilse donguden cikar Kisacasi algoritmada n degeri 32 alindigi icin bu algoritma 32 kez tekrarlanacaktir Carpma algoritmasi 3 yol Carpma algoritmalarinin 3 yolunda 32 bit carpilan yazmaci 32 bit AMB 64 bit carpim yazmaci 0 bit carpan yazmaci gerekmektedir Algoritmanin isleyisi ise su sekilde calismaktadir Her bir saat cevriminde carpim bir bit saga kaydirilir ve bu bitin degeri test edilir Carpim yazmacinin son bitinin degeri 0 ise sadece kaydirma islemi gerceklesirken bitin degeri 1 ise carpilan sayinin degeri carpimin sol yarisina eklenir ve sonuc carpim yazmacinin sol yarisina yazildiktan sonra degeri bir bit saga kaydirilir Carpan sayinin tum bitleri test edildikten sonra 2n uzunlugunda sonuc elde edilir Burada gecikme degeri en fazla n cevrim zamani kadar olur Resim galerisiCarpma algoritmasi 1 yol Carpma algoritmasi 1 yol Carpma algoritmasi 2 yol Carpma algoritmasi 2 yol Carpma algoritmasi 3 yol Carpma algoritmasi 3 yolKaynakca Strassen algorithm for polynomial multiplication everything2 10 Agustos 2016 tarihinde kaynagindan Erisim tarihi 10 Eylul 2013