Çevrimdışı

Günümüzden yaklaşık 4000 yıl önce toplama işlemini fazla yorucu bulan Babilliler çarpma işlemini icat ettiler. Günlerden bu yana çarpma işlemi sayesinde matematiksel işlemleri çok daha hızlı yapar hale geldik. Geçiğimiz ay ise çarpma işlemi hakkında yapılan bir araştırmanın sonuçlarına göre yeni bir yöntem keşfedildi.

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! O da 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.


Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir.


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 bakın” 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?


Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir.


Çoğu insan çarpma işlemini aynı şekilde öğrenir. İki sayıyı alır üst üste yaza ve alttaki sayının her basamağını üstteki sayının her basamağı ile çarpar, her basamak bir sola kayarak 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 gerekiyor. 100 basamaklı 2 sayıyı çarpmak için gereken küçük çarpma işlemi sayısı ise tam 10.000!

Gereken işlem sayısını bulmak için "2n" formülünü kullanabiliriz. "n" terimi basamak sayısını ifade ediyor. İşlemdeki en çok basamağa sahip sayının basamak sayısı 2 ile çarpıp, gereken işlem sayısını buluyoruz.


Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir.


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 bağırdı:

“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 rakamları ç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:


Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir.


Geleneksel yöntemle: 4 çarpma işlemi
Karatsuba yöntemiyle: 3 çarpma işlemi

Peki ya daha karmaşık bir örnekle yaparsak? Mesela 2531 x 1467:


Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir.


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. İşin içine çıkarmayı da dahil ederek süreci basitleştiriyor. Geleneksel yöntemde basamak sayısının karesi kadar işlem yaparken, Karatsuba yönteminde basamak saysının 2 katı kadar işlem yapmak yeterli oluyor.

100 basamaklı bir sayıyı çarpmal 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.

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 gerektiriyordu. 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 gönüyoruz:


Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir.


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 bu yöntemi kullanıyor.

Daha da hızlısı var. Keşfedilen yeni çarpma işlemi yöntemi:


Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir.


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.


Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir.


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 hala toplama 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 ne sunacak. Araştırmalar, çarpma işleminin artık bilgisayarlar için toplama işlemi kadar kolay olacağını gösteriyor.




Alıntıdır:

__________________
"Bizi bilen bilir, bilmeyen de kendi gibi bilir... "