İki matematikçi tarihteki en hızlı süper büyük çarpma algoritmasını keşfedebilir ve yaklaşık yarım yüzyıldır bir problemi çözmek isteyebilir.
Binlerce yıl kadar erken bir tarihte, Babilliler çarpmayı icat etmişlerdi. Ve daha geçen ay, matematikçiler bu hesaplama yöntemini daha da mükemmel hale getirmek için optimize ettiler.
18 Mart'ta iki araştırmacı, çok büyük iki sayının çarpımını hesaplamanın en hızlı yolunu keşfedebilir. Bu makalenin doğuşu aynı zamanda matematikteki en temel hesaplama yönteminin, yaklaşık yarım yüzyıldır var olan bir matematik problemini çözmesi beklenen daha yeni ve daha etkili bir hesaplama sürecine sahip olduğu anlamına geliyor.
Fransız Ulusal Bilimsel Araştırma Merkezi'nde matematikçi ve bu makalenin yazarlarından biri olan Joris van der Hoeven, Çoğu insan okulda öğrendikleri yöntemin en iyi yöntem olduğunu düşünüyor, ancak aslında araştırma dünyasında, Çarpma hesaplama yöntemleri alanı her zaman çok aktif olmuştur ve sürekli olarak yeni buluşlar ve optimizasyonlar vardır. "
Şekil Tarihte büyük sayıları çarpmak için en hızlı algoritmanın iki mucidi, Fransız Ulusal Bilimsel Araştırma Merkezi'nde matematikçi olan Joris van der Hoeven ve New South Wales Üniversitesi'nde profesör olan David Harvey'dir. Çok büyük sayıları hesaplarken, aşağıdaki şekildeki geleneksel hesaplama yöntemi çok zorlaşacaktır (Kaynak: École Polytechnique)
Pi'nin hesaplanmasından en son ve daha büyük asal sayıların aranmasına kadar matematiksel hesaplama alanındaki birçok zor problem, sonuçta temel çarpmanın hızıyla belirlenecektir. Van der Hoeven, diğer birçok problem türü için teorik olarak çözülebilecek en hızlı hız sınırının, nihayetinde çarpma hızıyla belirleneceğine inanıyor.
Van der Hoeven, "Fizikte de çok önemli bazı sabitler var. Örneğin, ışık hızı diğer birçok fiziksel olguyu belirleyen temel parametredir," dedi. "Bilgisayarların çeşitli matematik problemlerini ne kadar hızlı çözebileceğini bilmek istiyorsanız, tamsayı çarpımıdır. İşlem hızı da bu soruyu yanıtlamak için temel bir parametre olacak ve bu parametre birçok bilgisayar işleminin hızını tanımlamak için kullanılacaktır. "
Çoğu insanın öğrendiği çarpma yöntemi aşağıdaki yöntemdir. İki çarpanı iki satır halinde düzenleyin, yukarıdaki çarpandaki her bir rakamı çarpmak için aşağıdaki çarpandaki her rakamı kullanın ve ardından tüm çarpma sonuçlarını birbirine ekleyin. Örneğin, iki basamaklı iki sayının çarpımı ise, iki tek basamaklı sayıyı dört kez çarpmanız ve ardından bu dört çarpmanın sonuçlarını eklemeniz gerekir.
İlkokulda öğrendiğimiz bu çarpma algoritması, yani dikey çarpma hesaplama yöntemi, n basamak arasında çarparken, yaklaşık n kare tek basamaklı çarpma gerçekleştirmesi gerekiyor, burada n her biri Çarpandaki basamak sayısı. Bu nedenle, iki üç basamaklı sayının çarpımı 9 tek basamaklı çarpma gerektirir ve iki büyük 100 basamaklı sayıyı çarpmak istiyorsanız, 10.000 tek basamaklı çarpıma ihtiyacınız vardır.
Şekil Geleneksel dikey hesaplama yöntemi (kaynak: İnternet)
Yukarıda bahsedilen dikey hesaplama yöntemi aslında sayıları daha az basamakla çarpmak için daha uygundur. Milyonlarca basamağın veya milyarlarca basamağın çarpanlarını çarpmamız gerektiğinde, dikey hesaplama yöntemi, pi hesaplama veya daha büyük bir asal sayı bulma gibi güçsüzdür.
İki milyar basamaklı sayıları çarpmak istiyorsanız, milyar kare tek basamaklı sayıları çarpmanız gerekir.Bu işlem modern bilgisayarların yaklaşık 30 yıl sürmesini gerektirir.
Binlerce yıldır insanlar dikey hesaplama yönteminden daha hızlı çarpma algoritması olmadığına inanıyorlar.
1960 yılına kadar Anatoly Karatsuba adlı 23 yaşındaki bir Rus matematikçi, 20. yüzyılın en büyük matematikçilerinden Andrey Kolmogorov liderliğindeki bir seminere katıldı. O sırada Kolmogorov, n'nin karesinden daha küçük tek rakamlar arasında çarparak iki n basamaklı sayıyı çarpmanın bir yolu olmadığını iddia etti. Ama Karatsuba, var olduğunu düşündü ve sadece bir haftalık keşiften sonra, bu yolu buldu.
Yüksek enerjili erken uyarı için Karatsuba'nın önerdiği algoritma şu şekildedir:
25 ile 63 çarpımını hesaplamak için, geleneksel algoritma aşağıdaki gibi tek rakamlar ve birkaç ekleme arasında 4 çarpma gerektirir:
Karatsuba algoritması, tek rakamlar arasında 3 çarpma ve aşağıdaki gibi birkaç ekleme ve çıkarma gerektirir:
İkincisinin birçok adımı var gibi görünüyor, ancak ekstra büyük sayılar çarpıldığında avantajları ortaya çıkıyor, bu da esas olarak tek basamaklar arasındaki çarpma sayısının kaydedilmesinde yansıtılıyor: çarpan çok sayıda basamak içerdiğinde Karatsuba tekrarlanabilir İşlem, orijinal çarpanı daha küçük parçalara bölün. Bölme sayısı ne kadar fazlaysa, geleneksel algoritmalara kıyasla tek basamaklı sayılar arasında çarparak o kadar çok tasarruf edersiniz.
Örneğin, 2531'in 1467 ile çarpımını hesaplamak için, geleneksel algoritma tek rakamlar arasında aşağıdaki gibi 16 çarpma gerektirir:
Karatsuba algoritması, aşağıdaki gibi tek rakamlar arasında yalnızca 9 çarpma gerektirir:
(Kaynak: quanta)
Karatsubanın algoritmasının ana fikrinin, çok sayıda çarpanı daha küçük parçalara ayırmak ve bu parçaları yeni bir şekilde yeniden birleştirmek olan böl ve yönet algoritması olduğu da görülebilir. Bu şekilde kullanılabilir. Az sayıda toplama ve çıkarma, çok sayıda çarpmanın yerini alır. Karatsuba algoritması zamandan tasarruf sağlar çünkü bu işlem, önceki n kareler yerine sadece 2'nin tek basamakların n'inci kuvvetine çarpılmasını gerektirir.
Pennsylvania Eyalet Üniversitesi'nde matematikçi olan Martin Fürer, Ayrıca dikey hesaplama yöntemine kıyasla bu yöntemi okulda bir yıl önce öğrenebilirsiniz çünkü daha kolay ve hesaplamayı doğrusal zamanda hızlı bir şekilde tamamlayabilirsiniz. Bu neredeyse sayıları sağdan sola okumak kadar hızlı ". Martin Fürer ayrıca 2007 yılında dünyanın en hızlı çarpma algoritmasını yarattı.
Büyük sayıların çarpımı ile uğraşırken, orijinal sayıyı neredeyse basamak sayısı kadar parçalara ayırmak için Karatsuba işlemini tekrarlayabilirsiniz. Her bölme sayesinde, çok sayıda çarpımı, daha az işlem gerektiren eklemeler ve çıkarmalarla değiştirebilirsiniz.
Yeni Güney Galler Üniversitesi'nde matematikçi ve yeni makalenin ortak yazarlarından biri olan David Harvey, "Karatsuba algoritması bazı çarpmaları eklemelere dönüştürebilir ve eklemeler bilgisayarlar için daha hızlıdır" dedi.
Karatsuba'nın yöntemini kullanarak, n'nin tek hanenin 1.58'inci kuvvetine çarpımından sonra iki n basamaklı çarpan arasındaki çarpımı elde edebilirsiniz. Daha sonra 1971'de Arnold Schönhage ve Volker Strassen, büyük sayıları n × log n × log (log n) alt-tek basamaklarla çarpabilen bir yöntem yayınladı; burada log n, n'nin logaritmasıdır. Karatsuba'nın iki 1 milyar haneyi çarpmak için yöntemini kullanırken, yaklaşık 165 trilyon ek adım gerekir.
(Kaynak: bu makale)
Schönhage ve Strassen'in büyük sayıları çarpma algoritması, sonraki büyük sayı çarpma algoritmasının geliştirilmesinde iki önemli uzun vadeli etkiye sahiptir.
Öncelikle büyük sayı çarpımı alanında ilk kez sinyal işleme teknolojisi alanından ** Hızlı Fourier Dönüşümü adı verilen bir yöntem sahaya tanıtıldı. Sonraki her hızlı çarpma algoritması bu yönteme dayanmaktadır.
Bir başka önemli etki de aynı makalede Schönhage ve Strassen'in buldukları algoritmadan daha hızlı bir algoritma olması gerektiğini speküle etmeleridir - yalnızca n × log n işlemleri gerektiren bir yöntem ve bu algoritma En hızlı algoritma olacak. Spekülasyonları temelde bir önseziye dayanmaktadır, çünkü büyük sayıların çarpımı için gereken minimum temel işlem sayısının n × log n × log (log n) formülünden daha zarif olması gerektiğini düşünüyorlar.
"Bu aslında çok yaygın bir fikir birliği. İnsanlar, çarpma işleminin estetik açıdan çok önemli bir temel işlem olduğundan, böylesine önemli bir işlemin karmaşıklığın sınırı için çok zarif bir açıklama formülü gerektirdiğini düşünüyor." Fürer, "Genel deneyime göre, en temel şeylerin matematiksel açıklaması her zaman çok zariftir." Dedi.
Ancak, sonraki 36 yıl içinde, hiç kimse büyük sayıların çarpımı için Schönhage ve Strassen'den daha hızlı bir algoritma bulamadı, bu daha az zarif ve n × log n × log (log n) temel işlemleri gerektiren.
(Kaynak: quanta)
Fürer, 2007 yılına kadar nihayet bu alanda ilerleme kaydedilemeyen durumu kırdı ve bu keşif, bu alandaki insan keşfinin kapağını açmış gibi görünüyor. Son on yılda, matematikçiler sürekli olarak daha hızlı çarpma algoritmaları keşfettiler ve her algoritma n × log n'ye öncekinden daha yakın, ancak hiçbir zaman tam olarak ulaşamadı. Harvey ve van der Hoeven geçen aya kadar nihayet ulaştı.
Yöntemleri, önceki ana yöntemin iyileştirilmesi ve optimizasyonudur. Yöntemleri ayrıca sayıları böler, Hızlı Fourier Dönüşümünün geliştirilmiş bir versiyonunu kullanır ve aynı zamanda bu alandaki son kırk yıldaki diğer gelişmelerin sonuçlarını da kullanırlar. van der Hoeven, "Hızlı Fourier dönüşümünü daha radikal bir şekilde kullanıyoruz. Metodumuz bir kez yerine çok sayıda hızlı Fourier dönüşümü gerektiriyor ve ayrıca daha fazla çarpma yerine toplama ve çıkarma kullanıyor. . "
Harvey ve van der Hoeven'in algoritması, çarpmanın n × log n temel çarpımlarla tamamlanabileceğini kanıtladı. Ancak bu yöntemden daha hızlı bir algoritmanın olmadığını ispatlayamazlar. Bu yöntemin en iyi yöntem olduğunu kanıtlamak, bu algoritmayı bulmaktan çok daha zordur. Şubat ayının sonunda, Aarhus Üniversitesi'nden bir grup bilgisayar bilimcisi bir makale yayınladı ve başka bir kanıtlanmamış varsayım doğruysa, bu yöntemin çarpma için en hızlı algoritma olduğunun gerçekten kanıtlanacağını iddia etti.
Bu yeni algoritma teoride büyük önem taşıyacak olsa da, aslında önceki algoritmaya göre çok fazla değişime uğramamış, halihazırda kullandığımız algoritmadan sadece biraz daha iyi.
Van der Hoeven, "Bu algoritmayı kullanmak, en iyi durumda önceki algoritmadan yalnızca üç kat daha hızlıdır" dedi. "Eskisinden çok daha hızlı değil."
Ek olarak, bilgisayar donanımının tasarımı son birkaç yılda birçok değişikliğe uğramıştır. Yirmi yıl önce, bilgisayarlar toplamayı çarpmadan çok daha hızlı gerçekleştirdi. Ancak, çarpma ve toplama arasındaki işletim hızı farkı son 20 yılda büyük ölçüde azaldı ve bazı yonga mimarilerinde çarpma, toplamadan daha hızlıdır. Harvey, belirli donanımları kullanırken, "daha önce hayal bile edilemeyen, toplama hızını artırmak için bilgisayarın birden fazla çarpma yapmasına bile izin verebilirsiniz" dedi.
Bununla birlikte, donanım zaman içinde gelişmeye devam eder, ancak bir işlem için en iyi algoritma arayışı sonsuz ve sonsuzdur. Bilgisayar gelecekte ne hale gelecek olursa olsun, Harvey ve van der Hoeven'in algoritması her zaman en etkili çarpma yöntemlerinden biri olacak.
Şekil Yeni algoritmanın uzun versiyonu (Kaynak: quanta)
