İlkokul öğrencileri tek basamaklı sayıların çarpım tablosunu ezberleyebilir. Ancak öğretmen üç basamaklı sayıları çarpmalarını istediğinde ezber artık işe yaramaz. Bunun için bir algoritma kullanmaları gerekir. Öğrenciler sayılardan birini diğerinin altına yazar ve alttaki sayının her basamağını üstteki sayının her basamağıyla çarpar.
Matematikçiler binlerce yıl boyunca bunun mümkün olan en hızlı çarpma yöntemi olduğuna inanıyordu. Ta ki 1960 yılında, 23 yaşındaki bir genç şaşırtıcı bir keşif yapana kadar. Bu keşif, günümüzde hâlâ çözülememiş bir gizemin başlangıcı oldu.
Bu gizem, dijital dünyayla ilişkisi olan herkes için önem taşır. Çünkü çarpma işlemi bilgisayarların temel işlemlerinden biridir. Şifreleme, robotik, yapay zekâ, ses işleme ve silikon çiplere yaptırdığımız hemen her şey, kimi zaman son derece büyük sayıların tekrar tekrar çarpılmasını gerektirir.
Büyük ölçekte en basit işlem bile sistemi yavaşlatan bir darboğaza dönüşür. Bu nedenle küçük bir verim artışı bile dünya ekonomisi üzerinde büyük sonuçlara neden olur. Bunun nedenini anlamak için okulda öğrendiğimiz çarpma algoritmasının sayıların büyüklüğüne nasıl tepki verdiğine bakalım.
Çarpma İşleminin Hızı Nasıl Belirlenir?
İki basamaklı iki sayıyı çarptığınızda dört tek basamaklı çarpma işlemi yaparsınız. Üç basamaklı iki sayıya geçtiğinizde bu sayı dokuza çıkar. Başka bir deyişle işlem yükü, basamak sayısının karesiyle artar. Sayıların basamak sayısını n ile gösterirsek, gereken işlem miktarı yaklaşık n2 olur.
Bilgisayar biliminde bu büyüme biçimi Büyük O gösterimi ile ifade edilir. Okulda öğrendiğimiz çarpma algoritması için bu değer O(n2) biçimindedir ve “n kare mertebesi” diye okunur.
Kabaca söylemek gerekirse, sayıların basamak sayısı iki katına çıktığında gereken hesaplama miktarı dört katına çıkar. Sayılar bin kat uzarsa işlem yükü de bir milyon kat artar.
Antik Çağ’dan beri matematikçiler, O(n2) sınırının çarpma işlemi için aşılamaz olduğunu düşünüyordu. Ünlü Sovyet matematikçi Andrey Kolmogorov da bu görüşü resmî bir varsayım haline getirdi ve 1960 yılında Moskova Devlet Üniversitesi’nde verdiği bir seminerde dile getirdi.
Matematikçiler bir varsayım ortaya attığında, aslında ortaya bir hedef koymuş olurlar. Bundan sonra başkaları ya bu varsayımı kanıtlamaya ya da yanlışlamaya çalışır. Kolmogorov’un varsayımını çürütmek ise yalnızca bir hafta sürdü.
Semineri dinleyen 23 yaşındaki öğrenci Anatoly Karatsuba, kısa süre sonra Kolmogorov’a geri dönerek onun yanıldığını gösterdi. Kolmogorov bu sonuç karşısında oldukça şaşırdı. Ardından kanıtı kendisi kaleme aldı ve Karatsuba’yı başyazar olarak göstererek Sovyetler Birliği Bilimler Akademisi’nin dergisine gönderdi. Karatsuba ise çalışmanın yayımlandığını, basılı kopyalar kendisine ulaştığında öğrendi.
Anatoly Alekseyeviç Karatsuba, bu keşiften sonra çalışmalarını matematik alanında sürdürdü. Moskova Devlet Üniversitesi’nde eğitimini tamamladı, 1966’da bilim doktorasını aldı ve daha sonra Steklov Matematik Enstitüsü’nde çalıştı. Hayatı boyunca 160’tan fazla bilimsel çalışma ve kitap yayımladı.
Hızlı çarpma algoritması onun en çok tanınan keşfi olsa da daha sonraki kariyerinin asıl ağırlığını sayı teorisi oluşturdu. Çalışmaları nedeniyle Sovyetler Birliği Bilimler Akademisinin Çebışev Ödülü’nü ve Rusya Bilimler Akademisinin Vinogradov Ödülü’nü aldı
Karatsuba Yöntemi İle Çarpma İşlemi Nasıl Yapılır?
Karatsuba’nın asıl başarısı, zaman alan çarpma işlemlerinin bir kısmını daha hızlı toplama işlemleriyle değiştirebileceğini fark etmesiydi. Karatsuba’nın bunu nasıl başardığını küçük bir örnek üzerinde görelim.
Örnek olarak 12×34 işlemini ele alalım. Önce sayıları (10a+b)(10c+d) biçiminde düşünelim ve dağılma özelliği yardımı ile parantezleri açalım. Son durumda 100ac+10(ad+bc)+bd ifadesini elde ederiz.
Bu hepimizin bildiği yöntemdir ve ac=3, ad=4, bc=6, bd=8 biçiminde 4 defa çarpma işlemi yapmayı gerektirir. Ancak, Karatsuba tam bu noktada dikkat çekici bir cebirsel hile kullandı. İlk ve son terimler olan ac ile bd hesaplandıktan sonra, ortadaki ad+bc terimini iki ayrı çarpma yerine tek bir çarpma yardımıyla bulabileceğimizi fark etti. Bu nedenle ad+bc=(a+b)(c+d)−ac−bd eşitliğini kullandı.
Böylece ad ve bc değerlerini ayrı ayrı hesaplamaya gerek kalmaz, ac ve bd zaten bilindiği için yalnızca bir ek çarpma işlemi yeterlidir. Sonuçta dört çarpma yerine üç çarpma yapılır. Değerleri ana ifadede yerine koyduğumuzda da 100(3)+10(10)+8=408 sonucunu elde ederiz.
Küçük sayılarda tek bir çarpma işleminden tasarruf etmek önemsizdir. Ancak sayılar büyüdükçe bu tasarruf katlanarak artar. Örneğin geleneksel yöntemle 16 tek basamaklı çarpma gerektiren bir işlem, Karatsuba yöntemiyle yalnızca dokuz çarpmada hesaplanır. Bu nedenle Karatsuba algoritmasının çalışma süresi yaklaşık olarak O(n1.585) olur. Bu, geleneksel yöntemin O(n2) süresinden belirgin biçimde daha hızlıdır.
Aradaki farkı görmek için bin basamaklı iki sayıyı düşünelim. Okulda öğrendiğimiz yöntem yaklaşık bir milyon tek basamaklı çarpma gerektirirken, Karatsuba algoritması aynı işlemi 57 binden daha az çarpmayla tamamlar.
Çarpma İşlemini Daha Hızlı Yapmak İçin Yeni Yöntemler
Karatsuba’nın 23 yaşındayken geliştirdiği yöntem, bugün bazı yazılımlarda hâlâ kullanılıyor. Ancak algoritma her durumda daha hızlı değildir. Sayıları parçalara ayırmak ve sonuçları yeniden birleştirmek de zaman aldığı için küçük sayılarda geleneksel çarpma yöntemi daha kullanışlıdır. Karatsuba algoritması ancak sayılar yeterince büyüdüğünde avantaj sağlar.
Örneğin Python, küçük sayılarda okulda öğrendiğimiz çarpma yöntemini kullanır. Sayılar çok büyüdüğünde ise Karatsuba algoritmasına geçer. Böylece yazılım, sayının büyüklüğüne göre en uygun yöntemi seçer.
Karatsuba’nın keşfi, matematikçileri daha hızlı çarpma yöntemleri aramaya yöneltti. Bu arayış 2019’da önemli bir sonuca ulaştı. David Harvey ve Joris van der Hoeven, çok büyük sayıları Karatsuba yönteminden de hızlı çarpan yeni bir algoritma geliştirdi. Bu algoritmanın çalışma süresi yaklaşık olarak O(n.logn) kadardır.
Çarpma İşlemi İçin Bir Sınıra Ulaştık mı?
Ancak bu algoritmanın pratik bir sorunu vardır. Karatsuba yöntemi yalnızca büyük sayılarda hız kazanırken, bu yeni yöntem ancak akıl almayacak kadar büyük sayılarda avantaj sağlar. Bilgisayar biliminde bu tür yöntemlere “galaktik algoritma” denir. Teorik olarak çok hızlıdırlar, fakat günlük hesaplamalarda işe yarayacak kadar küçük sayılarda avantaj sunmazlar.
Yine de bu çalışma, çarpma işlemi için bilinen en hızlı yöntemi ortaya koydu. Bugün birçok araştırmacı, O(nlogn) hızının çarpma için ulaşılabilecek en iyi sınır olabileceğini düşünüyor. Fakat bunu kesin biçimde kanıtlayan kimse henüz yok. Bu nedenle çarpmanın gerçek hız sınırı hâlâ çözülmemiş bir matematik problemi olarak duruyor.
Okumak isterseniz: Çarpma Yapmanın İki Yolu: Rus Ve Antik Mısır Çarpımı
Kaynaklar ve İleri Okuma:
- Mathematicians Discover the Perfect Way to Multiply. Yayınlanma tarihi: 11 Nisan 2019; Kaynak site: Quanta Magazine. Bağlantı: Mathematicians Discover the Perfect Way to Multiply/
- This Guy Just Found a Faster Way to Multiply. Yayınlanma tarihi: 19 Ekim 2019. Kaynak site: Popular Mechanics. Bağlantı: This Guy Just Found a Faster Way to Multiply/
- Schönhage, A., Strassen, V. Schnelle Multiplikation großer Zahlen. Computing 7, 281–292 (1971). https://doi.org/10.1007/BF02242355
- Fürer, Martin. (2009). Faster Integer Multiplication. Proceedings of the Annual ACM Symposium on Theory of Computing. 39. 10.1137/070711761.
Matematiksel
