3 ile 5'i çarpabilirsiniz, 27 ile 33'ü çarpabilirsiniz, 124 ile 543'ü çarpabilirsiniz... Ancak 100 basamaklı iki sayıyı çarpmak istediğinizde bir hesap makinesine başvurmanız gerekir.
Sürpriz! Basit bir hesap makinesi de bu işlemi yapamaz ve siz bir bilgisayara danışırsınız. O yapar, ancak toplamda 10.000 küçük çarpma işlemi yapacağı için yaklaşık 30 yılda yapar. Evet, 30 yıl yanlış okumadınız.
Yahu yok mu bunun bir kolay yolu? İşte şimdi bilim insanlarıyla aynı soruyu sordunuz. Büyük sayıları kolayca çarpmaya çok ihtiyacımız var. Peki neden? Gelin bir bilene kulak verelim.
Fransa’da yer alan Ulusal Araştırma Merkezi’nde görevli matematikçi Joris van der Hoeven, Wired’a yaptığı açıklamada “Herkes okulda öğrendiğimiz çarpma işleminin en iyisi olduğunu düşünüyor, ancak aslında bu alanda hâlâ araştırmalar yapılıyor” diyor.
Araştırmacı, “Fizikte her türlü olayı tanımlamamızı kolaylaştıran ‘ışık hızı’ gibi önemli sabitlerimiz var. Bilgisayarlar için de bu sabit matematikteki çarpma işlemidir. Bilgisayarların matematik problemlerini ne kadar hızlı çözebileceğini bilmek isterseniz, yaptıkları çarpma işlemlerinin hızına bakarsınız.” açıklamasında bulundu.
Bir başka deyişle, ne kadar hızlı çarpma işlemi yapar ve bunu makinelere öğretirsek, makineler de o kadar hızlı olacaklar.
Sıradan, hepimizin bildiği çarpma yöntemi neden zor?
Çoğu insan çarpma işlemini aynı şekilde öğrenir. İki sayıyı alır üst üste yazar ve alttaki sayının her basamağını, üstteki sayının her basamağı ile çarpar. Alt kısımda birer basamak sola kaydırma yaparak alt alta satırlar yazar, sonra da bu satırları birbirleriyle toplarız.
3 basamaklı iki sayıyı çarpmak için toplamda 9 küçük çarpma işlemi yapmak gerekir. 100 basamaklı 2 sayıyı çarpmak için gereken küçük çarpma işlemi sayısı ise tam 10.000'dir!
Gereken işlem sayısını bulmak için "n üssü 2" formülünü kullanabiliriz. Burada "n" terimi, basamak sayısını ifade ediyor.
Yeni keşfedilen yöntemi anlamak için 59 yıl geçmişe gidelim:
Binlerce yıl, çarpma işlemi için daha hızlı bir yolun bulunamayacağı düşünüldü. 1960 yılında 23 yaşındaki Rus matematikçi Anatoly Karatsuba, dönemin en tanınan matematikçilerinden Andrey Kolmogorov’un düzenlediği bir seminere katıldı. Kolmogorov seminerdeki konuşmasında öğrencilere çarpma işlemi için genel bir prosedür olmayacağından bahsediyordu. Karatsuba, öğrencilerin arasından sıyrılıp profesöre seslendi:
“Hayır, daha kısa bir yol var!”
Sadece bir hafta sonra 23 yaşındaki genç matematikçi bahsettiği yolu keşfetti. Karatsuba’nın yöntemi bizim ilkokullarda öğrendiğimiz yönteme benziyordu, ancak biraz farklı işliyordu.
Bizim bildiğimiz yöntemden farklı olarak Karatsuba, aynı hizadaki basamakları çarparak ilerliyor. Ardından sayıların rakamlarını topluyor, toplamlarını çarpıyor ve bu çarpımın sonucundan basamak çarpımlarını çıkarıyordu.
Şöyle açıklayalım:
Örneğin yapmak istediğimiz işlem 25 x 63 olsun:
- Geleneksel yöntemle: 4 küçük çarpma işlemi
- Karatsuba yöntemiyle: 3 küçük çarpma işlemi
Peki ya daha karmaşık bir örnekle yaparsak? Mesela 2531 x 1467:
- Geleneksel yöntemle: 16 çarpma işlemi
- Karatsuba yöntemiyle: 9 çarpma işlemi
Karatsubanın yöntemine göre, işleme çarpılacak sayıyı ortadan ikiye ayırarak başlamak gerekiyor. Yöntem çıkarmayı da sürece dahil ederek, işlemi basitleştiriyor. Geleneksel yöntemde basamak sayısının karesi kadar işlem yaparken, Karatsuba yönteminde basamak sayısının 2 katı kadar işlem yapmak yeterli oluyor.
100 basamaklı bir sayıyı çarpmak için geleneksel yöntemle 10.000 işlem gerektiğini söylemiştik, Karatsuba tekniği ile aynı sonuca 200 işlemle ulaşabiliyorsunuz.
Ancaaak...
1 milyar basamaklı bir sayısının çarpımı için geleneksel yöntemi bir adım öteye taşıyan Karatsuba tekniği bile 165 trilyon tane ek çarpma işlemi gerektiriyor. Nitekim Karatsuba'da sayıyı ikiye bölseniz bile yine büyük bir sayı buluyor, Karatsuba içinde Karatsuba yaparak milyarlarca işleme ulaşıyordunuz. Yetersizdi.
Bugün bilgisayarlarda kullanılan yöntem ise bundan daha hızlıydı. 1971'de dönüyoruz:
1971'de Arnold Schönhage ve Volker Strassen, çarpma işleminin için logaritmik bir fonksiyon ekledi. Büyük sayıları şu formülle çarpabileceklerini keşfettiler:
n x logn x log(log n)
Schönhage ve Strassen'in yöntemi ise bilgisayarlarda kullanılacak kadar gelişmişti. 36 yıldır bilgisayarlarımız da bu yöntemi kullanıyor.
Daha da hızlısı var. Keşfedilen yeni çarpma işlemi yöntemi:
Pensilvanya Eyalet Üyniversitesi matematikçilerinden Martin Fürer, aradan geçen 36 yılın ardından hayatını çarpma işlemine adayan bir diğer önemli isim oldu. Schönhage ve Strassen yönteminin üzerine çıkacak bir teknik geliştirmek istedi. 2007 yılında çalışmaya koyuldu.
Yapılan son araştırmanın yazarlarından bir diğer matematikçi David Harvey, "Bazı çarpma işlemlerini toplama işlemlerine dönüştürürsek bilgisayarlar daha da hızlanacak" dedi. Size yazının başında bahsettiğimiz Van der Hooven, arkadaşı David Harvey ile birlikte Martin Fürer'e katıldılar. 3 kişilik ekip, 2007'den bu yana devam eden araştırma sürecini tamamladı.
Son 40 yılda yapılan hemen hemen her geliştirmeden yararlanan bilim insanları, tıpkı Karatsuba'nın yaptığı gibi rakamları bölümlere ayırıyor ve Schönhage - Strassen yöntemini referans alıyordu. Bugün dijital olarak fotoğraf ve müzik paylaşmamızı sağlayan, sinyal ayrıştırma formülü Faurier Dönüşümü bile işin içindeydi.
Van der Hoeven, “Foruier dönüşümünü tek sefer yerine birkaç kez kullanıyoruz ve çarpma işlemini daha çok toplama ve çıkarma haline getiriyoruz." diyor. Yani işlemi olabildiğince basitleştirerek bilgisayarların işini kolaylaştıracak bir yöntemden söz ediyor.
Bilgisayarlar, toplama işlemini çarpmadan daha hızlı gerçekleştiriyorlar. Son 20 yılda, iki işlem süresi arasındaki zaman farkı giderek azalsa da toplama işlemi, hâlâ bilgisayarlar için daha kolay.
Yayımlanan son araştırmanın detaylarına göre bilgisayarlar, yeni formülle 3 kat daha hızlı çarpma işlemi yapabilecekler. Bunun için Fürer, Hoeven ve Harvey tarafından 10 yılı aşkın sürede geliştirilen teknik, gerçek zamanlı olarak modern bilgisayarlarda simüle edilecek.
Bakalım bu testlerin sonuçları bize neler sunacak. Araştırmalar, çarpma işleminin artık bilgisayarlar için toplama işlemi kadar kolay olacağını gösteriyor.