Karatsuba Çarpım Algoritması

Etiketler :
Çarpma işlemi, toplama işlemine göre daha karmaşık yapılı bir işlemdir. Çarpma işleminde sola kaydırma işlemi yaparak alt alta basamak sayısı kadar işlem yapılmış olur. Yani 3 basamaklı bir sayı ile 3 basamaklı bir sayı çarpılırsa 3²=9 kadar çarpma işlemi yapılır. 
4 basamaklı bir sayı ile 4 basamaklı bir sayı çarpılırsa 4²=16 kadar çarpma işlemi yapılır. 5 basamaklı bir sayı ile 5 basamaklı bir sayı çarpılırsa 5²=25 kadar çarpma işlemi yapılır. Bu şekilde devam edildiğinde n basamaklı bir sayı ile n basamaklı bir sayı çarpılırsa n² kadar çarpma işlemi yapılır. Bu nedenle klasik çarpma algoritmasında basamak sayısı arttıkça çarpım sonucunu bulmak daha zor hale gelir. Rus Matematikçi Anatoly Karatsuba, özellikle büyük basamaklı sayıların çarpımını daha kolay hesaplamak için yeni bir çarpım algoritması yazmıştır ve bu yönteme Karatsuba Algoritması adı verilmiştir. Bu algoritmada amaç; çarpılacak sayıları alt gruplara bölerek daha az sayıda işlem yaparak sonuca ulaşmaktır. 
 
Çarpma işlemi bilgisayar aritmetiğindeki en önemli işlemlerden biridir. Karatsuba algoritması, çarpma işlemini basitleştirerek işlemlerin verimliliğini arttırmak, işlem maliyetini ve süreyi azaltmak için geliştirilen algoritmalardan biridir. Klasik yöntemde n bitlik iki tamsayının toplanması O(n) bit işlemi gerektirmektedir. İki n bitlik tamsayının çarpılması ise O(n²) bit işlemi gerektirmektedir. Karatsuba algoritması iki n bitlik sayının çarpılması için böl ve fethet (divide and conquer) tekniğini kullanır ve bu algoritmada O(nlog3) bit işlemi gerekir. Karatsuba algoritması çarpma işleminde bazı çarpmaları yapmak yerine daha az maliyetli olan toplama ve çıkarma işlemleriyle değiştirerek işlem sayısını en aza indirmeyi sağlayarak işlemlerin daha hızlı sonuca ulaştırır. Karatsuba algoritması küçük basamaklı (dijit) sayılar için klasik çarpma algoritmasından daha yavaş çalışmaktayken daha büyük basamaklı sayılar için çarpma işlemi yapıldığında daha hızlı ve verimli bir sonuç sunar.
Karatsuba algoritması çarpma işlemine göre 2 basamaklı iki sayıyı çarpmak istediğimizde, önce sayıları anlamlı bloklara ayırıp işlemleri kolaylaştırırız. Yukarıda verilen akış şemasına göre önce onlar basamağındaki iki sayıyı çarparız. (A) Sonra sayıların birler basamaklarındaki sayıları çarparız. (B) Arkasından her iki sayının da basamaklarını toplayıp bunları kendi arasında çarparız.(C) Bütün sonuçlar bulunduktan sonra her iki sayının da basamaklarını toplayıp bunları kendi arasında çarptığımız sonuçtan (C) diğer bulduğumuz iki sonucu çıkartırız. D=(C-A-B). En sonunda ayırma işlemine göre bulunan A,B ve D sonuçlarını blok içinde bulunduğu onluk bölük içinde A.10n +D.10(n/2)+B biçiminde yazarak işlemi bitiririz. Burada klasik çarpmada 2 dijitli iki sayının çarpımında 2*2=4 işlem yapmak yerine sadece 3 çarpma işlemi yaparak daha kolay olan toplama ve çıkarma işlemleri ile sonuca ulaşılmış olur. Böylece bilgisayar programlamada büyük basamaklı sayılarda bu işlemleri yapmak zaman açısından daha verimli hale gelir.
Karatsuba algoritması çarpma işlemine göre 3 basamaklı (dijit) olarak verilen iki tane sayıyı çarpmak istediğimizde, önce sayıları anlamlı ikişerli uygun bloklara ayırıp işlemleri kolaylaştırırız. Yukarıda verilen akış şemasına göre önce bu bloklarda ayrı ayrı çarpma işlemi uygulayarak sonuca ulaşırız.
Karatsuba algoritması çarpma işlemine göre 4 basamaklı (dijit) olarak verilen iki tane sayıyı çarpmak istediğimizde, önce sayıları anlamlı ikişerl ikişer uygun bloklara ayırıp işlemleri kolaylaştırırız. Yukarıda verilen akış şemasına göre önce bu bloklarda ayrı ayrı çarpma işlemi uygulayarak sonuca ulaşırız.
Kaynakça
1.https://www.geeksforgeeks.org/karatsuba-algorithm-for-fast-multiplication-using-divide-and-conquer-algorithm/
2.https://brilliant.org/wiki/karatsuba-algorithm/
3.Karatsuba ve nikhilam çarpma işlemi algoritmalarının farklı bit uzunlukları için performanslarının karşılaştırılması, Can Eyüpoğlu, Ahmet Sertbaş, İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi Yıl:14 Sayı: 27 Bahar 2015 s. 55-64 

