Ç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

İlk önce, satırlarını ve sütunlarını çarpılacak sayılarla işaretleyerek ızgarayı kurun. Ardından, üst üçgenlerde onlarca, altta birler rakamı olan kutuları doldurun.
Son olarak, çapraz yolları toplayın ve cevabı almak için gerektiği kadar taşıyın.

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
2   12       10  1100
1   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:
5830  23958233       1011011000110  1011011011001001011011001
2915  47916466       101101100011  10110110110010010110110010
1457  95832932       10110110001  101101101100100101101100100
728  191665864       1011011000  1011011011001001011011001000
364  383331728       101101100  10110110110010010110110010000
182  766663456       10110110  101101101100100101101100100000
91  1533326912       1011011  1011011011001001011011001000000
45  3066653824       101101  10110110110010010110110010000000
22  6133307648       10110  101101101100100101101100100000000
11 12266615296       1011  1011011011001001011011001000000000
5  24533230592       101  10110110110010010110110010000000000
2  49066461184       10  101101101100100101101100100000000000
1  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ı

Bilgisayar biliminde çözülmemiş problem :

İ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 1k 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 :

  1. hesapla x 1 · y 1 , sonucu F olarak adlandırın
  2. hesapla x 2 · y 2 , sonucu G olarak adlandırın
  3. hesaplayın ( x 1 + x 2 ) · ( y 1 + y 2 ), sonucu H olarak adlandırın
  4. H - F - G hesaplayın , sonucu K olarak adlandırın ; bu sayı x 1 · y 2 + x 2 · y 1'e eşittir
  5. 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:

  1. hesapla b · d , sonucu F olarak adlandırın
  2. a · c hesaplayın , sonucu G olarak adlandırın
  3. hesapla ( a + b ) · ( c + d ), sonucu H olarak adlandır
  4. sonucun sanal kısmı K = HFG = a · d + b · c
  5. sonucun gerçek kısmı GF = a · cb · 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

Hızlı Fourier dönüşümleri (FFT'ler) kullanılarak 1234 × 5678 = 7006652 ile çarpmanın gösterimi. 85 birliğin 8. kökü olarak seçilerek modulo 337 tamsayılarındaki sayı-teorik dönüşümler kullanılır. Açıklama amacıyla taban 2w yerine taban 10 kullanılır .

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

Referanslar

daha fazla okuma

Dış bağlantılar

temel aritmetik

Gelişmiş algoritmalar