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)

Temel İşlem Etkinlikleri (PDF)

Matematikteki dört temel işlem toplama, çıkarma, çarpma ve bölmedir. Bu işlem becerisinin iyi derecede olması, diğer konuların da rahatlıkla öğrenilmesine zemin hazırlayacaktır. Bu nedenle ortaokul veya lise eğitimine yeni başlayan tüm öğrencilerin, geçmiş öğrenim dönemlerine ait toplama, çıkarma, çarpma, bölme..vb temel işlem yeteneklerine ait becerilerini sağlamlaştırması gerekir. Bunun için ilgili konu başlıklarından yeterince sorunun olduğu alıştırma dosyaları aşağıdaki bağlantıdan indirilerek kullanılabilir. Alıştırma sayfaları basitten zora doğru belli bir düzen halinde sırayla hazırlanmıştır. Eksik olduğunuz kısımların çıktısını alıp çözerek işlem yeteneğinizi arttırabilirsiniz.

Toplama İşlemi (4 basamaklı + 4 basamaklı, çözümlü 12 sayfa 6*50=300 işlem)

Çıkarma İşlemi (4 basamaklı - 4 basamaklı, çözümlü, 12 sayfa 6*50=300 işlem)

Toplama İşlemi (Verilmeyenli toplama, 10 sayfa 10*50=500 işlem)

Çıkarma İşlemi (Verilmeyenli çıkarma, 10 sayfa 10*50=500 işlem)

Çarpma İşlemi (Eldeli, 1-2-3-4 basamaklı, 20 sayfa 950 işlem)

Çarpma İşlemi (Bilinmeyenli çarpma işlemleri, 1-2-3-4 basamaklı, 25 sayfa 1150 işlem)

Çarpma İşlemi (4 basamaklı * 2-3-4 basamaklı, çözümlü, 20 sayfa 10*50=500 işlem)

Bölme işlemi (1-2-3-4-5 basamaklı, çözümlü, 20 sayfa 20*35=700 işlem)

Bölme işlemi (1-2-3-4-5 basamaklı, 22 sayfa 22*50=1100 işlem)

Rasyonel sayılarda işlemler (Toplama, çıkarma, çarpma, bölme tamsayılı kesir dönüştürme, bileşik kesir çevirme, 13 sayfa, 780 işlem)

 

Ritmik sayma işlemleri, (ikişer, üçer, dörder.....onar düzenli katlı/ düzensiz katlı ileriye veya geriye doğru artan/azalan sayı dizilerinden ritmik sayma alıştırmaları, 19 sayfa)

 

Ölçü birimleri ( Uzunluk ölçüleri, kütle ölçüleri, sıvı ölçüleri, 5 sayfa)

Çapma İşlemi (Çin-Hint Metodu)

Çarpma, temel matematik işlemlerinden biridir. Sayılarda çarpma, çarpılan sayının çarpan sayı kadar adedinin toplamının alınması işlemidir. Aslında özel olarak bir toplama işlemidir. Çapma işlemi belli adetteki sayıların toplanmasının adıdır. Abaküs üzerinden toplama işlemleri yapılabildiği gibi çarpma işlemi de mental aritmetik metotlarıyla yapılabilir. 

Farklı bir çarpma yöntemi olarak Çinliler tarafından sıklıkla kullanılan tablo yöntemini anlatmak istiyorum. Bunun için çarpılacak sayılar satır ve sütun halinde kolonlara yazılır. Daha sonra satırdaki rakam ile sütundaki rakam tek tek çarpılarak altında yer alan kutucuğa birler ve onlar basamağı ayrı olacak şekilde iki bölmeli olarak yazılır. Bu şekilde bütün çarpma yapıldıktan sonra çaprazlama olarak bütün çarpım sonuçları altta gelecek şekilde toplanarak elde edilen sayılar bir kenara yazılır. Bu sayılar içerisinde 10 tabanını geçenler varsa bunlar elde olarak bir sonraki rakama devredilir. Bu şekilde çarpma işlemi bitirilmiş olur.

Örnek: Tablo üzerinden de gösterildiği gibi 45 x 256 = 11.520 işleminin Çin metodu ile çözümünü bulalım.
Bu yöntemde çarpılacak sayılar basamaklarına ayrılarak sütun ve satır başlarına yazılır. Her bir kutu çaprazlamasına ikiye bölünür. Satır ile sütunların çarpımları iki üçgen bölüme birler ve onlar basamağı ayrı olacak biçimde yerleştirilir. Örneğin şekilde 5 ve 2'nin çarpımı (10) 1 ve 0 olarak ilk iki üçgene sırasıyla yerleştirilir. Daha sonra çapraz kolonlar birbiriyle toplanır. Örneğin 5 + 3 + 4 = 12 işleminin birler basamağı olan 2 rakamı en sağa yazılır ve 1 rakamı elde olarak hemen solundaki çapraz kolona devreder. Toplamaların tamamı bu şekilde tamamlandıktan sonra en dıştan başlanarak soldan sağa rakamlar (koyu yazılanlar) işlemin sonucu 11520 sayısını verir.

