Karatsuba Çarpım Algoritması

Ç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 

 

Karatsuba Çarpım Algoritması Konu Anlatım Özetini indirmek için tıklayınız. (PDF)

W. George Horner ve Horner Yöntemi

Horner metodu, bir polinomun değerini hızlı ve etkin bir şekilde hesaplamak için kullanılan basit bir yöntemdir. Bu yöntem, özellikle yüksek dereceli polinomlarda hesaplama sırasında ortaya çıkan çok sayıda çarpma ve toplama işlemini azaltarak daha verimli bir hesaplama sağlar. Horner metodu sayesinde işlem sayısı azalır; bu da hesaplamaların daha hızlı yapılmasını ve hata olasılığının düşmesini sağlar. Bu özelliği nedeniyle, bilgisayar ve sayısal hesaplama algoritmaları açısından oldukça uygundur. Ayrıca Horner metodu, yalnızca polinom değerini bulmak için değil, polinom bölmesi veya Newton-Raphson yöntemi gibi kök bulma işlemlerinde de yaygın olarak kullanılır. 

Newton–Raphson yöntemi, bir denklemin kökünü yani f(x)=0 denklemini sağlayan x değerini bulmak için kullanılan, hızlı yakınsama özelliğine sahip bir nümerik analiz yöntemidir. Bu yöntemde, x_n noktasında fonksiyona bir teğet çizilir ve bu teğetin x-eksenini kestiği nokta bir sonraki denklemin kökü olarak tahmin ettiğimiz x_n+1 noktasını verir. Bu şekilde teğet çizilerek devam eilir. Böylece bu yöntemle, fonksiyonun grafiği üzerinde köke adım adım hızlı bir şekilde yaklaşmayı sağlar. Bu teğet çizme işlemi, ardışık adımlarla köke yeterince yaklaşılana kadar tekrarlanır. Newton yöntemi, özellikle başlangıç değeri köke yakın olarak seçildiğinde çok daha hızlı yakınsama göstereceğinden daha kullanışlı bir metod olur.
Horner metodu, İngiliz matematikçi William George Horner (9 Haziran 1786-22 Eylül 1837) tarafından akademik dünyaya kazandırılmıştır. George Horner, bilimsel yazı hayatına 1810’lu yıllarda başlamıştır. "The Ladies’ Diary" ve "The Gentleman’s Diary" gibi dönemin önemli dergilerinde çeşitli matematik problemleri yayımlamıştır. 1819 yılında, "Royal Society (Kraliyet Cemiyeti)’nin Philosophical Transactions" dergisinde yayımlanan makalesiyle Horner Yöntemini bilim dünyasına tanıtmıştır. George Horner adıyla bilim dünyasına tanıtılmış olan "Polinom Bölmesi Yöntemi", Horner’den çok önceleri, 13. yüzyılda Çinliler tarafından Zhu Shijie (ö. 1300?) adıyla bilinmekteydi. William Horner, 1819 yılında yayımladığı makalesiyle bu yöntemi Avrupa’ya tanıtmış ve polinomlarda bölme işleminin daha hızlı ve düzenli bir biçimde hesaplanmasını sağlayan bu yaklaşımı açıklamıştır. Tarihsel olarak, bu yönteme benzer fikirler Horner’dan önce Joseph-Louis Lagrange ve René Descartes gibi matematikçiler tarafından da Avrupa’da kısmen kullanılmıştır. Buna rağmen yöntemi sistematik bir hale getirip yaygınlaştıran kişi William George Horner olduğu için bu teknik onun adıyla anılmaktadır. 

Öklid Algoritması

Öklid Algoritması; (Bkz.Euclidin Hayatı) (MÖ.325-MÖ.265) tarafından bulunan kullanışlı bir bölüm işlevidir. EBOB bulma işlemlerinde genellikle asal çarpanlarına ayrılması yönteminden yararlanırız. Lakin bazı durumlarda bu asal çarpanlarına ayırma işlemi sıkıntılı olabilir. Özellikle büyük sayılar verildiğinde EBOB bulma işlemi, asal çarpan yönteminde daha zor hale gelebilir. İki tam sayının en büyük ortak bölenini bulmak için yapılan ardışık bölme işlemine öklit algoritması denir. Ardışık bölme işlemine kalan sıfır oluncaya kadar devam edilir. Sıfırdan önceki en son bölen sayı EBOB u verir. Öklid algoritmasında yapılması gereken temel mantık; ardışık olarak büyük sayıyı küçük sayıya bölerek kalanın 0 olması durumuna kadar devam edilmesidir. Bazı durumlarda kalan 0 olmayabilir bu durumlarda farklı çözüm yolları geliştirilmelidir. 

Asal Sayılar ve Bölen Durumları

Matematik öğretmeni Mehmet Arslan Hocamızın kendi el yazısı ile oluşturduğu, asal sayı ve bölen sayıları için örnek problemlerin ve özelliklerin oluşturduğu karalamaları sizinle paylaşıyoruz.Güzel el yazısı ve kısa özeti için kendisine teşekkürü bir borç biliriz. Yazımız gayet okunaklı olduğu için ayrıca bir açıklamaya gerek duymadan bu şekliyle istifade etmenizi umuyoruz.

Bölünebilme Kuralları

Bölünebilme Kuralları, matematikte sayıların 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 17, 19, 25, 36 gibi sayılara kalansız olarak bölünüp bölünemediklerini, bölme işlemi yapmadan kolayca anlamaya yardımcı olan kurallarıdır. En sık kullanılan 2, 3, 4, 5, 6, 8, 9, 10, 11 sayıları ile kalansız bölünebilme işlemleridir.  Bu sayılara tam bölünebilme için belli alışılmış kurallar vardır.