Çarpma işlemi için mükemmel algoritma nedir? Matematikçiler cevabı yeni bulmuş olabilir
Nereden çarpma işlemi Buluşundan bu yana binlerce yıl geçti, ancak yakın zamana kadar matematikçiler bu "zanaatı" mükemmelliğe yaklaştırmış olabilirler. Merak ediyor olabilirsiniz, henüz mükemmel bir çarpım hesaplama yöntemimiz yok mu? Çocukluğumuzdan beri sınıfta öğrendiğimiz yöntem yeterince iyi değil mi? Aslında çarpma algoritmaları matematikte aktif bir araştırma alanıdır.
Mevcut yöntem basit ve görünüşte etkili olsa da, bir milyardan fazla basamaklı olanlar gibi aşırı büyük sayılar için uygun değildir. İster pi hesaplıyor ister büyük asal sayılar arıyor olsun, son analizde yer alan hesaplama problemlerinin karmaşıklığı çarpma hızından kaynaklanmaktadır. 18 Mart matematikçi David Harvey ile Joris van der Hoeven (Sırasıyla New South Wales Üniversitesi ve Paris Politeknik Üniversitesi'nden) HAL'da (Fransız Ulusal Bilimsel Araştırma Merkezi Kurumsal Deposu) iki çok büyük sayıyı çarpmanın yeni bir yöntemini açıklayan bir makale sundu. Bu, şimdiye kadar bulunan en hızlı ve en verimli çarpma algoritmasıdır.
Bir bilgisayarın bazı matematiksel problemleri ne kadar hızlı çözebileceğini bilmek istediğimizde, tamsayılar arasındaki çarpma en temel anahtardır. Hesaplanacak sayı çok büyük olduğunda hızı ölçmek için en önemli kriter, basamak sayısı arttıkça gerekli hesaplama miktarının ne kadar hızlı artacağıdır.
Neredeyse hepimiz sınıfta aynı çarpma yöntemini öğrendik: çarpılacak iki sayıyı birlikte yukarı ve aşağı yazıyoruz, ardından yukarıdaki sayının her basamağını çarpmak için alttaki sayının her basamağını kullanıyoruz ve son olarak da sonucu Toplayın. Diğer bir deyişle, iki basamaklı çarpma ile iki basamaklı bir çarpma yaptığımızda, son ürünü elde etmek için toplam dört küçük çarpma yapmamız gerekir.
Geleneksel algoritma 2 haneyi çarpar ve birim rakamları 4 kez çarpması ve ardından sonucu elde etmek için toplaması gerekir.
N basamakları n basamakla çarpmak için bu "taşıma" yöntemini kullanırken, genellikle n² adım alır, bu nedenle 3 basamaklı bir çarpma 9 çarpma gerektirir ve 100 basamaklı bir çarpma 10.000 çarpma gerektirir . Diğer bir deyişle, bu yöntem yalnızca birkaç basamaklı sayıları çarpmak için uygundur, ancak milyonlarca veya milyarlarca basamaklı sayılarla karşılaştığınızda başınız derde girecektir.
Geleneksel 4 basamağı çarpma algoritması, toplamda 16 birim basamak çarpımı gerektirir.
Ancak pi'yi doğru bir şekilde hesaplarken veya büyük asal sayıları ararken, bu tür işlemleri gerçekleştirmeliyiz. Bu yöntemi iki milyar basamaklı sayıyı çarpmak için kullanırsanız, yaklaşık 30 yıl sürecektir.
1960 yılında, 20. yüzyılın en büyük matematikçilerinden biri olarak selamlandı. Kolmogorov (Andrey Kolmogorov) bir keresinde sayıları n²'den daha az adımda çarpabilen evrensel bir hesaplama yöntemi olmadığını ileri sürdü. Ve sadece 23 yaşında olan matematikçi Anatoly Karatsuba Ama evet düşün! Bir hafta aradıktan sonra onu buldu. 1962'de resmen yayınladı. Karatsuba algoritması .
Karatsuba'nın algoritması, sayıları parçalamayı, onları yeni bir şekilde yeniden birleştirmeyi ve ardından çok sayıda çarpımı az sayıda ekleme ve çıkarma ile değiştirmeyi gerektirir. Bu yöntem zaman kazandırır, çünkü toplama işlemi n² çarpma adımlarına kıyasla yalnızca 2n adım gerektirir.
Karatsuba algoritması 2 haneyi çarpar, sadece 3 çarpma işlemi (B, C, E) ve ayrıca toplama ve çıkarma işlemleri gerekir.
Daha büyük sayıları işlerken, orijinal sayıları bölmek için Karatsuba algoritmasını yeniden kullanabilirsiniz. Her bölme yaptığınızda, hesaplamak için birçok adım gerektiren çarpmayı değiştirmek için toplama ve çıkarmayı kullanabilirsiniz. Bilgisayarlar için toplama, çarpmadan daha hızlıdır. Karatsuba'nın algoritması, n basamaklı sayıları çarpmanın hesaplama karmaşıklığını n ^ 1.58'e düşürebilir.
Karatsuba algoritmasının 4 basamaklı çarpımı yalnızca 3 Karatsuba çarpma işlemi gerektirir.Her Karatsuba işlemi üç adet tek basamaklı çarpma işlemi içerir, bu nedenle toplamda yalnızca 9 çarpma işlemi gerekir.
1971'de Alman matematikçiler Arnold Schonhage ile Volker Strassen N basamaklı sayıları çarpmak için bir yöntem yayınladı (n daha büyüktür). n × günlük (n) × günlük (günlük (n)) Çarpma işlemi tek adımda tamamlanır. N'si 1 milyara eşit olan iki sayı birlikte çarpıldığında, Schonhage ve Strassenin algoritması, Karatsubanın yöntemine kıyasla yaklaşık 165 trilyon adım tasarruf sağlar.
Schonhage ve Strassen'in algoritması, yalnızca bilgisayarların büyük ölçekli veri çarpımını hesaplaması için bir yöntem haline gelmedi, aynı zamanda Hızlı Fourier dönüşümü Hızlı çarpma algoritmaları için kullanılabilecek bir teknik olarak. Ek olarak, yöntemlerinden daha hızlı bir algoritma olması gerektiğini düşünüyorlardı: n basamaklı sayıları çarpmak için, daha hızlı algoritma yalnızca n × günlük (n) Yalnızca bir işlem adımı tamamlanabilir ve bu algoritma, çarpmanın sınır hızı olabilir.
Schönhage ve Strassen'in yöntemi 36 yıldır güçlü ve matematikçiler tarafından 2007 yılına kadar tanınmıyordu. Martin Fürer dövmek. Fürer o sıralarda en hızlı çarpma yöntemini keşfetti, ancak algoritmasından vazgeçti. Bir röportajda bunun son derece zor bir meydan okuma olduğunu ve buna güvenmediğini söyledi. Bu nedenle, yeni araştırmanın başarısı karşısında son derece şaşırdı ve heyecanlandı.
Bununla birlikte, Fürer'den bu yana, matematikçiler son on yılda daha hızlı çarpma algoritmaları keşfettiler, her biri yavaş yavaş n × log (n) 'ye yaklaştı, ancak tam olarak başaramadılar. Geçen aya kadar Harvey ve van der Hoeven bu sınıra ulaştı.
Yeni yöntem, öncekilerin çalışmalarını iyileştirmenin sonuçlarına dayanmaktadır. Geliştirilmiş bir Hızlı Fourier Dönüşümü adımı kullandılar ve bunu yöntemlerinde birçok kez kullandılar Hızlı Fourier dönüşümü , Daha fazla çarpımı toplama ve çıkarma ile değiştirin.
Harvey ve van der Hoeven'in algoritması, çarpmanın gerçekte n × log (n) adımlarla tamamlanabileceğini kanıtladı ve bu, teoride büyük bir ilerleme olarak kabul edilebilir. Ancak pratikte, bariz avantajlar göstermez ve yüksek verimliliği esas olarak şaşırtıcı derecede büyük sayıların çarpılmasına yansır. Van der Hoeven, mevcut algoritmalardan 3 kat daha hızlı olmasını bekleyebileceğimizi söyledi.
Bu çalışmada, yalnızca 10214857091104455251940635045059417341952 bitten fazla ikili sayıları dikkate aldılar ve bu sayılar 0 ve 1 ile kodlandı. Fakat gerçekte herhangi bir büyük ölçekli çarpma gerçekleştirmediler, çünkü bu sayı, evrendeki atom sayısından çok daha fazla. Bu, bilgisayarların bu tür hesaplamaları yapamayacağı anlamına gelir, çünkü bırakın onları çarpmak bir yana, böylesine büyük sayıları temsil edecek yeterli atom yoktur. Yaptıkları şey, teorik olarak bu tekniğin diğer yöntemlerden daha hızlı olacağını veya en azından bu kadar çok sayıda olacağını kanıtlayacak bir teknik bulmaktı.
Bu algoritmaya pek elverişli olmayan bir diğer faktör, bugünün bilgisayar donanımının 20 yıl öncekinden çok farklı olmasıdır. Bazı yeni çip mimarilerinde, çarpma ile toplama ve çıkarma arasındaki hız farkı azalıyor ve hatta bazıları toplama ve çıkarmadan daha hızlı olabilir. Bu nedenle, bazı durumlarda, araştırmacıların işlem hızını artırmak için toplama yerine çarpma kullanmaya çalışması da gerekebilir.
Yine de, bu algoritma yeni asal sayıları veya kesin pi bulmada hala rol oynayabilir. Çarpma gibi temel bir problemde böyle bir başarıya ulaşabilmek kuşkusuz çok dikkat çekicidir. Ve donanım zamanla değişse bile, birinci sınıf algoritmalar sonsuzdur. Gelecekteki bilgisayar nasıl görünürse görünsün, Harvey ve van der Hoeven'in bugüne kadarki en etkili çarpma algoritmasını buldukları gerçeğini değiştirmeyecek.
Derleyici: Zuoyou
Referans bağlantısı:
https://hal.archives-ouvertes.fr/hal-02070778/document
https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/
https://www.sciencenews.org/article/mathematicians-may-have-found-fastest-way-multiply-huge-numbers?tgt=nr
