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ı

Asal sayılar, yalnızca 1 ve kendisi olmak üzere iki tam sayı böleni bulunan pozitif tam sayılardır. Örneğin 2, 3, 5, 7, 11... gibi sayılar asal sayılardır. En küçük asal sayı 2’dir ve aynı zamanda 2 çift asal sayıdır; diğer tüm asal sayılar tektir. Asal sayıların sayısı sonsuzdur, bu yüzden en büyük asal sayı yoktur.

1’den 100’e kadar olan asal sayılar şunlardır: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Her 1’den büyük tam sayı ya asal bir sayıdır ya da asal sayıların çarpımı şeklinde yazılabilir. Bu asal sayılara “asal çarpanlar” denir. Örneğin 12 sayısı 2² .3 şeklinde, 21 sayısı ise 3¹.7¹ biçiminde asal çarpanlarına ayrılabilir. Bu özellik, sayıların temel yapı taşlarının asal sayılar olduğunu gösterir.

Asal sayılar, Antik Yunan matematikçileri tarafından incelenmiştir. Öklid, ünlü eseri Elementler’de asal sayılarla ilgili temel sonuçları ortaya koymuştur. Öklid, asal sayıların sonsuz olduğunu göstermiştir. Pisagor ve takipçileri sayıları daha çok felsefi açıdan incelerken, asal sayıları “saf” ve “bölünemez” yapılar olarak görmüşlerdir. Eratosthenes ise asal sayıları bulmak için “Eratosthenes Kalburu” adı verilen yöntemi geliştirmiştir. Bu yöntem, belirli bir sınıra kadar asal sayıları sistematik şekilde bulmayı sağlamıştır. Antik Mısır, Antik Çin ve Hindistan’da asal sayılar, daha çok pratik hesaplamalar ve sayıların özelliklerini anlama amacıyla incelenmiş, özellikle bölünebilme ve çarpanlara ayırma konularında önemli katkılar sağlanmıştır.

 

Asal sayılar ile Pascal Üçgeni arasında ilginç bir ilişki vardır; Pascal üçgeninde her satır, bir önceki satırdaki sayıların toplanmasıyla oluşur ve bu sayılar aslında binom katsayılarıdır. Eğer satır numarası bir asal sayıysa (örneğin 2, 3, 5, 7 gibi), o satırdaki uçlardaki 1’ler hariç tüm sayılar o asal sayıya tam bölünür. Mesela 5. satırdaki binom katsayıları: 1, 5, 10, 10, 5, 1 olup buradaki 5, 10, 10, 5 sayılarının hepsi 5’e bölünür. Bu durum sadece asal sayılar için geçerlidir. Eğer satır numarası asal değilse (örneğin 6), aynı özellik görülmez. Bu yüzden Pascal üçgeni, asal sayıları test etmek veya anlamak için matematikte kullanılan ilginç yapılardan biridir. 

İki sayının yalnızca 1 ortak böleni varsa bu sayılar “aralarında asal” olarak adlandırılır. Asal sayılar günümüzde özellikle şifreleme sistemlerinde önemli bir rol oynar; örneğin RSA yöntemi, büyük asal sayılar kullanarak dijital verilerin güvenliğini sağlar.

Asal sayılar ve bölen ilişkisi hakkında ilginç bir çalışma, bir öğretmenimiz tarafından yapılmıştır. 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.