Karatsuba yöntemi: En hızlı çarpma algoritmalarından biri

Her insanımız için geleneksel ve en basit çarpma yöntemi “sütun” çarpma yöntemidir. Bize okulda öğretiliyor ve biraz beyin gerilimi gerektiren diğer yöntemlere fazla dikkat etmeden onunla yaşıyoruz. Bakalım nasıl...
Ən sürətli vurma alqoritmlərindən biri.  Karatsuba metodu

Her insanımız için geleneksel ve en basit çarpma yöntemi “sütun” çarpma yöntemidir. Bize okulda öğretiliyor ve biraz beyin gerilimi gerektiren diğer yöntemlere fazla dikkat etmeden onunla yaşıyoruz. Bakalım nasıl çalışıyor…

Bugün, sonsuz ve geniş bir ağda, daha önce hiç görmediğimiz bir şeyle karşılaşabiliyoruz.

Bu yöntem matematik tarihinde büyük sayıları çarpmanın ilk yöntemi olarak kabul edilir ve 1960 yılında Sovyet ve Rus matematikçi Anatoly Alekseyevich Karatsuba tarafından geliştirilmiştir.

O sırada 23 yaşındaki Karatsuba, 20. yüzyılın en büyük matematikçisi Andrei Nikolai Kolmagorov’un bir seminerine katıldı. Kolmagorov, n ^ 2 işleminden daha az çarpma yöntemi olmadığını söyledi.

Burada n, çarpılan sayılardaki basamak sayısıdır. Örneğin 4 basamaklı sayıları çarparken 16 işlem gerekir.

Anatoly Alekseyev beynini bir hafta boyunca çalıştırdı ve tamamen yeni bir yol buldu.

Özü, bir sayının sayılarını bölmek ve belirli bir şekilde yeniden bir araya getirmektir. En kolay yol, bir örnekle göstermektir!


Adım 1, 2 ve 3

Sayıları sayılara böleriz ve sonra onlarla, birimleri çarparız..

4. ve 5. Adım

İlk önce ilk sayının sayılarını, ardından ikinci sayının sayılarını topluyoruz. Ve son olarak, aralarında alınan toplamları çarpıyoruz.


6. Adım

5. adımda elde ettiğimiz sayıdan 2. ve 3. adımda elde ettiğimiz sayıyı çıkarıyoruz.

Nereden geldiğinin netleşmesini umuyoruz

7. Adım

“Adım 2” + “Adım 6” + “Adım 3” – sayıları bu şekilde ekliyoruz.

Değişikliğe dikkat edin! Tam olarak yazdığımız gibi eklemelisiniz.

Dürüst olmak gerekirse, bu çözdüğüm ilk örnek ve her şey ilk seferden alındı!

Şaşırtıcı olmayan bir şekilde, okul bundan bahsetmiyor. Buradaki işlemleri açıklamanız gerekiyor ve bu “sütun” yöntemi kadar kullanışlı değil…

Mantıklı bir soru sorabilirsiniz:

Buradaki hız nerede?

Her şey algoritmalara ve işlemin basitliğine bağlıdır. Örneğin 4 basamaklı bir sayıyı 16 ile çarparsanız – bu yöntemde sadece 9 işlem vardır. Hesaplaması çok kolay olan, toplama ve çıkarmanın çarpmaya göre daha hızlı olduğu bu yöntemde, en azından eskisi gibi birçok çarpma işleminin yerini toplama ve çıkarma işlemleri almaktadır.

4 basamaklı sayıları çarpma

Aslında Karatsuba, hızlı algoritmalar teorisinin temellerini attı. Şimdi, bu en hızlı algoritma değil, ama daha hızlıları var.

60 yıl önce bu yöntem en hızlısı olarak kabul ediliyordu ama şimdi yazdığımız gibi daha hızlı yöntemler var…

İstediğiniz çarpma yöntemini kullanın! “Sütunun” daha kolay olduğunu biliyorum! En iyisi bunu bir hesap makinesinde yapmak!

BU İÇERİĞE EMOJİYLE TEPKİ VER!
+1
0
+1
0
+1
0
+1
0
+1
0
+1
0
+1
0
Kategoriler
Bilim
Henüz Yorum Yok

Cevap bırakın

*

*

Benzer Konular