Temel Matematiksel Kavramlar

Çarpma İşlemini Yapmak İçin Bildiğimizden Farklı Bir Yöntem

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 olsa da büyük sayılar için durum aynı değildir. David Harvey ve Joris van der Hoeven adlı matematikçiler, çarpma işlemini daha hızlı yapmak için farklı bir yöntem öneriyorlar. Bu yöntem sayesinde çok büyük sayıları çarpmak daha kolay olabilir.

çarpı işareti

Çarpma İşlemi Daha Hızlı Yapılabilir mi?

İ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.

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

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. Yeni önerilen 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.”. Yöntemle ilgili en yüksek beklenti eski yöntemlerden üç kat daha hızlı olması. Bu durumda şimdilik çarpma işlemini yapmak ile ilgili en hızlı yolu bulmuş olabiliriz.

Kaynak ve İleri Okuma: Mathematicians Discover the Perfect Way to Multiply; https://www.quantamagazine.org/

Matematiksel

Bir cevap yazın

E-posta hesabınız yayımlanmayacak.

İlgili Makaleler

Başa dön tuşu