Başlıktaki soru size mantıklı gelmeyecektir. Sonucunda çarpma işlemini nasıl yapıldığını hemen hemen hepimiz biliriz. Diyelim ki sizden 25 ile 63’ü çarpmanız istendi. Siz de çoğu insan gibiyseniz, muhtemelen cevabı telefonunuzun hesap makinesi ile hesaplarsınız. Ancak şarjınızın bittiğini ve bir hesap makinesi bulamadığınızı düşünelim. Bu durumda çaresiz muhtemelen ilkokulda öğrendiğiniz standart algoritmayı kullanmak zorundasınız.
Bu yöntemde alttaki sayının her basamağını tek tek üstteki sayı ile çarparız. Sonrasında da çıkan sonuçları toplarız. Dikkat ettiyseniz iki basamaklı iki sayıyı birbiri ile çarpmak için aslında bir 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. Hatta kendinize meydan okumak isterseniz bu sayıları aklınızdan da çarpmak isteyebilirsiniz. Bu durumda da dağılma özelliğini kullanmanız gerekecektir. Bu durumda 25 × 63 = 25 × (60 + 3) = 25 × 60 + 25 × 3 = 1500 + 75 = 1575 işlemini yaparak da sonucu bulabilirsiniz.
Yukarıdaki yöntemlerden hangisini bir çarpma işlemi esnasında kullanacağınız size kalmıştır. Hangisi daha iyi ya da daha kötü diyemeyiz. Ancak hangisinin daha verimli olduğunu bulabiliriz. Verimlilik, farklı kişiler için farklı bağlamlarda farklı anlamlara gelebilirken, bunu bir bilgisayarın bakış açısıyla düşünelim. Bir bilgisayarın çarpma işlemini gerçekleştirmesi ne kadar sürer?
Çarpma İşlemi Yaparken Hangi Yöntem Daha Verimlidir?
Verimliliği göz önünde bulundurarak örneğimiz olan 25 × 63’ü tekrar gözden geçirelim. Standart algoritmayı kullanarak 25 × 63’ü hesaplamak için dört küçük çarpma işlemi yapmamız gerekiyordu: 3 × 5, 3 × 2, 6 × 5 ve 6 × 2. Dağılma özelliğini uyguladığımız zaman da dikkatle bakarsanız yine dört küçük çarpma yapmak zorunda kaldığımızı fark edeceksiniz. Gördüğünüz gibi iki yöntem de verimlilik açısından eşdeğerdir.
Eşdeğer çıkmaları mantıklıdır. Çünkü temelinde ikisi de aynı şeydir. AB ve CD iki basamaklı sayılarının çarpımını bulmak istediğinizi düşünelim. AB sayınızı 10 A + B ve CD sayınızı 10C + D biçiminde göstererek çarparsak sonuç aşağıdaki gibi olacaktır.
(10 A + B ) × (10 C + D ) = 100( Bir × C ) + 10( Bir × D ) + 10( B × C ) + B × D . Şimdi buna sayılarımızı yerleştirelim. Bu durumda sonucumuz şöyledir.
25 × 63 = (10 × 2 + 5) × (10 × 6 + 3) = 100 (2 × 6) + 10(2 × 3) + 10(5 × 6) + 5 × 3 = 1200 + 60 + 300 + 15 = 1575.
Her durumda karşımıza 4 küçük çarpma çıkıyor ve temelde bu bir sınır gibi gözüküyor. 3 basamaklı iki sayıyı çarptığımız zamanlarda da bu sınır 9 oluyor. 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. Bilgisayarlar bile 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, 1018 tane çarpma gerekir. Bu da modern bir bilgisayarın yaklaşık 30 yılını alır.
Karatsuba Yöntemi İle Çarpma İşlemi Nasıl Yapılır?
1960 yılında, Rus matematikçi Anatoly Karatsuba, çarpmanın daha verimli bir yolunu bulmak için yola koyuldu ve sonunda yeni bir üst sınır buldu. Karatsuba, ‘ AB ‘ ve ‘ CD iki basamaklı sayılarının çarpımını hesaplamak için gereken dört küçük çarpmanın hepsinin , A + B ve C + D rakamlarının toplamlarını çarptığımızda da ortaya çıktığını fark etti. Bunun nasıl yapıldığını anlamak için aşağıdaki görseli incelemenizi öneririz.
Karatsuba tekniği kesinlikle küçük sayıları çarparken kullanacağınız bir yöntem değil. Ancak daha verimli bir yöntem. Baştan beri 4 sayısının çarpma için bir üst sınır olduğunu kabul etmiştik. Ancak bu yöntem sayesinde yeni üst sınırımız 3 oluyor.
Örneğin, 1.234 ve 5.678 gibi dört basamaklı iki sayıyı çarpmak istediğimizi varsayalım. Geleneksel çarpma teknikleri, toplam 4 × 4 = 16 küçük çarpma işlemi gerektirecektir. Ancak Karatsuba’nın yöntemini kullanarak bunu 12 küçük çarpma işlemine indirmeniz mümkündür. Bu yüzde 25 verimlilik aslında bir başlangıçtır.
Genel olarak konuşmak gerekirse iki n basamaklı sayıyı geleneksel yöntemlerle çarparken n × n = n 2 küçük çarpma işlemi yapmamız gerekecektir. Ancak Karatsuba’nın algoritması n 1.58 civarında küçük çarpma işlemi gerektirir. Sayılar büyüdükçe bu büyük bir fark yaratır. Ancak Karatsuba’nın yönteminin daha akıllıca uygulamaları, çarpma sayısını daha da azaltabilir ve sayılar arttıkça tasarruf da artar.
Çarpma İşlemini Daha Hızlı Yapmak İçin Uzun Yıllardır Yeni Yöntemler Araştırıyoruz
Bir bahşişi hesaplarken bu algoritmayı kullanmazsınız, ancak iş büyük sayıları çarpmaya geldiğinde, Karatsuba’nın yöntemi büyük bir ilerlemeydi. Ve Karatsuba 1960’ta daha hızlı çarpmanın kapısını açtığından beri matematikçiler, Fourier dönüşümü gibi gelişmiş teknikleri kullanarak yeni hız rekorları kırıyorlar.
Aslına bakarsanız 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ç duyuyordu. Tam olarak söylemek gerekirse bu çarpma işlemi tam olarak n x logn adım gerektiriyordu.
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. 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 çok daha kısa sürüyor.
Bu durumda şimdilik çarpma işlemini yapmak ile ilgili en hızlı yolu bulmuş durumdayız. Ancak unutmayın. Bu hız biz insanlar için değil temelinde bilgisayarlar için gereklidir. Bu nedenle siz nasıl biliyorsanız aynı biçimde çarpma yapmaya devam edebilirsiniz. Ayrıca çarpma yapmanın eğlenceli bir yoluna da göz atmak isterseniz: Çarpma Yapmanın Eğlenceli İki Yolu: Rus Çiftçi Ve Antik Mısır Çarpımı
Kaynaklar ve İleri Okuma:
- Mathematicians Discover the Perfect Way to Multiply; Yayınlanma tarihi: 11 Nisan 2019; Bağlantı: https://www.quantamagazine.org/
- This Guy Just Found a Faster Way to Multiply. Yayınlanma tarihi: 19 Ekim 2019; Bağlantı: https://www.popularmechanics.com/science/a29514208/faster-way-multiply/
- On Your Mark, Get Set, Multiply. Yayınlanma tarihi: 23 Eylül 2019; Bağlantı: https://www.quantamagazine.org/
Size Bir Mesajımız Var!
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 veya Patreon üzerinden ufak bir bağış yaparak da büyümemize destek olabilirsiniz. Matematik ile kalalım, bilim ile kalalım.
Matematiksel
