Çarpma algoritması - Multiplication algorithm
Bir çarpma algoritması bir bir algoritma (veya yöntemi) çarpma iki sayı. Sayıların boyutuna bağlı olarak farklı algoritmalar kullanılır. Ondalık sistemin ortaya çıkmasından bu yana verimli çarpma algoritmaları var olmuştur.
ızgara yöntemi
Izgara yöntemi (veya kutu yöntemi) genellikle en öğrencilere öğretilen birden çok basamaklı çoğalması için bir giriş metodu olduğu ilkokul veya ilkokul . 1990'ların sonlarından beri İngiltere ve Galler'de ulusal ilkokul matematik müfredatının standart bir parçası olmuştur.
Her iki faktör de yüzlerce, onluk ve birim parçalarına bölünür ("bölünür") ve daha sonra bu katkılar toplamda nihai cevabı vermek için toplanmadan önce, parçaların ürünleri daha sonra nispeten basit bir yalnızca çarpma aşamasında açıkça hesaplanır. ayrı bir ekleme aşaması.
Örneğin 34 × 13 hesaplaması, ızgara kullanılarak hesaplanabilir:
300 40 90 + 12 ———— 442
× | 30 | 4 |
---|---|---|
10 | 300 | 40 |
3 | 90 | 12 |
ardından ya tek bir toplamda (sağa bakın) ya da satır satır toplamları oluşturarak (300 + 40) + (90 + 12) = 340 + 102 = 442 elde etmek için 442 elde edilir.
Bu hesaplama yaklaşımı (mutlaka açık ızgara düzenlemesi ile olmasa da) kısmi ürün algoritması olarak da bilinir . Özü, basit çarpmaların ayrı ayrı hesaplanması ve tüm toplamaların son toplama aşamasına bırakılmasıdır.
Izgara yöntemi prensipte herhangi bir büyüklükteki faktöre uygulanabilir, ancak alt ürünlerin sayısı basamak sayısı arttıkça hantal hale gelir. Yine de, çok basamaklı çarpma fikrini ortaya koymak için yararlı bir açık yöntem olarak görülüyor; ve çoğu çarpma hesaplamasının bir hesap makinesi veya elektronik tablo kullanılarak yapıldığı bir çağda, pratikte bazı öğrencilerin ihtiyaç duyacağı tek çarpma algoritması olabilir.
Uzun çarpma
Bir ederse pozisyonel rakamı sistem kullanılır, çarparak sayıların doğal yolu olarak okullarda öğretilir uzun çarpma , bazen denilen ilkokul çarpma bazen denilen Standart Algoritma çarpın: çarpılan her hanesi ile çarpan tüm doğru düzgün sonra ve kaydırılan sonuçlar. Tek haneler için çarpım tablosunun ezberlenmesini gerektirir .
Bu, daha büyük sayıları taban 10'da elle çarpmak için kullanılan olağan algoritmadır. Bilgisayarlar başlangıçta çok benzer bir kaydırma ve ekleme algoritması kullandılar, ancak modern işlemciler, daha karmaşık bir fiyata daha verimli algoritmalar kullanarak hızlı çarpmalar için devreleri optimize etti. donanım gerçekleştirme. Kağıt üzerinde uzun çarpma işlemi yapan bir kişi tüm ürünleri yazacak ve sonra bunları toplayacaktır; bir abaküs kullanıcısı , her biri hesaplanır hesaplanmaz ürünleri toplayacaktır.
Örnek
Bu örnek, 23,958,233'ü (çarpan) 5,830 (çarpan) ile çarpmak için uzun çarpma kullanır ve sonuç (ürün) için 139.676.498.390'a ulaşır.
23958233 × 5830 ——————————————— 00000000 ( = 23,958,233 × 0) 71874699 ( = 23,958,233 × 30) 191665864 ( = 23,958,233 × 800) + 119791165 ( = 23,958,233 × 5,000) ——————————————— 139676498390 ( = 139,676,498,390 )
Aşağıdaki sözde kod, yukarıdaki çarpma işlemini açıklar. Sonunda sonuç olan toplamı korumak için yalnızca bir satır tutar. '+=' operatörünün, mevcut değerin toplamını belirtmek ve kompaktlık için işlemi (Java ve C gibi dillere benzer şekilde) depolamak için kullanıldığını unutmayın.
multiply(a[1..p], b[1..q], base) // Operands containing rightmost digits at index 1
product = [1..p+q] // Allocate space for result
for b_i = 1 to q // for all digits in b
carry = 0
for a_i = 1 to p // for all digits in a
product[a_i + b_i - 1] += carry + a[a_i] * b[b_i]
carry = product[a_i + b_i - 1] / base
product[a_i + b_i - 1] = product[a_i + b_i - 1] mod base
product[b_i + p] = carry // last digit comes from final carry
return product
Alan karmaşıklığını optimize etme
D tabanındaki iki giriş numarasındaki toplam basamak sayısı n olsun . Sonucun bellekte tutulması gerekiyorsa, uzay karmaşıklığı önemsizdir Θ( n ). Bununla birlikte, bazı uygulamalarda, tüm sonucun bellekte tutulması gerekmez ve bunun yerine sonucun rakamları hesaplandıkça dışarı aktarılabilir (örneğin, sistem konsoluna veya dosyasına). Bu senaryolarda, uzun çarpmanın bir günlük uzay algoritması olarak kolayca formüle edilebilmesi avantajı vardır ; yani, yalnızca girişteki ( Θ (log n )) basamak sayısının logaritması ile orantılı çalışma alanına ihtiyaç duyan bir algoritma . Bu, çarpılmakta olan sayıların çift logaritmasıdır (log log N ). İşlenenlerin kendilerinin hala bellekte tutulması gerektiğine ve bu analizde Θ( n ) boşluklarının dikkate alınmadığına dikkat edin.
Yöntem, sonucun her bir basamağının yalnızca önceki adımdan elde edilen taşımayı bilerek sağdan sola hesaplanabileceği gözlemine dayanmaktadır. Let bir ı ve b ı olması ı ile, işlenen inci basamaklı bir ve b uzunlukta olması sıfır bıraktığı üzerine fularlanır n , r ı olması ı sonucun inci basamaklı ve C ı olması taşıma için oluşturulmuş r ben (i=1 en sağdaki basamaktır) o zaman
veya
Basit bir endüktif argüman, taşımanın asla n'yi aşamayacağını ve r i için toplam toplamın asla D * n'yi aşamayacağını gösterir : ilk sütuna taşıma sıfırdır ve diğer tüm sütunlar için sütunda en fazla n basamak vardır , ve önceki sütundan en fazla n'lik bir taşıma ( tümevarım hipotezine göre). Toplam en fazla D * n'dir ve bir sonraki sütuna taşıma en fazla D * n / D veya n'dir . Böylece bu değerlerin her ikisi de O(log n ) basamaklarında saklanabilir .
Sözde kodda, günlük alanı algoritması şöyledir:
multiply(a[1..p], b[1..q], base) // Operands containing rightmost digits at index 1
tot = 0
for ri = 1 to p + q - 1 // For each digit of result
for bi = MAX(1, ri - p + 1) to MIN(ri, q) // Digits from b that need to be considered
ai = ri − bi + 1 // Digits from a follow "symmetry"
tot = tot + (a[ai] * b[bi])
product[ri] = tot mod base
tot = floor(tot / base)
product[p+q] = tot mod base // Last digit of the result comes from last carry
return product
Bilgisayarlarda kullanım
Bazı yongalar , çeşitli tamsayı ve kayan noktalı sözcük boyutları için donanımda veya mikro kodda uzun çarpma uygular . İçinde rasgele hassas aritmetik , 2'ye baz grubu ile uzun çarpma kullanımı yaygındır ağırlık , burada ağırlık bit sayısı nispeten küçük sayının çarpımı için, bir kelime var.
Bu yöntemi kullanarak iki sayıyı n basamaklı çarpmak için yaklaşık n 2 işlem gerekir. Daha resmi olarak: basamak sayısının doğal bir boyut metriğini kullanarak, iki n basamaklı sayıyı uzun çarpma kullanarak çarpmanın zaman karmaşıklığı Θ ( n 2 )'dir.
Yazılımda uygulandığında, uzun çarpma algoritmaları, eklemeler sırasında pahalı olabilen taşma ile uğraşmak zorundadır. Tipik bir çözüm, sayıyı küçük bir tabanda temsil etmektir, b , öyle ki, örneğin 8 b , temsil edilebilir bir makine tamsayısıdır. Bir taşma meydana gelmeden önce birkaç ekleme yapılabilir. Sayı çok büyüdüğünde, sonuca bir kısmını ekleriz veya kalan kısmı taşır ve b'den küçük bir sayıya geri göndeririz . Bu işleme normalizasyon denir . Richard Brent bu yaklaşımı Fortran paketinde kullandı, MP.
kafes çarpma
Kafes veya elek ile çarpma algoritmik olarak uzun çarpmaya eşdeğerdir. Bu hesaplama yönlendirir ve tüm çarpma ayıran bir kafes (kâğıt üzerinde bir ızgara) hazırlanmasını gerektirir eklemeler . 1202 yılında Fibonacci'nin Liber Abaci adlı eserinde Avrupa'ya tanıtıldı . Fibonacci, ara hesaplamaları yapmak için sağ ve sol ellerini kullanarak işlemi zihinsel olarak tanımladı. Matrakçı Nasuh , 16. yüzyıldan kalma Umdet-ul Hisab adlı bu kitapta bu yöntemin 6 farklı çeşidini sunmuştur. Osmanlı İmparatorluğu genelinde Enderun okullarında yaygın olarak kullanılmıştır . Napier'in kemikleri veya Napier'in çubukları da, Napier tarafından ölüm yılı olan 1617'de yayınlandığı gibi bu yöntemi kullandı.
Örnekte gösterildiği gibi, çarpan ve çarpan yukarıda ve bir kafesin veya bir eleğin sağında yazılmıştır. Bu bulunursa Hârizmî 'ın 'Aritmetik', Sigler bahsettiği Leonardo'nun kaynaklarından biri, 'Fibonacci Liber Abacı' 2002 yazarı.
- Çarpma aşamasında, kafes, her satırı ve sütunu etiketleyen karşılık gelen rakamların iki basamaklı ürünleri ile doldurulur: onlar basamağı sol üst köşeye gider.
- Toplama aşamasında, kafes köşegenler üzerinde toplanır.
- Son olarak, bir taşıma aşaması gerekliyse, kafesin sol ve alt taraflarında gösterilen cevap, uzun toplama veya çarpma işleminde olduğu gibi onluk basamakları taşıyarak normal forma dönüştürülür.
Örnek
Sağdaki resimler, kafes çarpımı kullanılarak 345 × 12'nin nasıl hesaplanacağını gösterir. Daha karmaşık bir örnek olarak, 23,958,233 çarpı 5,830 (çarpan) hesaplamasını gösteren aşağıdaki resmi düşünün; sonuç 139.676.498.390'dır. 23.958.233'ün kafesin üst kısmında ve 5.830'un sağ tarafta olduğuna dikkat edin. Ürünler kafesi doldurur ve bu ürünlerin toplamı (köşegende) sol ve alt taraflardadır. Daha sonra bu toplamlar gösterildiği gibi toplanır.
2 3 9 5 8 2 3 3 +---+---+---+---+---+---+---+---+- |1 /|1 /|4 /|2 /|4 /|1 /|1 /|1 /| | / | / | / | / | / | / | / | / | 5 01|/ 0|/ 5|/ 5|/ 5|/ 0|/ 0|/ 5|/ 5| +---+---+---+---+---+---+---+---+- |1 /|2 /|7 /|4 /|6 /|1 /|2 /|2 /| | / | / | / | / | / | / | / | / | 8 02|/ 6|/ 4|/ 2|/ 0|/ 4|/ 6|/ 4|/ 4| +---+---+---+---+---+---+---+---+- |0 /|0 /|2 /|1 /|2 /|0 /|0 /|0 /| | / | / | / | / | / | / | / | / | 3 17|/ 6|/ 9|/ 7|/ 5|/ 4|/ 6|/ 9|/ 9| +---+---+---+---+---+---+---+---+- |0 /|0 /|0 /|0 /|0 /|0 /|0 /|0 /| | / | / | / | / | / | / | / | / | 0 24|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0| +---+---+---+---+---+---+---+---+- 26 15 13 18 17 13 09 00 |
01 002 0017 00024 000026 0000015 00000013 000000018 0000000017 00000000013 000000000009 0000000000000 ————————————— 139676498390 |
= 139,676,498,390 |
İkili veya Köylü çarpma
İkili yöntem aynı zamanda köylü çarpımı olarak da bilinir, çünkü köylü olarak sınıflandırılan kişiler tarafından yaygın olarak kullanılır ve bu nedenle uzun çarpım için gerekli çarpım tablolarını ezberlememiştir . Algoritma eski Mısır'da kullanılıyordu. Başlıca avantajları, hızlı bir şekilde öğretilebilmesi, ezber gerektirmemesi ve kağıt ve kalem yoksa poker fişleri gibi jetonlar kullanılarak gerçekleştirilebilmesidir. Dezavantajı, uzun çarpma işleminden daha fazla adım almasıdır, bu nedenle büyük sayılar için hantal olabilir.
Açıklama
Kâğıda, çarpanı art arda yarıya indirdiğinizde elde ettiğiniz sayıları, kalanı yok sayarak bir sütuna yazın; yanındaki bir sütunda, çarpanı art arda ikiye katlayın. İlk sayının son basamağının çift olduğu her satırın üzerini çizin ve ürünü elde etmek için kalan sayıları ikinci sütuna ekleyin.
Örnekler
Bu örnek, 33 sonucunu elde etmek için 11 ile 3'ü çarpmak için köylü çarpmasını kullanır.
Decimal: Binary: 11 3 1011 11 5 6 101 110 2121011001 24 1 11000 —— —————— 33 100001
Adımları açıkça açıklamak:
- üstte 11 ve 3 yazıyor
- 11 yarıya bölünür (5.5) ve 3 ikiye katlanır (6). Kesirli kısım atılır (5.5, 5 olur).
- 5 ikiye bölünür (2.5) ve 6 ikiye katlanır (12). Kesirli kısım atılır (2.5, 2 olur). Sol sütundaki (2) rakam çift olduğundan, sağ sütundaki (12) rakam atılır.
- 2 yarıya bölünür (1) ve 12 ikiye katlanır (24).
- Tüm çizilmemiş değerler toplanır: 3 + 6 + 24 = 33.
Yöntem işe yarar çünkü çarpma dağıtıcıdır , yani:
Daha önceki örneklerdeki rakamları kullanarak daha karmaşık bir örnek (23.958,233 ve 5.830):
Decimal: Binary: 583023958233101101100011010110110110010010110110012915 47916466 101101100011 10110110110010010110110010 1457 95832932 10110110001 101101101100100101101100100 72819166586410110110001011011011001001011011001000364383331728101101100101101101100100101101100100001827666634561011011010110110110010010110110010000091 1533326912 1011011 1011011011001001011011001000000 45 3066653824 101101 10110110110010010110110010000000 2261333076481011010110110110010010110110010000000011 12266615296 1011 1011011011001001011011001000000000 5 24533230592 101 10110110110010010110110010000000000 249066461184101011011011001001011011001000000000001 98132922368 1 1011011011001001011011001000000000000 ———————————— 1022143253354344244353353243222210110 (before carry) 139676498390 10000010000101010111100011100111010110
Bilgisayarlarda ikili çarpma
Bu, köylü çarpmasının bir çeşididir.
Taban 2'de, uzun çarpma neredeyse önemsiz bir işleme indirgenir. Her bir '1' bit için çarpan , kaydırma çarpılan uygun bir miktarda, ve daha sonra ampul değerleri toplar. Bazı işlemcilerde , özellikle çarpan küçükse veya her zaman aynıysa, çarpma talimatları yerine bit kaydırma ve ekleme kullanmak daha hızlıdır.
Kaydır ve ekle
Tarihsel olarak, bilgisayarlar küçük tam sayıları çarpmak için bir "kaydır ve ekle" algoritması kullandılar. Hem taban 2 uzun çarpma hem de taban 2 köylü çarpması bu aynı algoritmaya indirgenir. Taban 2'de, çarpanın tek basamağıyla çarpma, basit bir mantıksal AND işlemi dizisine indirgenir . Her bir kısmi ürün, her bir kısmi ürün hesaplanır hesaplanmaz, bir cari toplama eklenir. Şu anda mevcut olan mikroişlemcilerin çoğu , donanım çarpanlarında veya mikro kodda çeşitli tam sayı ve kayan nokta boyutları için bu veya diğer benzer algoritmaları ( Both kodlaması gibi ) uygular .
Halihazırda mevcut işlemcilerde, bit bazında kaydırma talimatı, çarpma talimatından daha hızlıdır ve ikinin kuvvetleriyle çarpma (sola kaydırma) ve bölme (sağa kaydırma) için kullanılabilir. Bir sabitle çarpma ve bir sabitle bölme, bir dizi kaydırma ve toplama veya çıkarma işlemi kullanılarak gerçekleştirilebilir. Örneğin, yalnızca bit kaydırma ve toplama kullanarak 10 ile çarpmanın birkaç yolu vardır.
((x << 2) + x) << 1 # Here 10*x is computed as (x*2^2 + x)*2 (x << 3) + (x << 1) # Here 10*x is computed as x*2^3 + x*2
Bazı durumlarda, bu tür kaydırmalar ve toplamalar veya çıkarmalar, donanım çarpanlarından ve özellikle bölücülerden daha iyi performans gösterecektir. Bir formun bir sayısına veya çoğu zaman bir bölme , bu kadar kısa bir diziye dönüştürülebilir.
Dizilerin Bu tür her zaman bir "çarpma" talimat olmayan bilgisayarlar için kullanılacak zorunda ve ayrıca kayan noktalı sayılara uzantısı tarafından kullanılıp kullanılamayacağını hesaplanması ile bir cümledeki kaymalar 2 * x olarak x + x olarak bu mantıksal olarak eşdeğerdir.
Çeyrek kare çarpma
Bazı kaynakların Babil matematiğine (MÖ 2000-1600) atfettiği taban fonksiyonunu içeren aşağıdaki özdeşlik kullanılarak iki miktar çeyrek kareler kullanılarak çarpılabilir.
Biri ise x + y ve x - y garip, diğer, daha sonra söz alan dörtte bir oranında azaltır böylece kareler 1 mod 4 olan, çok tek olduğu; çıkarma daha sonra çeyrekleri iptal eder ve kalanların atılması, aynı ifadeyle taban fonksiyonları olmadan karşılaştırıldığında herhangi bir fark yaratmaz. Aşağıda, 0'dan 18'e kadar olan rakamlar için geri kalanı atılan çeyrek karelerin bir arama tablosu bulunmaktadır; bu, 9×9'a kadar sayıların çarpılmasına izin verir .
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
⌊ n 2 / 4⌋ | 0 | 0 | 1 | 2 | 4 | 6 | 9 | 12 | 16 | 20 | 25 | 30 | 36 | 42 | 49 | 56 | 64 | 72 | 81 |
Örneğin, 9 ile 3'ü çarpmak isterseniz, toplamın ve farkın sırasıyla 12 ve 6 olduğunu gözlemlersiniz. Tabloda bu değerlerin her ikisine de bakıldığında, farkı 27 olan, 9 ve 3'ün çarpımı olan 36 ve 9 elde edilir.
Antoine Voisin, çarpma işlemine yardımcı olmak için 1817'de 1'den 1000'e kadar çeyrek kareler tablosu yayınladı. 1'den 100.000'e kadar daha büyük bir çeyrek kareler tablosu 1856'da Samuel Laundy tarafından ve 1888'de Joseph Blater tarafından 1'den 200000'e kadar bir tablo yayınlandı.
Analog bilgisayarlarda , iki analog giriş sinyalinin ürünü olan bir analog sinyal oluşturmak için çeyrek kare çarpanlar kullanıldı . Bu uygulamada, işlemsel yükselteçler kullanılarak iki giriş voltajının toplamı ve farkı oluşturulur . Bunların her birinin karesi, parçalı lineer devreler kullanılarak yaklaştırılır . Son olarak, iki karenin farkı, bir başka işlemsel yükselteç kullanılarak dörtte birlik bir faktörle oluşturulur ve ölçeklenir.
1980'de Everett L. Johnson, bir dijital çarpanda çeyrek kare yöntemini kullanmayı önerdi . Örneğin, 8 bitlik iki tamsayının çarpımını oluşturmak için, dijital aygıt toplamı ve farkı oluşturur, her iki niceliği bir kareler tablosunda arar, sonuçların farkını alır ve iki biti sayıya kaydırarak dörde böler. sağ. 8 bitlik tam sayılar için, çeyrek kareler tablosu 2 9 -1=511 girişe sahip olacaktır (olası toplamların tüm aralığı 0..510 için bir giriş, 0..255 aralığında yalnızca ilk 256 girişi kullanan farklar) veya 2 9 -1=511 giriş (negatif farklar için 2-tamamlayıcı ve 9-bit maskeleme tekniğini kullanarak, farklılıkların işaretini test etmekten kaçınır), her giriş 16-bit genişliğindedir (giriş değerleri 0²/4 )=0 ila (510²/4)=65025).
Çeyrek kare çarpan tekniği, bir donanım çarpanı için herhangi bir desteği olmayan 8 bitlik sistemlere de fayda sağlamıştır. Charles Putney bunu 6502 için uyguladı .
Büyük girdiler için hızlı çarpma algoritmaları
İki basamaklı sayıları çarpmak için en hızlı algoritma nedir ?
Karmaşık çarpma algoritması
Karmaşık çarpma normalde dört çarpma ve iki toplama içerir.
Veya
Ancak çarpma sayısını üçe indirmenin bir yolu var.
( a + bi ) · ( c + di ) çarpımı aşağıdaki şekilde hesaplanabilir.
- k 1 = c · ( a + b )
- k 2 = bir · ( d - c )
- k 3 = b · ( c + d )
- Gerçek kısım = k 1 − k 3
- Hayali kısım = k 1 + k 2 .
Bu algoritma, dört yerine yalnızca üç çarpma ve iki yerine beş toplama veya çıkarma kullanır. Bir çarpma, elle hesaplamada olduğu gibi, üç toplama veya çıkarma işleminden daha pahalıysa, o zaman hızda bir kazanç vardır. Modern bilgisayarlarda çarpma ve toplama yaklaşık olarak aynı süreyi alabilir, bu nedenle hız artışı olmayabilir. Kayan nokta kullanılırken bir miktar hassasiyet kaybı olabileceği konusunda bir takas vardır.
İçin hızlı Fourier dönüşümleri (FFTs) (ya da herhangi bir doğrusal dönüşüm ) kompleksi çarpar, sabit katsayılar ile olan c + di (denilen Twiddle faktörler (eklemeler iki durumda FFTs olarak), D - c ve c + d ) önceden hesaplanabilir . Bu nedenle, sadece üç çarpma ve üç toplama gereklidir. Bununla birlikte, bu şekilde bir toplama için çarpma işlemi yapmak, modern kayan nokta birimleriyle artık faydalı olmayabilir .
Karatsuba çarpma
Bilgisayar cebir sistemleri ve bignum kitaplıkları gibi birkaç bin basamak aralığında sayıları çarpması gereken sistemler için uzun çarpma çok yavaştır. Bu sistemler, 1960'da keşfedilen (1962'de yayınlandı) Karatsuba çarpmasını kullanabilir . Karatsuba'nın yönteminin kalbi, iki basamaklı çarpma işleminin klasik olarak gerekli olan dört çarpma yerine yalnızca üç ile yapılabileceği gözleminde yatar. Bu, şimdi böl ve yönet algoritması olarak adlandırılan şeyin bir örneğidir . İki adet 2 basamaklı temel m sayısını çarpmak istediğimizi varsayalım : x 1 m + x 2 ve y 1 m + y 2 :
- hesapla x 1 · y 1 , sonucu F olarak adlandırın
- hesapla x 2 · y 2 , sonucu G olarak adlandırın
- hesaplayın ( x 1 + x 2 ) · ( y 1 + y 2 ), sonucu H olarak adlandırın
- H - F - G hesaplayın , sonucu K olarak adlandırın ; bu sayı x 1 · y 2 + x 2 · y 1'e eşittir
- F · m 2 + K · m + G'yi hesaplayın .
Temel m sayılarının bu üç ürününü hesaplamak için, aynı numarayı yine etkili bir şekilde özyineleme kullanarak kullanabiliriz . Sayılar hesaplandıktan sonra, onları bir araya toplamamız gerekir (4. ve 5. adımlar), bu da yaklaşık n işlem alır .
Karatsuba çarpması, O ( n log 2 3 ) ≈ O( n 1.585 ) zaman karmaşıklığına sahiptir ve bu yöntemi, uzun çarpmadan önemli ölçüde daha hızlı hale getirir. Özyineleme yükü nedeniyle, Karatsuba'nın çarpması, n'nin küçük değerleri için uzun çarpmadan daha yavaştır ; tipik uygulamalar bu nedenle küçük n değerleri için uzun çarpmaya geçer .
Karatsuba'nın algoritması, uzun çarpmadan asimptotik olarak daha hızlı olan ve bu nedenle hızlı çarpma teorisi için başlangıç noktası olarak görülebilen çarpma için bilinen ilk algoritmaydı.
1963 yılında Peter Ungar ayarı önerilen m için i kompleks çarpma algoritması benzer bir azalma elde etmek. ( a + bi ) · ( c + di ) ile çarpmak için şu adımları izleyin:
- hesapla b · d , sonucu F olarak adlandırın
- a · c hesaplayın , sonucu G olarak adlandırın
- hesapla ( a + b ) · ( c + d ), sonucu H olarak adlandır
- sonucun sanal kısmı K = H − F − G = a · d + b · c
- sonucun gerçek kısmı G − F = a · c − b · d
Önceki bölümdeki algoritma gibi, bu da üç çarpma ve beş toplama veya çıkarma gerektirir.
Toom-Aşçı
Başka bir çarpma yöntemine Toom-Cook veya Toom-3 denir. Toom–Cook yöntemi, çarpılacak her sayıyı birden çok parçaya böler. Toom-Cook yöntemi, Karatsuba yönteminin genellemelerinden biridir. Üç yollu bir Toom-Cook , beş N boyutunda çarpma maliyetine 3N boyutunda bir çarpma yapabilir. Bu, işlemi 9/5 oranında hızlandırırken, Karatsuba yöntemi 4/3 oranında hızlandırır.
Gittikçe daha fazla parça kullanmak özyinelemeli çarpmalar için harcanan süreyi daha da azaltabilse de, toplamalardan ve rakam yönetiminden kaynaklanan ek yük de büyür. Bu nedenle, Fourier dönüşümleri yöntemi birkaç bin basamaklı sayılar için tipik olarak daha hızlıdır ve daha büyük sayılar için asimptotik olarak daha hızlıdır.
Fourier dönüşüm yöntemleri
Strassen'e (1968) dayanan temel fikir , hızlı tamsayı çarpımı gerçekleştirmek için hızlı polinom çarpımı kullanmaktır. Algoritma pratik hale getirildi ve 1971 yılında Schönhage ve Strassen tarafından teorik garantiler sağlanarak Schönhage-Strassen algoritması ortaya çıktı . Detaylar aşağıdaki gibidir: Aşağıda özetlenen süreçte taşmaya neden olmayacak en büyük w tamsayısını seçiyoruz . Sonra iki sayıyı aşağıdaki gibi m grup w bitine böldük
Biz de polinomların olarak bu sayıların bakmak x , x = 2 w , almak
O zaman şunu söyleyebiliriz,
Açıkça yukarıdaki ayar, iki polinom a ve b'nin polinom çarpımı ile gerçekleştirilir . Şimdi kritik adım, yukarıdaki çarpmaları saf O ( m 2 ) zamanından daha hızlı gerçekleştirmek için polinomların Hızlı Fourier çarpımını kullanmaktır .
Fourier dönüşümlerinin modüler ayarında kalmak için , birlik kökü (2 m ) olan bir halka arıyoruz . Bu nedenle çarpma modulo N yapıyoruz (ve dolayısıyla Z / NZ halkasında ). Ayrıca, N seçilmelidir, böylece hiçbir 'çevreleme' olmaz, esasen hiçbir modülo N indirgemesi meydana gelmez. Bu nedenle, N seçimi çok önemlidir. Örneğin, şu şekilde yapılabilir,
Halka Z / NZ böylece (2 olurdu m o kontrol edilebilir, aynı zamanda, yani) birlik inci kökü, 8. C k < N ve dolayısıyla ortaya çıkar bükülür.
Algoritma, Θ ( n log( n ) log(log( n ))) zaman karmaşıklığına sahiptir ve uygulamada 10.000 ila 40.000'den fazla ondalık basamaklı sayılar için kullanılır. 2007'de bu Martin Fürer ( Fürer'in algoritması ) tarafından karmaşık sayılar üzerinde Fourier dönüşümleri kullanılarak n log( n ) 2 Θ( log * ( n )) zaman karmaşıklığını verecek şekilde geliştirildi . Anindya De, Chandan Saha, Piyush Kurur ve Ramprasad Saptharishi, 2008'de modüler aritmetik kullanarak aynı çalışma süresini elde eden benzer bir algoritma verdiler . Yukarıdaki materyal bağlamında, bu son yazarların başardıkları şey, N'yi 2 3 k + 1'den çok daha az bulmaktır , böylece Z / NZ'nin (2 m ) birlik kökü vardır. Bu, hesaplamayı hızlandırır ve zaman karmaşıklığını azaltır. Ancak, bu ikinci algoritmalar, pratik olmayan büyük girdiler için yalnızca Schönhage-Strassen'den daha hızlıdır.
Mart 2019'da David Harvey ve Joris van der Hoeven , O ( n log n ) çarpma algoritmasını açıklayan bir makale yayınladı .
Kullanılarak sayı-teorik dönüşümü yerine kesikli Fourier dönüşümü engeller yuvarlama hata modüler aritmetiği kullanılarak yerine problemlerin kayan nokta aritmetik. FFT'nin çalışmasını sağlayan çarpanlara ayırmayı uygulamak için, dönüşümün uzunluğu küçük asal sayılara çarpanlara ayrılabilmeli ve N − 1 faktörü olmalıdır , burada N alan boyutudur. Özel olarak, bir Galois'in alan GF (kullanarak hesaplama k 2 ), k a, Mersenne asal bir 2'nin bir katı büyüklükte dönüşüm kullanımına izin verir; örneğin k = 2 31 − 1 , 2 32'ye kadar dönüştürme boyutlarını destekler .
Alt sınırlar
Tek bir işlemcide iki n bitlik sayıyı çarpmak için önemsiz bir Ω ( n ) alt sınırı vardır ; hiçbir eşleştirme algoritması (geleneksel makinelerde, yani Turing'e eşdeğer makinelerde) veya daha keskin bir alt sınır bilinmemektedir. Çarpma, herhangi bir asal p için AC 0 [ p ] dışındadır , yani bir ürünü hesaplayabilen VE, OR, DEĞİL ve MOD p geçitlerini kullanan sabit derinlikli, polinom (veya hatta üslü) boyutlu devreler ailesi yoktur . Bu, MOD q'nun sabit derinlikli bir azalmadan çarpmaya kadar devam eder. Çarpma için alt sınırlar, bazı dallanma programları sınıfları için de bilinmektedir .
polinom çarpımı
Yukarıdaki tüm çarpma algoritmaları, polinomları çarpmak için de genişletilebilir . Örneğin, Strassen algoritması polinom çarpımı için kullanılabilir. Alternatif olarak, polinomları tek bir ikili çarpıma dönüştürmek için Kronecker ikame tekniği kullanılabilir.
Cebirsel formüllerin çarpımına izin vermek için uzun çarpma yöntemleri genelleştirilebilir:
14ac - 3ab + 2 multiplied by ac - ab + 1
14ac -3ab 2 ac -ab 1 ———————————————————— 14a2c2 -3a2bc 2ac -14a2bc 3 a2b2 -2ab 14ac -3ab 2 ——————————————————————————————————————— 14a2c2 -17a2bc 16ac 3a2b2 -5ab +2 =======================================
Sütun tabanlı çarpmanın başka bir örneği olarak, 23 uzun ton (t), 12 yüz ağırlık (cwt) ve 2 çeyrek (qtr) 47 ile çarpmayı düşünün. Bu örnekte kaçınılması gereken ölçüler kullanılır: 1 t = 20 cwt, 1 cwt = 4 qtr.
t cwt qtr 23 12 2 47 x ———————————————— 141 94 94 940 470 29 23 ———————————————— 1110 587 94 ———————————————— 1110 7 2 ================= Answer: 1110 ton 7 cwt 2 qtr
Önce çeyrekleri 47 ile çarpın, sonuç 94 ilk çalışma alanına yazılır. Ardından, cwt 12*47 = (2 + 10)*47'yi çarpın, ancak henüz kısmi sonuçları (94, 470) toplamayın. Aynı şekilde 23'ü 47 ile çarparak (141, 940) elde ederiz. Çeyrek sütunu toplanır ve sonuç ikinci çalışma alanına yerleştirilir (bu durumda önemsiz bir hareket). 94 çeyrek 23 cwt ve 2 qtr'dir, bu nedenle 2'yi cevaba yerleştirin ve 23'ü soldaki bir sonraki sütuna koyun. Şimdi cwt sütunundaki üç girişi 587 vererek toplayın. Bu 29 t 7 cwt, yani 7'yi cevaba ve 29'u soldaki sütuna yazın. Şimdi ton sütununu ekleyin. Yapılması gereken bir ayar yoktur, bu nedenle sonuç sadece kopyalanır.
Aynı düzen ve yöntemler, herhangi bir geleneksel ölçüm ve eski İngiliz £sd sistemi gibi ondalık olmayan para birimleri için kullanılabilir .
Ayrıca bakınız
- ikili çarpan
- Bölme algoritması
- logaritma
- Zihinsel hesaplama
- prosthaferez
- Sürgülü hesap cetveli
- Trachtenberg sistemi
- Bir polinomun değerlendirilmesi için Horner şeması
- Kalıntı sayı sistemi § Başka bir hızlı çarpma algoritması için çarpma, lineer cebir gibi birçok işlem sırayla yapıldığında özellikle verimlidir
- baba çarpanı
- Wallace ağacı
Referanslar
daha fazla okuma
- Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
- Savard, John JG (2018) [2006]. "İleri Aritmetik Teknikleri" . dörtlü blok . 2018-07-03 tarihinde kaynağından arşivlendi . 2018-07-16 alındı .
- Johanson, Kenny. Düşük Güç ve Düşük Karmaşıklık Kaydır ve Ekle Tabanlı Hesaplamalar (PDF) (Tez tezi). Bilim ve Teknolojide Linköping Çalışmaları (1 ed.). Linköping, İsveç: Elektrik Mühendisliği Bölümü, Linköping Üniversitesi . ISBN'si 978-91-7393-836-5. ISSN 0345-7524 . No 1201. Arşivlenmiş (PDF) 2017-08-13 tarihinde orijinalinden . 2021-08-23 alındı . (x+268 sayfa)
Dış bağlantılar
temel aritmetik
- UCSMP Günlük Matematikte Aritmetiğin Birçok Yolu
- Antik matematik hakkında bir Powerpoint sunumu
- Kafes Çarpma Flash Video