Karatsuba Çarpım Algoritması

Etiketler : algoritma çarpma işlemi gündelik hayatta matematik

Ç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(n^log3) 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.10ⁿ +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