Karatsuba Algoritması

Sayıları Daha Hızlı Çarpmanın Yolu

Karatsuba algoritması, iki büyük sayıyı çarpmanın, klasik (veya “okul”) çarpma yönteminden daha verimli olan bir böl ve yönet (divide and conquer) algoritmasıdır. Anatolii Alexeevitch Karatsuba tarafından 1960 yılında keşfedilen bu yöntem, nn haneli iki sayıyı çarpma karmaşıklığını, geleneksel O(n2)O(n^2) yönteminden O(nlog⁡23)≈O(n1.585)O(n^{\log_2 3}) \approx O(n^{1.585}) seviyesine düşürür. Bu iyileştirme, özellikle astronomik büyüklükteki sayılarla (örneğin kriptografi ve bilgisayımlı cebirde) uğraşırken çok önemli bir hız kazancı sağlar.

Algoritmanın temel mantığı, çarpılacak sayıları daha küçük parçalara bölmek ve bu parçalar arasında yapılan birkaç çarpma işlemini, daha az sayıda toplama/çıkarma işlemiyle birleştirerek sonucu oluşturmaktır. İki nn-haneli xx ve yy sayısını çarpmak istediğimizi varsayalım. Bu sayıları, her biri n/2n/2 haneli olacak şekilde iki parçaya ayırabiliriz:

x=a⋅10m+bx = a \cdot 10^{m} + b y=c⋅10m+dy = c \cdot 10^{m} + d

Burada m=⌈n/2⌉m = \lceil n/2 \rceil, aa ve cc sayıların daha anlamlı (yüksek mertebeli) kısımlarını, bb ve dd ise daha az anlamlı (düşük mertebeli) kısımlarını temsil eder. Klasik çarpma yönteminde, bu dört parçayı birbiriyle çarparak dört çarpım yapmamız gerekir:

x⋅y=(a⋅10m+b)(c⋅10m+d)=ac⋅102m+(ad+bc)⋅10m+bdx \cdot y = (a \cdot 10^{m} + b)(c \cdot 10^{m} + d) = ac \cdot 10^{2m} + (ad + bc) \cdot 10^{m} + bd

Karasuba’nın dahice içgörüsü, bu dört çarpım yerine sadece üç çarpım yapmanın mümkün olduğunu fark etmesiydi. ad+bcad + bc terimini, (a+b)(c+d)(a+b)(c+d) çarpımını hesaplayarak dolaylı yoldan bulabiliriz:

  1. ac=a⋅cac = a \cdot c çarpımını hesapla.
  2. bd=b⋅dbd = b \cdot d çarpımını hesapla.
  3. (a+b)(c+d)=ac+ad+bc+bd(a+b)(c+d) = ac + ad + bc + bd çarpımını hesapla.
  4. (a+b)(c+d)(a+b)(c+d) değerini bulmak için, 3. adımdaki sonuçtan ilk ikisini çıkar:
ad+bc=(a+b)(c+d)−ac−bdad + bc = (a+b)(c+d) - ac - bd

Sonuç olarak, xx ve yy‘nin çarpımını sadece üç temel çarpım (ac,bdac, bd ve (a+b)(a+c)(a+b)(a+c)) kullanarak ifade edebiliriz:

x⋅y=ac⋅102m+((a+b)(c+d)−ac−bd)⋅10m+bdx \cdot y = ac \cdot 10^{2m} + ( (a+b)(c+d) - ac - bd ) \cdot 10^{m} + bd

Bu üç çarpım da orijinal sayıların yarı boyutundaki parçalarla yapıldığı için, bu yöntem özyinemeli (recursive) olarak uygulanabilir. Her özyineleme adımında problem boyutu yarıya iner ancak 3 alt probleme ayrılır. Bu da zaman karmaşıklığını O(nlog⁡23)O(n^{\log_2 3}) yapar. Bu, özellikle binlerce haneli sayılar için, O(n2)O(n^2)‘den çok daha verimli bir yoldur ve günümüzdeki en hızlı çarpma algoritmalarının (örneğin Schönhage–Strassen algoritması) temelini oluşturur.