İlkokulda öğretilen alt alta çarpma yöntemi, yüzyıllar boyunca sayıları çarpmanın en hızlı yolu sayılıyordu. Ancak 1960'ta 23 yaşında bir öğrencinin yaptığı şaşırtıcı keşif, bugüne kadar tam olarak çözülememiş bir matematik gizemini başlattı.
Bu gizem yalnızca akademik bir merak konusu değil: Şifreleme, robotik, yapay zeka, ses işleme ve bilgisayar çiplerinin üstlendiği hemen her işlem, büyük sayıların defalarca çarpılmasını gerektiriyor. Bu ölçekte en basit işlem bile bir soruna dönüşebiliyor ve küçük bir verimlilik kazanımı bile küresel ekonomik sonuçlar doğurabiliyor.
İlkokul yönteminin gizli maliyeti
İki basamaklı iki sayıyı çarparken dört, üç basamaklı sayılarda ise dokuz ayrı tek basamaklı çarpma işlemi gerekiyor; yani iş yükü basamak sayısının karesiyle büyüyor. Bilgisayar bilimciler bu büyümeyi saniye yerine işlem adımı sayısıyla, "Big O" gösterimiyle ifade ediyor: İlkokul yöntemi O(n²) adım gerektiriyor. Bu da sayılar iki katına çıktığında işin dört kat, bin katına çıktığında ise bir milyon kat artması anlamına geliyor.
Kolmogorov'un iddiasını 23 yaşında bir öğrenci çürüttü
Antik çağlardan bu yana matematikçiler, O(n²)'nin çarpma için aşılamaz bir hız sınırı olduğunu düşünüyordu. Ünlü Sovyet matematikçi Andrey Kolmogorov, 1960'ta Moskova Devlet Üniversitesi'nde verdiği bir seminerde bu sınırı resmi bir varsayım olarak ortaya attı.
Seminerde dinleyiciler arasında bulunan 23 yaşındaki üniversite öğrencisi Anatoly Karatsuba, yalnızca bir hafta sonra geri dönüp Kolmogorov'un yanıldığını kanıtladı.
Kolmogorov bu sonuç karşısında büyük şaşkınlık yaşadı, ilginç bir şekilde kanıtın resmi metnini kendisi kaleme alıp Karatsuba'yı baş yazar göstererek yayımlattı. Karatsuba, çalışmadan ancak makalenin baskılarını postada aldığında haberdar oldu.
Pahalı çarpmayı ucuz toplamayla değiştirmek
Karatsuba'nın dehası, zahmetli ve zaman alan çarpma işlemlerinin bir kısmını kolay ve hızlı toplama işlemleriyle değiştirebileceğini fark etmesinde yatıyordu. İki n basamaklı sayıyı toplamak yalnızca O(n) zaman alıyor, çünkü rakamlar üzerinde tek bir geçiş yeterli oluyor.
Sayılar onlar ve birler basamağına ayrılıyor: 12 için a=1, b=2; 34 için c=3, d=4.
Böylece 12 × 34 işlemi (10a+b) × (10c+d) olarak yazılıp açıldığında 100(ac) + 10(ad+bc) + (bd) ifadesi ortaya çıkıyor.
Geleneksel yöntemde bunun için dört ayrı çarpma gerekir: ac=3, ad=4, bc=6, bd=8. Karatsuba'nın hilesi ise ortadaki (ad+bc) terimini tek bir çarpmayla bulmayı sağlıyor:
(ad+bc) = ((a+b) × (c+d)) − ac − bd
Sayılarla: ((1+2) × (3+4)) − 3 − 8 = 21 − 11 = 10.
Yani ac=3, bd=8 ve (ad+bc)=10 değerleri yerine konduğunda sonuç yine 408 çıkıyor ama bu kez dört değil, yalnızca üç çarpma işlemiyle. Sayılar büyüdükçe bu yöntem özyinelemeli olarak tekrar tekrar uygulanabiliyor ve kazanç katlanarak artıyor.
Bu yöntem bugün birçok yazılımın temelinde yer alıyor, örneğin Python programlama dili, sayılar belirli bir büyüklüğü (yaklaşık 630 ondalık basamağı) aştığında otomatik olarak Karatsuba'nın yöntemine geçiyor.
2019'daki "galaktik" rekor
Karatsuba'nın buluşu, çarpmanın nihai hız sınırını bulmak için onlarca yıl süren bir yarışı başlattı. Bu yarış 2019'da matematikçiler David Harvey ve Joris van der Hoeven'in, önceki tüm atılımları geride bırakan son derece sofistike bir algoritma tanımlamasıyla bir dönüm noktasına ulaştı. Yeni algoritma O(n×log n) sürede çalışıyor, bu da iki devasa sayının çarpımını hesaplamanın, onları toplamaktan ya da yalnızca okumaktan çok da fazla zaman almadığı anlamına geliyor.
Ancak bu zaferin bir kısıtı var: Karatsuba'nın yöntemi yalnızca yeterince büyük sayılarda ilkokul yöntemini geride bırakırken Harvey-van der Hoeven algoritması ancak akıl almaz büyüklükteki sayılarda öne geçebiliyor. Bilgisayar biliminde böylesi yöntemlere, pratikte hiçbir zaman kullanılamayacak kadar dev sayılarda etkili olan "galaktik algoritma" deniyor.
Bununla birlikte bu, alanında çığır açan bir başarı olarak kabul ediliyor. Bugün teorik bilgisayar bilimcilerin çoğu, O(n×log n)'nin çarpma için mümkün olan en hızlı sınır olduğundan şüpheleniyor; bunu resmi olarak kanıtlamak ise matematik alanının kutsal problemi, haline geldi. Ne var ki tarih, geniş bir uzlaşının matematiksel bir kanıt anlamına gelmediğini gösteriyor çarpmanın hız sınırına dair varsayımlar daha önce de çürütülmüştü.