0 yorum:

Fayda vermeyen ilimden Allah'a sığınırım. “Allah'ım; bana öğrettiklerinle beni faydalandır, bana fayda sağlayacak ilimleri öğret ve ilmimi ziyadeleştir."

İlim; amel etmek ve başkalarıyla paylaşmak içindir. Niyetimiz hayır, akıbetimiz hayır olur inşallah. Dua eder, dualarınızı beklerim...

Aşağıdaki Yazılar İlginizi Çekebilir!!!

  • Matematikçiler Tarih Şeridi21.05.2014 - 5 YorumGeçmişten günümüze kadar matematikte emek sarfetmiş bilim insanlarından bazılarını, bir tarih şeridi halinde görmek istersek, aşağıdaki gibi bir pano düzenleyebiliriz. Bu tarih şeridine benzer bir çalışmayı, Matematik sınıflarımızda değerlendirerek,…
  • 2021 TYT- AYT Matematik Soru Dağılımı05.09.2021 - 0 Yorum2021 TYT Matematik sınavındaki sorular, tamamen lise müfredatı içerisinde olan konuların, yenilikçi problem tarzındaki sorulardan oluşmuştur. Önceki yıllara göre zorlayıcı soruların olduğunu kabul etmek gerekir.  Problemler ünitesi ile…
  • Berat Gecesinin Mahiyeti ve Önemi16.08.2008 - 0 Yorum Yıllık bir program çerçevesinde yürütülen ticari faaliyetler, yıl sonunda o program esaslarına göre kontrol) ve teftiş edilir. Kâr zarar hesapları yapılır. Kesin hesabın tespitinden sonra da gelecek yılın programı hazırlanarak şeklini alır. Her yıl…
  • Logaritma Mantisi ve Karakteristiği20.09.2024 - 0 YorumHerhangi bir tam sayının logaritması, birisi tam sayı diğeri de kesirli kısımdan ibaret olmak üzere iki parçadan ibarettir. Yani herhangi bir tabanda logaritma alınırken sonuç ya tamsayı olarak çıkar ya da tam ve ondalıklı kısım olarak iki parçalı…
  • Molla Lütfi ve Matematik19.04.2013 - 0 Yorum(ö.1495) 15. yüzyılda Fatih Sultan Mehmet ve II. Beyazıd dönemlerinde yaşamış meşhur matematikçilerdendir. Sinan Paşa’nın ve Ali Kuşçu’nun talebesi olmuş Ali Kuşçu’dan öğrendiği matematik bilgilerini Sinan Paşa’ya aktarmıştır. Böylece Sinan Paşa…
  • Doğruların Grafiğini Çizme14.03.2009 - 0 Yorum Doğruların Grafikleri:Doğruların grafiklerini çizmek için x ve y eksenlerini kestikleri noktalar bulunur. x eksenini kestiği nokta için y = 0 ve y eksenini kestiği nokta için x = 0 değerleri alınır. Eğer bir doğrunun eksenleri kestiği x ve y…
  • Daniel Bernoulli28.01.2011 - 0 Yorum Daniel Bernoulli (8 Şubat 1700 – 17 Mart 1782) İsviçreli matematikçi ve fizikçidir. Bernoulli ailesindeki ünlü matematikçilerdendir. Özellikle matematiği akışkan mekaniği alanına uyarlamasıyla bilinir. Olasılık ve istatistik alanındaki…
  • Kirsteen Rogers, Temel Matematik Sözlüğü 19.04.2011 - 0 YorumTemel Düzey İçin Şekilli Matematik Sözlüğü, matematiği anlamak isteyen ilköğretim çocuklarının ve ailelerinin ihtiyaT duyduğu tüm bilgileri doğrudan ve basit bir şekilde açıklamaktadır. Bu kitap, matematiksel özgüven ve başarı için çocukların sağlam…