Yazan : Şadi Evren ŞEKER

İki tam sayının çarpımı için kullanılan algoritmalardan birisidir. Algoritma temel olarak çok haneli sayıların çarpımında hız kazandırır.

Algoritmanın çalışması

Algoritma öncelikle çarpılacak olan sayıları, alt gruplara böler. Örneğin herhangi bir x sayısı aşağıdaki şekilde yazılabilir:

x = x1Bm + x0

Buradaki B herhangi bir tabanı ve m bu tabanın herhangi bir üstünü belirtmektedir.

Örneğin 2545 sayısını ele alalım:

2545 = 23 x 102 + 45

Şeklinde yazarsak burada B = 10 ve m = 2 alınmış olur.

Aynı sayı aşağıdaki şekilde de yazılabilir:

2545 = 1 x 52 + 45

Herhangi bir sayı yukarıdaki örneklerde görüldüğü üzere farklı bir taban ve üst değeri kullanılarak yazılabilir.

Kısacası, x sayısı, x1 ve x0 olarak iki parçaya bölünmüştür.

Bu algoritmada, çarpımın yapılacağı x ve y sayılarının ikisi de aşağıdaki şekilde parçalanır.

x = x1Bm + x0

y = y1Bm + y0

Bu parçalama işleminden sonra çarpıma geçilebilir.

xy = (x1Bm + x0)(y1Bm + y0)

= x1y1B2m + (x1y0 + x0y1) Bm + x0y0

= z2B2m + z1Bm + z0

Yukarıdaki ilk satırda, çarpımı yapılmak istenen x ve y sayılarının parçalanmış hallerinin çarpımı şeklinde yazılmasını görüyoruz.

Ardından çarpım parantezler içerisine dağıtılıyor ve son olarak çarpım z2 z1 z0 terimler cinsinden yazılıyor. Bu terimleri çekecek olursak:

z2 = x1y1

z1 = x1y0 + x0y1

z0 = x0y0

Yukarıdaki z1 terimini açacak olursak aşağıdaki şekilde ilerletmemiz mümkün olur:

z1 = (x1y1 + x1y0 + x0y1 + x0y0) – x1y1x0y0 = x1y0 + x0y1

Dolayısıyla bir önceki adımda tanımlanan z2 ve z0 terimleri ile bu açılım birleştirildiğinde z1 için aşağıdaki sonuç yazılabilir

z1 = (x1 + x0)(y1 + y0) − z2z0

Örnek

Yukarıdaki çarpma işlemini bir örnek üzerinden göstermeye çalışalım.

Çarpmak istediğimiz sayılar 2543 ve 7532 olsun. Bu sayıları öncelikle parçalıyoruz:

2543 = 25 102 + 43

7532 = 75 102 + 32

Parçalama işlemi ardından sırasıyla çarpma işleminin katsayılarını buluyoruz:

z2 = 25 × 75 = 1875

z0 = 43 × 32 = 1376

z1 = (25 + 43)(75 + 32) − z2z0 = 68 × 107 − 672 − 2652 = 7276 – 1875 – 1376 = 4025

Yukarıda bulunan katsayıları sonuç denkleminde yerine yazarsak:

z2 × 102×2 + z1 × 102 + z0 = 1875 × 10000 + 4025 × 100 + 1376 = 19153876

olarak sonuç doğru bir şekilde bulunur.

Algoritmanın Analizi

Klasik bir çarpma işlemi n haneli iki sayının çarpımı için n2 işlem gerektirir. Yukarıda anlatılan karatsuba algoritması için bu işlem miktarı aşağıda verilmiştir:

Buradaki n hane için log23 çarpma işlemi gerekmesi, yukarıda bulunan her z2 z1 z0 katsayısı için sayının n/2 haneye indirilmesi ve ardından 3 adet çarpma işleminin yapılmasına dayanır.

Bu sayı n<15 için bize klasik çarpmanın daha avantajlı olduğunu gösteriyor. n=15 için yukarıdaki terimin çarpım maliyeti aşağıda hesaplanmıştır:

Görüldüğü üzere klasik yöntemle 152 = 225 değerinden daha az maliyetlidir. Aslında sayının küsuratı sayılmazsa 14 haneli sayılar için neredeyse klasik çarpma ile aynı hızdadır. Dolayısıyla n=14 için iki yöntemin aynı karmaşıklıkta olduğu söylenebilir. Ancak 14’den büyük sayılar için karatsuba çarpımı avantaj sağlayabilmektedir.

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


+ 8 = onaltı