Avustralya ve Fransa’dan bir çift matematikçi, yarım asırdır en büyük matematikçileri bile şaşırtan algoritmik bir bulmacayı çözerken çok basamaklı sayıların çarpımı için yeni bir yöntem keşfetti.
Çoğumuz için, nispeten küçük sayıları çarpma yolu, bundan yaklaşık 4000 yıl önce Babilliler tarafından öncülük edilen inanılmaz derecede kullanışlı olan, çarpım tablosunu hatırlamaktır.
Peki ya, sayılar büyürse?
Eğer sayılar artarsa – ve tabii ki bir hesap makinemiz ya da bilgisayarımızın olmadığını farz edersek – bu durum çoğumuz için uzun süren bir çarpım sürecine dönüşür:
Bu aşamada da okulda öğrendiğimiz en doğru ve kullanışlı olan yöntemi uygular yani basit şekilde sayıları tek tek birbirleriyle çarparız. Uzun çarpma işlemleriyle ilgili tek bir sorun var. Çok uzun sürüyorlar. İşlemlerin uzun ve yavaş olmasının nedeni, soruda her sayıdaki her rakam için ayrı ayrı çarpma işlemi yapmanız gerekmesidir.
Bu muhtemelen senin ve benim için bir sorun olmayabilir. Zaten bu uzun işlemleri çoğunlukla kendimiz için yapmıyoruz. Ama bu durum çarpmanın büyüsünü öğrendikten sonra bunu zahmetli işlemlerde kullanan öğrenciler için zaman çalan bir engeldir.
Daha da önemlisi, bu bilgisayarlar için bir problem, hesaplama performansındaki darboğazları, ancak kendimizin anlayabileceği soyut matematiğin sınırları dayatıyor.
Temel olarak, uzun çarpma işlemleri bir algoritmadır ancak bu işlem süreci özenli bir şekilde yapıldığı ve uzun sürdüğü için verimli değildir. Matematikçiler uzun çarpma işlemlerinin ne kadar zahmetli olduğunu hesaplamanın bir yolunu buluyorlar.
Avustralya’daki New South Wales Üniversitesi’nden matematikçi David Harvey’in aşağıdaki videoda açıkladığı gibi, her iki sayının da 3 basamaklı olduğu bir çarpma işleminde (n = 3), işleme dahil olan çarpım sayısı aslında 9’dur, ki bu sayı n2( kare)’dir:
Bununla ilgili sorun, sayılar büyüdükçe, ilgili iş miktarının da artacağı gerçeğidir. Bu durum her zaman n’in ikinci kuvveti şeklinde temsil edilir.
Verimsiz olmasına rağmen, uzun çarpım algoritması aslında, Rus matematikçi Anatoly Karatsuba’nın n üzeri 1.58’in mümkün olduğunu keşfettiği 1960’lara kadar sahip olduğumuz en gelişmiş çarpım algoritmasıdır.
Bundan tam 10 yıl sonra, bir çift Alman matematikçi başka bir atılımda bulundu: Schönhage – Strassen algoritması, varsayımlandı – ama hiçbir zaman kanıtlanmadı – daha fazla ayrıntılandırmanın da mümkün olduğunu kanıtladı.
Harvey, “ Algoritmada n basamaklı sayıları esasen n * log (n) temel işlemleri kullanarak çarpan bir algoritma olması gerektiğini öngördüler” diye açıklıyor.
“Makalemiz bunu gerçekleştiren ilk algoritma örneğini vermektedir.”
Araştırmacılara göre, iki sayının her biri geleneksel çarpma işlemiyle bir milyar basamakla çarpılırsa, bunun hesaplanması kullandığımız bilgisayarların bile bir ayını alacaktır.
Bu durum aslında Schönhage-Strassen algoritmasını kullanarak, 30 saniyenin altında bir zamanda sonuçlanabilir ve yeni teorik kanıtlarıyla – teoride geçerli – matematiksel olarak mümkün olan en hızlı çarpma algoritmasını bile temsil eder.
Harvey “Bu anlamda, çalışmamızın bu sorun için yolunun sonu olması bekleniyor, ancak henüz bunu nasıl bir titizlikle kanıtlayacağımızı bilmiyoruz” diyor.
“İnsanlar neredeyse 50 yıldır böyle bir algoritma arayışı içerisindeydiler. Birisinin sonunda başarılı olacağı beklenen bir sonuç değildi.”
Yeni algoritmanın yalnızca çok büyük sayıları bir araya getirmek için yararlı olacağına dikkat çekmek önemlidir. Şimdi bir soru işareti daha belirdi. Tam olarak ne kadar büyük?
Araştırmacılar bunu sıkça sorulan sorularda “Hiçbir fikrimiz yok” diye açıklıyor ancak gazetede verdikleri bir örnek 10 üzeri 214857091104455251940635045059417341952’ye eşittir ki bu çok ama çok büyük bir sayıdır.
Dünyadaki matematik topluluğu, henüz hakemli olarak gözden geçirilmemiş olsa da halihazırda dalgalanmalar yaratan yeni bulguları ilgi çekici bulmaktadır.
Pensilvanya Eyalet Üniversitesi’nden teorik bilgisayar bilimcisi Martin Fürer Science News’e “Bunun yapılmasına çok şaşırdım.” dedi. Fürer, Schönhage-Strassen algoritmasını on yıldan daha uzun bir süre önce yeniden canlandırmaya çalıştı.
Ancak sonunda Science News’a “Bana oldukça umutsuz görünüyordu” diyerek çalışmayı bıraktı.
Şimdiyse matematikçilerin bu işi doğrulayabilmesi için gereken umut yeniden sağlandı.
INRIA Bordeaux ve Institut de Mathématiques de Bordeaux’dan matematikçi ve bilgisayar uzmanı Fredrik Johansson, New Scientist’e verdiği demeçte:
“Sonuç doğruysa, bu hesaplama karmaşıklığı teorisinde büyük bir başarıdır.”
“Bu çalışmadaki yeni fikirlerin daha fazla araştırmaya ilham vermesi muhtemeldir. Bu fikirler süreç boyunca pratik gelişmelere yol gösterebilir.”
Bu arada, David Harvey ve çalışma arkadaşı Fransa’daki École Polytechnique’den Joris van der Hoeven, algoritmalarının en uygun forma getirilmesi gerektiğini düşünüyor. Ve ispatlarında doldurmadıkları ufak boşlukları tamamlamayı umuyorlar.
Harvey, The Weekend Australian’a yaptığı açıklamada,
“Çalışmaların çoğu bizi gerçekten doğru yolda olduğumuza inandırıyor ancak hala çalışmamızın yanlış olduğu ihtimalinin ortaya çıkabileceğinden korkuyorum.” dedi.
Bu çalışmayla ilgili baskı öncesi bulgulara HAL açık erişim arşivinden ulaşabilirsiniz.
Bunlar da ilginizi çekebilir:
- Adeta Matematikle Konuşan Mimar Sinan Eserleri ve Hayatı
- Anunnakiler ilk matematiksel sistem ile evrene ilişkin şifreleri mi açığa vurmak istediler?
- Arılar, temel matematik işlemlerini yapabilir
- Farkına Varmadan Her Gün Kullandığınız Matematiksel Formül: Bayes Teoremi
Editör / Yazar: O.Can CANİKLİ
Yorumlar 2