ARİTMETİK

Çarpma İşlemi İçin Yeni Bir Yöntem

David Harvey ve Joris van der Hoeven adlı matematikçiler, çarpma işlemini daha hızlı yapmak için yeni bir yöntem geliştirdi.

4000 yıl önce Babilliler tarafından keşfedilen çarpma işlemi en mükemmel halini aldı. Bu yöntem sayesinde çok büyük sayıları çarpmak daha kolay olabilecek.

Okullarda öğretilen çarpma işlemi dünyanın hemen her yerinde aynı biçimde yapılır. İ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.

Bu küçük sayıları çarpmak için ideal bir yöntem ancak büyük sayılar için durum aynı değil…

Çarpma İşleminin Hikayesi

İ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 Rus matematikçi Anatoly Karatsuba’nın öne sürdüğü bir iddia ile değişti.

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.

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.

Karatsuba tekniğinin 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ı.

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.

Son geliştirilen yönteme aslında, onlardan önce yapılan önemli işlerin bir rötuşu olarak bakılabilir.

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.

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/

Matematiksel

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.

Bir cevap yazın

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

Başa dön tuşu