Çarpma İşlemi Yapmak İçin En Hızlı Yöntem Nedir?

Yaklaşık 4 bin önce, Babilliler çarpma işlemini icat etti. Yakın zamanda da, matematikçiler onu mükemmelleştirdi.

Okullarda öğretilen çarpma işlemi dünyanın hemen her yerinde aynı biçimde yaparız. İki sayı alır, alttaki sayının her basamağını tek tek üstteki sayı ile çarparız. Sonrasında da çıkan sonuçları toplarız. İki basamaklı iki sayı birbiri ile çarpmak için de birer basamaklı dört sayıyı birbiriyle çarpmanız gerekir.

İlköğretim yıllarının başında öğrendiğimiz bu yöntem de elbette sorun yoktur. Hatta küçük sayıları birbiri ile çarpmak için en kolay metot elbette hala budur. Ancak bu çarpma işlemini kullandığımız adım sayısı olarak düşünürseniz, nihayetinde ürkütücü bir gerçekle karşılaşacaksınız.

Sonuçta iki tane bir basamaklı sayıyı çarpmak için bir küçük çarpma işlemi, iki tane iki basamaklı sayıyı çarpmak için dört küçük çarpma işlemi, 3 basamaklı iki sayıyı çarpmak için de 9 çarpma işlemi yapmanız gerekir. Yani n basamaklı iki sayıyı birbiri ile çarparsanız bunun için n2 tane çarpma işlemi yapmanız gerekecektir. Bu durumda 100 basamaklı iki sayıyı çarpmak için 10000 adet çarpma işlemi yapmak gerekir.

Gerçekten de bir bilgisayarımız veya hesap makinemiz yoksa, büyük sayıları çarpmak son derece zaman alıcıdır. Bu sorun sadece ortalama bir insan geçerli de değildir. Bilgisayarlar sayılar büyüdükçe uzun çarpma işlemi ile ilgili sorunlar yaşamaya başlarlar. Bir milyar basamaklı iki sayıyı çarpmak, 10 18 tane çarpma gerekir. Bu da modern bir bilgisayarın yaklaşık 30 yılını alır.

Yakın zamanda David Harvey ve Joris van der Hoeven adlı matematikçiler, çarpma işlemini daha hızlı yapmak için farklı bir yöntem önerdi. Bu yöntem sayesinde çok büyük sayıları çarpmak artık daha kolay.

Çarpma İşlemini Daha Hızlı Yapmak İçin Uzun Yıllardır Yeni Yöntemler Araştırıyoruz

çarpı işareti

Herkes temelde okulda öğrendiğiniz yöntemin en iyi yöntem olduğunu düşünse de aslında matematikçiler konu ile ilgili bir çok araştırma yapmaktadır. Çarpma işleminin hikayesi, 1960 yılında Rus matematikçi Anatoly Karatsuba’nın öne sürdüğü bir iddia ile değişti. Kendisi günümüzde adı ile anılan farklı bir teknik ortaya koymuştu.

Karatsuba tekniği, iki basamaklı sayılar yerine büyük sayılarla uğraşırken kolayca kullanılacağınız bir yöntem. Yapmanız gereken sayınızı, sayının ne kadar basamağı varsa, o kadar parçaya ayırmak. Bu sayede de çarpma işlemini daha az adım gerektiren toplama ve çıkarma işlemleri haline gelecektir.

Sonucunda çarpma işleminin n2 adımda yaptığı işi, toplama ve çıkarma işlemi  2n adımda yapar. Bu da zamandan tasarruf anlamına gelmektedir. Büyük sayıları hızlıca çarpmak için Karatsuba yöntemini nasıl kullanacağınızı görseli detaylı bir biçimde inceleyerek anlayabilirsiniz.

Karatsuba Yöntemi İle Çarpma İşlemi Nasıl Yapılır?

büyük sayılar nasıl hızlıca çarpılır, çarpma işlemi
Karatsuba algoritması hızlı bir çarpma algoritmasıdır. 1960 yılında Anatoly Karatsuba tarafından keşfedildi ve 1962’de yayınlandı.

Karatsuba algoritmasının hükümdarlığı, Arnold Schönhage ve Volker Strassen’in 1971 de yayınladıkları bir makale ile son buldu. İki Alman matematikçi tarafından geliştirilen Schönhage-Strassen algoritması aslında 1971’den 2007’ye kadar en hızlı çarpma yöntemiydi. Bu yöntem, bir milyar basamaklı iki sayı söz konusuyken, Karatsuba yönteminden 165 trilyon daha az adıma ihtiyaç duyuyor. Tam olarak söylemek gerekirse bu çarpma işlemi tam olarak n x logn adım gerektiriyor.

Schönhage ve Strassen’in bulduğu yöntem, beraberinde, uzun vadede 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 yöntemi 36 yıl hüküm sürdü. Onların ortaya koyduğu yöntem, matematikçilerin, her seferinde n x logn  ifadesine biraz daha yaklaşan, daha hızlı çarpma algoritmaları geliştirmelerine ön ayak oldu. Son önerilen, yazının başında aktardığımız yönteme de aslında, onlardan önce yapılan önemli işlerin bir rötuşu olarak bakılabilir.

Yeni yöntemde Fourier dönüşümü bir değil, bir çok defa kullanılıyor. Böylece çok daha fazla sayıda çarpmayı toplama ve çıkarma ile yer değiştirmek mümkün oluyor. Bu çarpma yöntemi eski yöntemlerden üç kat daha hızlı. Bu durumda şimdilik çarpma işlemini yapmak ile ilgili en hızlı yolu bulmuş olabiliriz.



Kaynaklar ve İleri Okuma:


Dip Not:

Matematiksel, 2015 yılından beri yayında olan ve Türkiye’de matematiğe karşı duyulan önyargıyı azaltmak ve ilgiyi arttırmak amacıyla kurulmuş bir platformdur. Sitemizde, öncelikli olarak matematik ile ilgili yazılar yer almaktadır. Ancak bilimin bütünsel yapısı itibari ile diğer bilim dalları ile ilgili konular da ilerleyen yıllarda sitemize dahil edilmiştir. Bu sitenin tek kazancı sizlere göstermek zorunda kaldığımız reklamlardır. Yüksek okunurluk düzeyine sahip bir web sitesi barındırmak ne yazık ki günümüzde oldukça masraflıdır. Bu konuda bizi anlayacağınızı umuyoruz. Ayrıca yazımızı paylaşarak da büyümemize destek olabilirsiniz. Matematik ile kalalım, bilim ile kalalım

Matematiksel

Fatma Ayca Cetinkaya

Matematik alanındaki lisans derecemi Ankara Üniversitesi'nden, yüksek lisans ve doktora derecelerimi Mersin Üniversitesi'nden aldım. Mersin Üniversitesi Matematik bölümünde öğretim üyesi olarak görev yapmaktayım.

Bu Yazılarımıza da Bakmanızı Öneririz