Algoritam množenja
Algoritam množenja je algoritam (ili metoda) za množenje dva broja. U zavisnosti od veličine brojeva, mogu se koristiti različiti algoritmi. Efikasni algoritmi množenja postoje još od pojave decimalnog sistema.
Metod mreže (grid metod)
Metod mreže ili metod kutije je uvodni metod za množenje višecifrenih brojeva, i često se uči u osnovnoj školi. To je standardni deo nacionalnog plana i programa za matematiku u osnovnim školama u Engleskoj i Velsu od kasnih 1990-ih godina. Oba faktora (broja) su podeljena na stotine, desetice i jedinice, i proizvodi delova se zatim računaju eksplicitno u relativno jednostavnoj fazi množenja, pre nego što se na kraju saberu da bi se dobio konačni rezultat.[1]
Primer je množenje 34x13, može se izračunati korišćenjem mreže:
300 40 90 + 12 ———— 442
× 30 4 10 300 40 3 90 12
a zatim se sabiraju da bi se dobilo 442, bilo u jednoj sumi, ili kroz formiranje red po red zbirova (300 + 40) + (90 + 12) = 340 + 102 = 442.
Ovaj pristup računanja (mada ne obavezno sa eksplicitnim aranžmanom mreže) je takođe poznat i kao algoritam delimičnih proizvoda. Njegova suština je odvojeno računanje jednostavnih množenja, pri čemu se sabiranje ostavlja za krajnju fazu.
Metod mreže se u principu može primeniti na faktore bilo kojih veličina, iako broj potproizvoda može postati jako veliki kako se povećava broj cifara. Svakako predstavlja korisni eksplicitni metod kao uvod za ideju množenja višecifrenih brojeva; i u doba kada se većina računanja vrši pomoću digitrona, ovo može biti jedini algoritam množenja koji će učenicima ikad biti potreban.
Dugo množenje
Ako se koristi pozicioni sistem brojeva, prirodan način množenja koji se uči u školama je metod dugog množenja, nekad nazivan i standardnim algoritmom: pomnožiti množenik svakom cifrom množioca i onda ih sabrati sve ispravno. Ovaj način zahteva memorisanje tablice množenja za jednocifrene brojeve.
Ovo je uobičajeni algoritam za množenje većih brojeva na papiru, čija je osnova 10. Kompjuteri su na početku koristili sličan algoritam pomeranja i dodavanja brojeva čija je osnova 2, ali moderni procesori imaju optimizovana kola za brza množenja koristeći efikasnije algoritme, po ceni složenije hardverske realizacije. Osoba koja radi dugo množenje na papiru će zapisati sve proizvode i zatim ih sabrati, ali osoba koja koristi abakus će sabirati proizvode nakon svakog računanja.
Primer
Ovaj primer koristi dugo množenje da bi se pomnožio 23 958 233 (množenik) sa 5830 (množilac), i dobija se 139 676 498 390 (rezultat).
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 )
Ispod se nalazi pseudokod koji opisuje proces množenja naveden iznad. U njoj se nalazi samo jedan red koji održava sumu koja će na kraju biti finalni rezultat. Obratiti pažnju da se operator += koristi da označi sumu postojeće vrednosti i sačuva operaciju, kao u programskim jezicima C i Java.
multiply(a[1..p], b[1..q], base) // Operandi na desnoj poziciji sadrže cifru 1 product = [1..p+q] //Dodeliti prostor za rezultat for b_i = 1 to q // za sve cifre u b carry = 0 for a_i = 1 to p //za sve cifre u a product[a_i + b_i - 1] += carry + a[ai] * b[bi] carry = product[ai + bi - 1] / base product[a_i + b_i - 1] = product[ai + bi - 1] mod base product[b_i + p] += carry // poslednja cifra dolazi iz konačnog prenosa return product
Množenje rešetkom
Množenje rešetkom ili sitom je algoritamski ekvivalent dugog množenja. Zahteva pipremu rešetke, tj mreže nacrtane na papiru koja vodi računanje i razdvaja množenja od sabiranja. Prvi put je korišćen u Evropi 1202. godine u Fibonačijevoj "Liber Abaci". Leonardo opisuje ovu operaciju kao mentalnu, koristeći i desnu i levu ruku kako bi prenosio prelazna računanja. Matrakci Nasuh je predstavio 6 različitih varijanti ove metode u knjizi iz 16.veka "Umdet-ul Hisab". Korišćena je u Enderun školama širom Otomanskog carstva. Napijerove šipke ili kosti su takođe koristile ove metode.
Kao što je prikazano u primeru, množenik i množilac su napisani iznad i desno od rešetke ili sita. Tokom faze množenja, rešetka se popunjava dvocifrenim proizvodima odgovarajućih cifara koje označavaju svaki red i kolonu. Desetice idu u gornji levi ugao.
Tokom faze sabiranja, rešetka se sabira na dijagonalama. Na kraju, ako je neophodna faza pomeranja, rešenje prikazano na levim i donjim stranama rešetke se konvertuje u normalnu formu prenosom cifara desetica kao u algoritmu dugog množenja.
Primer
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4e/Hindu_lattice.svg/220px-Hindu_lattice.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a6/Hindu_lattice_2.svg/220px-Hindu_lattice_2.svg.png)
Slika na desnoj strani pokazuje kako izračunati 345 × 12 koristeći množenje rešetkom. Kao složeniji primer možemo razmotriti sliku ispod koja prikazuje množenje 23 958 233 sa 5830, rezultat je 139 676 498 390. Obratiti pažnju da je 23 958 233 na vrhu rešetke a 5830 je sa desne strane. Proizvodi popunjavaju rešetku ili sume tih proizvoda (na dijagonali) su duž levih i donjih strana. Zatim su te sume izračunate, kao što je prikazano.
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 |
Binarno množenje
Za brojeve čija je osnova 2, dugo množenje se svodi na trivijalnu operaciju. Za svaki bit jedinicu u multiplier, pomeriti multiplicand za odgovarajući iznos, a zatim sabrati pomerene vrednosti. U zavisnosti od arhitekture procesora računara i izbora multipliera, moze biti brže kodirati ovaj algoritam koiristeći hardversko pomeranje i sabiranje bitova nego zavisiti od instrukcija za množenje, kada je multiplier fiksiran i broj sabiranja je mali.
Ovaj algoritam se naziva još i seljačko množenje, jer je bio u širokoj upotrebi među onima koji nisu bili školovani i samim tim nisu upamtili tablicu množenja koje zahteva dugo množenje. Ovaj algoritam se takođe koristio i u drevnom Egiptu.
Na papiru, zapišite u jednoj koloni brojeve koje dobijete kada više puta prepolovite multiplier, ignorišući ostatak. u koloni pored njega u više navrata udvostručiti multiplicand. Precrtati svaki red u kome je poslednja cifra prvog broja parna, i dodajte preostale brojeve u drugu kolonu kako bi se dobio rezultat.
Glavne prednosti ove metode su te da može da se nauči brzo, memorisanje nije potrebno, i može se izvesti korišćenjem tokena kao sto su čipovi za poker ako papir i olovka nisu dostupni. Međutim, ima više koraka od dugog množenja tako da može da bude nezgrapno kada su u pitanju veliki brojevi.
Primeri
Ovaj primer koristi binarno množenje da pomnoži 11 sa 3, pri čemu se dobija rezultat 33.
Decimalno: Binarno: 11 3 1011 11 5 6 101 110 2121011001 24 1 11000 —— —————— 33 100001
Eksplicitni opis koraka: 11 i 3 su napisani na vrhu. 11 je prepolovljeno na 5.5 a 3 je udvostručeno na 6. Frakcioni deo, tj. deo iza decimale se odbacuje. 5 je prepolovljeno na 2.5 a 6 je duplirano na 12. Decimalni deo se odbacuje.
Broj u levoj koloni je paran, tako da se deo u desnoj koloni odbacuje. 2 se polovi a 12 se duplira.
Sve neprecrtane vrednosti se saberu: 3+6+24=33.
Ovaj metod radi jer je množenje distributivna operacija, tako da
Komplikovaniji primer, sa korišćenjem prethodno navedenih cifara (23 958 233 i 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
Ostali algoritmi množenja
- Pomeranje i sabiranje
- Množenje "quarter square"
- Algoritam za množenje brojeva blizu celog broja
- Gausov kompleksni algoritam množenja
- Karacubin algoritam množenja
- Toom-Cook algoritam množenja
- Furijeove transformacije
Vidi još
- Binarni množenik
- Algoritam deljenja
- Logaritam
- Logaritmar
Reference
- ^ Gary Eason, Back to school for parents, BBC News, 13 February 2000
Rob Eastaway, Why parents can't do maths today Архивирано на сајту Wayback Machine (4. март 2016), BBC News, 10 September 2010
Spoljašnje veze
- "BBC - back to school for parents"
- "BBC - Why parents can't do math today" Архивирано на сајту Wayback Machine (4. март 2016)
- Novel Methods of Integer Multiplication and Division
- Quarter Tables Revisited: Earlier Tables, Division of Labor in Table Construction, and Later Implementations in Analog Computers
- Fast Fourier transformations: a tutorial review and a state of the art
- Faster integer multiplications