Çarpma İşlemi İçin Yeni Bir Yol Keşfedildi

4000 yıl önce Babilliler tarafından keşfedilen çarpma işlemi geçtiğimiz aylarda, şu an için alabileceği en mükemmel halini aldı. İki araştırmacı çok büyük iki sayının birbiriyle çok hızlı biçimde çarpılabileceği bir yöntem geliştirdi.

Bu iki araştırmacının, matematikteki en basit işlemlerden biri olan çarpma işlemi için, en etkili yöntemi bulmanın peşine düştükleri çalışmaları uzun soluklu bir tırmanışın da doruk noktası oldu.

Fransız Ulusal Bilim Araştırmaları Merkezi’nde matematikçi olarak görev yapan ve çalışmanın ortak yazarlarından birisi olan Joris van der Hoeven konuyla ilgili yaptığı açıklamada “Herkes okulda öğrendiği yöntemin, öğrenilebilecek en iyi yöntem olduğunu düşünüyor. Oysa bu halen gelişmekte olan bir araştırma alanı.” dedi.

Gerçekten, pi sayısındaki yeni basamakları bulmaktan, büyük asal sayıları keşfetmeye kadar, karmaşık hesaplama gerektiren birçok problemin çözümü, çarpma işleminin hızına bağlı.

Van der Hoeven, bu durumu da göz önünde bulundurarak, buldukları sonuçları, diğer problemlerin ne kadar hızlı çözülebileceğini anlatan bir matematiksel hız sınırı bulma işi olarak tarif etti.

Açıklamasına “Fizikte, ışık hızı sabiti gibi, olayları anlatmanıza olanak sağlayan önemli sabitler vardır,” diyerek devam eden Van der Hoeven sözlerini, “Eğer bilgisayarların belirli matematiksel problemleri hangi hızla çözdüğünü bilmek isterseniz, tamsayılardaki çarpma işlemi ile karşılaşırsınız. Tamsayılardaki çarpma işlemi bu hızı tarif etmenin bir yapı taşı olarak düşünülebilir.” diyerek bitirdi.

Okullarda öğretilen çarpma işlemi dünyanın hemen her yerinde aynı biçimde öğretilir. İki sayı alınır, alttaki sayının her basamağı üstteki sayının her basamağı ile çarpılır ve bu çarpma işlemleri sonucunda toplama işlemi yapılarak çarpma işleminin sonucuna varılır.

Yani eğer, iki basamaklı iki sayı birbiriyle çarpılmak isteniyorsa, sonuca ulaşmak için birer basamaklı dört sayıyı birbiriyle çarpmanız gerekir.

“Taşıma yöntemi” de denilen bu yöntemde, n birbirleriyle çarpılan sayıların basamak sayısını göstermek üzere n2 adıma ihtiyaç duyulur. Yani, 3 basamaklı iki sayıyı çarpmak için 9 ve 100 basamaklı iki sayıyı çarpmak için 10000 adet çarpma işlemi yapmak gerekir.

Taşıma yönteminin, küçük basamaklı sayıları çarpmak için ideal bir yöntem olduğu söylenebilir. Fakat bu yöntemin, iş, pi sayısını doğru hesaplamak veya büyük asal sayıları bulmak gibi, milyonlarca veya milyarlarca basamağa sahip olan sayıları çarpmaya gelince, açmaza sürükleneceği de su götürmez bir gerçek.

İcadından sonra, çok uzun bir zaman boyunca, daha hızlı bir yönteminin olamayacağı kabul edilen çarpma işleminin hikayesi, 1960 yılında, o zaman 23 yaşında olan Rus matematikçi Anatoly Karatsuba’nın öne sürdüğü bir iddia ile değişti.

Karatsuba’nın dinleyici olarak katıldığı, konuşmacının ise yirminci yüzyılın en önemli matematikçilerinden biri olan Andrey Kolmogorov olduğu bir seminerde; Kolmogorov çarpmanın n2′den daha az adımda yapılamayacağını savunurken, Karatsuba böyle bir yolun mümkün olabileceğini düşündü ve düşüncelerini bir haftalık bir çalışmadan sonra görücüye çıkardı.

