Çok büyük rakamları çarpmanın yeni formülü bulundu

Güncelleme:

Avrupalı iki matematikçi, yaklaşık elli yıldır çözülemeyen bir matematik algoritmasını çözerek çok büyük sayıların çarpımıyla ilgili eski bir sorunu ortadan kaldırmış olabilirler.

Avustralya ve Fransa’dan iki matematikçi, büyük sayıları çarpmak için alternatif bir yol geliştirirken, yaklaşık yarım yüzyıl boyunca en büyük matematikçilerden bazılarının kafasını karıştıran algoritmik bir bulmacayı da çözmüş oldu. Çoğumuz açısından, nispeten küçük sayıları çarpma yolumuz zaman çizelgelerini hatırlatır; bu, yaklaşık 4 bin yıl önce Babilliler tarafından öncülük edilen inanılmaz derecede kullanışlı bir yoldur.

Peki ya sayılar büyüdüğünde ne olur? Eğer rakamlar ağırlaşırsa -ve elbette bir hesap makinemiz veya bilgisayarımız olmadığını varsayarsak- okulda öğrendiğimiz bir başka yararlı yol ve temelde iki sayıyı çarpmak için güvenilir olan bir teknik aracılığıyla, birçoğumuz uzun bir çarpma yöntemine başvururuz.

Uzun yoldan çarpmayla ilgili tek bir sorun mevcut: Bu, yavaş bir yöntem. Yavaş olmasının sebebi, problemin her bir sayısındaki her bir rakam için tüm sonuçları eklemeden önce ayrı bir çarpma işlemi gerçekleştirmeniz gerekmesi.

ZAHMETLİ YOLA KUSURSUZ BİR ALTERNATİF
Bu muhtemelen, sizin ve benim gibi nadiren uzun yoldan çarpım işlemine başvuran insanlar için bir sorun olmayabilir. Buna karşın, çocukların çarpmanın büyüsünü öğrenirken tanık olduğu olumsuz taraf, hesaplamalar sırasında zahmetli bir yolda ilerlemeleri. Daha da önemlisi bu, bilgisayarlar için de bir sorun; zira hesaplamaları gerçekleştirirken ancak bizim anlayabileceğimiz ve soyut matematiğin sınırları tarafından dayatılan, kendine has zorluklarla karşılaşıyorlar.

Temelde, uzun yoldan çarpım bir algoritmadır; fakat bu süreç kaçınılmaz biçimde zahmetli olduğu için pek de verimli değildir. Gerçekten de matematikçilerin uzun yoldan çarpmanın ne kadar zahmetli olduğunu hesaplamasının da bir yöntemi var.

Avustralya’da bulunan Yeni Güney Galler Üniversitesi’nde (UNSW) matematikçi olan David Harvey’in aşağıdaki videoda açıkladığı üzere, her iki sayının da üç basamaklı (n=3) olduğu bir çarpımda, bağlantılı çarpma işlemlerinin sayısı aslında dokuzdur, bu da n2 biçiminde ifade edilir:

Bununla ilgili sorun, sayılar büyüdükçe işin miktarının da artmasıdır ve ‘n’ her zaman ikinin kuvvetiyle temsil edilir.

GEÇMİŞTE KANITLANAMAYAN BİR TEORİ
Verimsiz olsa da uzun çarpma algoritması Rus matematikçi Anatoly Karatsuba’nın n1.58‘in mümkün olduğunu keşfettiği 1960’lara dek elimizdeki en gelişmiş çarpma algoritmasıydı. On yıl sonra, iki Alman matematikçi yeni bir sıçrama yarattı ve ‘Schönhage–Strassen Algoritması’, algoritmayı daha fazla geliştirmenin mümkün olduğunu öngörüyordu; fakat bunu asla kanıtlayamadılar.

Harvey, “Esasen, n* kök(n) temel işlemlerini kullanarak, n basamaklı sayıları çarpan bir algoritma olması gerektiğini öngördüler,” diye açıklıyor.

“Makalemiz, bunu başaran bir algoritmanın bilinen ilk örneğini sunuyor.”

Araştırmacılara göre, uzun çarpma işlemi vasıtasıyla her biri bir milyar haneye sahip olan iki sayıyı birbiriyle çarpmak, bilgisayarın bir ayını alıyor. (Aynı işlem) Schönhage-Strassen algoritması kullanıldığında 30 saniyenin altında bir sürede tamamlanabiliyor; teorik kanıtlara göre -teorik olarak- bu işlem daha hızlı gerçekleşebilir ve hatta matematiksel bağlamda mümkün olan en hızlı çarpma algoritmasını temsil edebilir.

Harvey, “Bu anlamda, çalışmamızın bu sorunlu yola bir çözüm olmasını bekliyoruz; fakat bunu tam olarak nasıl kanıtlayacağımızı şimdilik bilmiyoruz,” diyor.

“İnsanlar yaklaşık 50 yıldır böyle bir algoritmanın peşinde koşuyorlar. En nihayetinde birisinin bunu başarması beklenen bir sonuç değildi.”

Yeni algoritmanın sadece çok büyük sayıları çarpmak için yararlı olacağını belirtmek gerekiyor. Peki, tam olarak ne kadar büyük sayılardan bahsediyoruz? Araştırmacılar kendilerine sıkça sorulan bu soruya “Hiçbir fikrimiz yok” diyorlar; ancak makalelerinde verdikleri bir örnek, 10214857091104455251940635045059417341952’ye eşit ve bu gerçekten de çok büyük bir sayı.

MATEMATİK DÜNYASINDA HEYECAN YARATTI
Dünya genelindeki matematikçiler, henüz hakemli olarak gözden geçirilmemiş durumda olan ama daha şimdiden bir heyecan dalgası yaratan yeni bulguları gözden geçirmeye devam ediyor. Penn State Üniversitesi’nde teorik bilgisayar bilimci olan Martin Fürer, Science News’e verdiği demeçte “Bunun yapılabilmesi beni çok şaşırttı,” diyor.

Fürer’in kendisi de on yıl önce Schönhage-Strassen algoritmasını yenilemeye çalıştı; ancak aktardığı kadarıyla, en sonunda “Çok umutsuz görünüyordu,” diyerek algoritma üzerinde çalışmayı bıraktı. Buna karşın, matematikçilerin çalışmayı doğrulayabilmeleri kaydıyla, umut yeniden yeşerdi.

INRIA Bordeaux ve Bordeaux Matematik Enstitüsü’nde matematikçi ve bilgisayar bilimci olan Fredrik Johansson, New Scientist’e verdiği demeçte, “Eğer sonuç doğruysa, bu, ‘bilgisayımsal karmaşıklık teorisi’ açısından büyük bir başarıdır” diyor.

“Bu çalışmadaki yeni fikirlerin daha fazla araştırmaya ilham vermesi ve yöntemde pratik iyileştirmelere yol açması muhtemel görünüyor.”

Bu arada, Harvey ve Fransa’daki Politeknik Okulu’ndan araştırma ortağı Joris van der Hoeven, algoritmalarının iyileştirilmesi gerektiğini ifade ediyor ve ispatlarında bir şeylerin önünü tıkamadıklarını umuyorlar. Harvey, AAP’ye verdiği demeçte, “Birçok çalışma bizi gerçekten doğru olduğuna ikna etti,” diyor. “Ama yine de yanlış olmasından korkuyorum.”

Araştırmanın ön bulgularına HAL açık erişim sitesinden ulaşılabilir.

Yazının aslı Science Alert sitesinden alınmıştır. (Çeviren: Tarkan Tufan)