İşlemin Youtube Videosundan farklı örnekleri inceleyebilirsiniz. https://www.youtube.com/watch?v=DMAAAgXTEeE

Çarpma İşlemi (Çin/Japon Metodu)

Japon ve Çin dünyasında sıklıkla kullanılan bir başka çarpma yöntemini daha şu şekilde paylaşmak istiyorum. “Chinese Stick Multiplication” adıyla bilinen ve çubuklar yardımıyla yapılan Çin/Japan çarpma tekniği geleneksel çarpma yöntemlerine etkili bir alternatif yöntem sunar.Yöntemin temelleri oldukça basittir ve günümüzde kullandığımız çarpma algoritmalarına benzer şekilde çalışır. Ancak en büyük avantajı, çarpma işlemini görselleştirme imkânı sunmasıdır. Özellikle ilkokul kademesinde eğlencelidir. Eskiden Çin, Japon coğrafyasında tahta çubuklar, kemik parçaları, bambu dalları gibi araçlar yardımıyla bu çarpma işlemi yapılmıştır. Çarpma işleminin görselliği ve eğlenceli özelliği sayesinde özellikle öğrenme sürecinde oldukça etkili bir araç olduğu gözlemlenmiştir. Bu yöntem, ilköğretim düzeyinde çocuklara çarpma kavramını daha iyi kavratmak amacıyla halen belli bölgelerde öğretilmektedir. Ayrıca, yöntemin öğrenme üzerindeki olumlu etkileri yapılan araştırmalarla desteklenmiştir. 

Bu çarpma yönteminde her sayı için bir düz çizgi çizilir. Yalnız basamaklarına göre uygun biçimde aralarında boşluk bırakmadan kaç rakamı varsa o sayıda yan yana düz çizgi çizilir. Daha sonra ikinci sayı için de aynı şekilde diğer çizgileri kesecek bir şekilde ters yönde düz çizgiler basamaklarda yer alan rakamların adedine göre çizilir. Bütün bu çizme işlemi bittikten sonra altta gelen çizgilerdeki tüm kesişim noktalarının tamamının adedi toplanarak çarpma işleminin sonucu bulunur.  Eğer sayılar iki ya da daha fazla basamaktan oluşan kesişim noktası verirse bunların sadece birler basamağı yazılır. Diğer basamakları elde olarak bir sonrakine devredilir. Bu şekilde sağdan sola doğru çarpma işlemi yapılarak elde edilen noktaların sayısına göre işlem bitirilmiş olur. 

Örnek: 98*67=6566 işleminin sonucunu bu çarpma metoduna göre çizerek bulalım.

 

Örnek: 321*123=39483 işleminin sonucunu bu çarpma metoduna göre çizerek bulalım. İşlemde eldeli toplamanın nasıl yapıldığını görelim. Aşağıdaki görselde her bir basamak, renkli bir çubukla gösterilerek metodun daha kolay kavranması amaçlanmıştır. 

 

Örnek: 102*23=2346 işleminin sonucunu bu çarpma metoduna göre çizerek bulalım. İşlemde basamakların hehangi birinde 0 olduğunda buna ait olan çizgi kırmızı ile çizilir fakat işlemin sonucunda toplama işleminde bu sonuçlar toplanmadan diğer noktalar sayılar işlemin sonucu hesaplanır. Aşağıdaki görselde her bir basamak, renkli bir çubukla gösterilerek metodun daha kolay kavranması amaçlanmıştır. 

“Chinese Stick Multiplication” çarpma metodu, özellikle küçük çocuklara çarpma işleminin temellerini öğretmek açısından oldukça değerlidir. Ancak büyük basamaklı sayılarla uğraşırken bu yöntem çizgi çizmenin zorluğu nedeniyle pek kullanışlı değildir. İşlemin farklı örnekleri için orjinal youtube videosunu aşağıdaki adresten izleyebilirsiniz.

 

 

 “Chinese Stick Multiplication”

Büyük basamaklı sayılarda çarpma işlemi yapılırken Rus Matematikçi Anatoly Karatsuba tarafından bulunan ve büyük basamaklı sayıların çarpımını hesaplamada daha kullanışlı olan bir çarpım algoritması tercih edilir. Karatsuba Algoritması'nda amaç; çarpılacak sayıları alt gruplara bölerek daha az sayıda işlem yaparak sonuca en kısa yoldan ulaşmaktır.

“Chinese Stick Multiplication” Youtube Video Adresi https://www.youtube.com/watch?v=AiOKSpGs758

“Chinese Stick Multiplication” Youtube Video Adresi https://youtu.be/scCfeJhJ2TA?si=uLwXNDsBLtMcGv9S