Karatsuba’nın yöntemi, bir sayının basamaklarını parçalara ayırmak ve daha sonra o parçaları alışılmadık bir biçimde yeniden bir araya getirmek üzerine kurulu. Burada “alışılmadık” olarak nitelendirilen biçimden kastedilen, çok sayıda çarpma işleminin yerini az sayıda toplama ve çıkarma işleminin alması. 

Böylece çarpma işleminin n2 adımda yaptığı işi, toplama ve çıkarma işlemi  2n adımda yapıyor ve zamandan tasarruf ediliyor.

büyük sayılar nasıl hızlıca çarpılır, çarpma işlemi

2007 yılında, o zamana kadarki en hızlı çarpma tekniğini geliştiren ve halen Pennsylvania Devlet Üniversitesi’nde matematikçi olarak çalışmalarına devam eden Martin Fürer konu ile ilgili olarak, “Okulda, çarpmayı bu yöntemle öğrendiğiniz zaman, normalde öğrendiğinizden bir sene daha erken öğrenebiliyorsunuz, çünkü bu yöntem diğerinden çok daha kolay bir yöntem. Yöntemin bir diğer güzelliği, işlemleri doğrusal bir zaman diliminde yapabiliyor olmanız, bu neredeyse sayıları sağdan sola doğru okumak kadar hızlı.” dedi.

Karatsuba tekniği, iki basamaklı sayılar yerine büyük sayılarla uğraşırken de kolayca kullanılabilen bir yöntem. Burada yapılacak iş, orijinal sayıyı, sayının ne kadar basamağı varsa o kadar parçaya ayırmak ve hemen her ayırmada, birçok adım gerektiren çarpma işlemini daha az adım gerektiren toplama ve çıkarma işlemleri ile değiştirmek.

Joris van der Hoeven ile birlikte, çarpma işleminin şimdiye kadar aldığı en mükemmel hali almasında emeği geçen bir diğer isim olan ve halen New South Wales Üniversitesi’nde çalışan matematikçi David Harvey konu ile ilgili şunları söyledi, “Bazı çarpma işlemlerini toplama ile değiştirebilirsiniz. Buradaki fikir, bilgisayarların toplama işlemini, çarpma işleminden daha hızlı yapacak olmalarıdır.”

Karatsuba tekniğinin, sayıları sadece n1.58 tek haneli basamak kullanarak çarpma olanağını sağladığı hükümdarlığı, Arnold Schönhage ve Volker Strassen’in 1971 de yayınladıkları bir makale ile son buldu. Schönhage ve Strassen, yayınladıkları makalede, logn, n sayısının logaritmasını göstermek üzere, büyük sayıların n x logn x log(logn) adımda çarpılabileceği bir yöntemden bahsettiler.

Bu yöntem, bir milyar basamaklı iki sayı söz konusuyken, Karatsuba yönteminden 165 trilyon daha az adıma ihtiyaç duyuyor.

Schönhage ve Strassen’in bulduğu ve bilgisayarların çok büyük sayıları çarparken kullandıkları yöntem, beraberinde, uzun vadede çok işe yarayacak iki önemli sonucu daha getirdi.

İlki, bu yöntemin hızlı Fourier dönüşümü adı verilen ve sinyal işleme alanında da kullanılan bir teknik kullanmasıydı. Schönhage ve Strassen’in kullandığı bu teknik, o zamandan beri yapılan her hızlı çarpma işleminin temelini oluşturmuş durumda.

İkincisi, Schönhage ve Strassen’in aynı makalede bahsettikleri, sadece n x logn adıma ihtiyaç duyan ve kendi buldukları yöntemden bile daha hızlı olan bir yöntem olduğu varsayımlarıydı. Bu varsayım, çarpma gibi temel bir işlemin, n x logn x log(logn)  sayısından daha zarif bir limiti olması gerektiği içgüdüsüne dayanıyordu.

Fürer, bu içgüdüyle ilgili olarak, “Şimdiye kadarki deneyimlerimizden, basit şeylerin şık bir matematiksel estetiğe sahip olması gerektiği gibi bir sonuç çıkarabiliyorduk. Çarpmanın da çok önemli basit bir işlem olduğu yönünde genel bir kanı vardı ve bu işlem, sırf bu yüzden bile olsa, daha şık bir karmaşıklık sınırına ihtiyaç duymalıydı.” dedi.

Schönhage ve Strassen’in yöntemi 36 yıl hüküm sürdü. Daha sonra sahne Fürer’in oldu ve Fürer’in açtığı yol, on yıldan fazla zamandır, matematikçilerin, her seferinde n x logn  ifadesine biraz daha yaklaşan, fakat ona yetişemeyen, daha hızlı ardışık çarpma algoritmaları geliştirmelerine ön ayak oldu.

Harvey ve Van der Hoeven geliştirdiği ve Mart ayında görücüye çıkardıkları yönteme, onlardan önce yapılan önemli işlerin bir rötuşu olarak bakılabilir.

Bu rötuş, basamakları birbirinden ayırıyor, hızlı Fourier dönüşümünün geliştirilmiş bir versiyonunu kullanıyor ve son kırk yılda yapılan iyileştirmelerin sağladığı avantajları kullanıyor. Hoeven geliştirdikleri yöntemi anlatmak için “Hızlı Fourier metodunu daha kuvvetli bir biçimde kullanıyoruz,” diyor, “onu tek bir defa kullanmak yerine birçok sefer kullanıyoruz ve böylece çok daha fazla sayıda çarpmayı toplama ve çıkarma ile yer değiştirebiliyoruz.”

Harvey ve van der Hoeven’in algoritması çarpmanın n x logn   adımda yapılabileceğini ispatlıyor, fakat bunu yapmanın daha hızlı bir yöntemi olmadığını ispatlamıyor. Harvey ve van der Hoeven’in buldukları yaklaşımın en iyi yaklaşım yolu olduğunu kanıtlamak çok zor.

Aarhus Üniversitesi’nden bir grup bilgisayar bilimcisinin Şubat ayının sonunda yayınladıkları makalede çarpma işleminin en hızlı yolu olabilecek ispatlanmamış bir varsayımın doğru olup olmadığı tartışılıyor.

Bulunan bu yeni algoritma teorik olarak önemli olmasına rağmen, yaklaşım olarak şimdiye kadar kullanılan algoritmalardan çok daha az iyilikte olduğu için, pratikte çok bir şey değiştirmiyor. Hoeven bu durumla ilgili olarak, “Yöntemle ilgili en yüksek beklentimiz, eski yöntemlerden üç kat daha hızlı olması yönünde” diyor ve ekliyor, “bu durumda elde edilen sonuçlar çok da şaşırtıcı sonuçlar olmayacaktır.”

Yukarıda bahsedilenlere ek olarak, bilgisayarların da donanım olarak değiştiğini söylemeden geçmek hata olur. Fakat bilgisayar donanımları ne kadar iyileşirse iyileşsin, sınıfının en iyisi olan algoritmalar ebedi.

Bu durumda, bilgisayarların gelecekte nasıl görüneceklerinden bağımsız olarak Harvey ve van der Hoeven’in algoritmasının hala çarpma için etkili yöntem olacağı söylenebilir.

Kaynak ve İleri Okuma: https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/

 

Fatma Ayca Cetinkaya

Matematik alanındaki lisans derecemi Ankara Üniversitesi'nden, yüksek lisans ve doktora derecelerimi Mersin Üniversitesi'nden aldım. Halen Mersin Üniversitesi Matematik bölümünde Doktor Öğretim Üyesi unvanıyla çalışmaktayım.

İlgili Makaleler

2 Yorum

  1. Zahmet olmazsa son geliştirilen yöntemin nasıl uygulandığını görsellerle destekleyebilir misiniz?

Seyran Memmedov için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Başa dön tuşu
Kapalı