MATE MATI KA SLIKA 22. Sliko 20 smo raztegnili do pravega razmerja stranic slikarskega platna. [6] A. Criminisi, R. Thomas, Getting into the picture, Plus magazine, 2003: https://p1us. maths.org/content/getti ng-pi cture [7] R. Zhang, Image Rectification: Remove Projective and Affine Distortions, Homework 2, Purdue university, 2008: https://engineering. purdue.edu/kak/computervi sion/ECE661. 08/soluti on/hw2_s2.pdf [8] S. K. Badam, ECE661 Computer Vision Homework - 3, Purdue university, 2012: https://engi neeri ng.pu rdue.edu/ kak/computervi si on/ECE661_Fa112012/ soluti on/hw3_s2.pdf _ XXX Hitro množenje velikih števil vU vU vU Bo štjan Gabrov šek in Aljo ša Peperko -> Običajni uveljavljeni način množenja dveh števil temelji na množenju enic, desetič, stotic enega izmed števil z drugim številom in seštevanju teh vmesnih zmnožkov. Alternativni način množenja števil, ki ga bomo opisali v tem prispevku, naj bi bil [2] predstavljen že v približno tri tisoč let stari indijski knjigi. Temelji na naravni ideji, da najprej izračunamo število enic, desetič, stotic v zmnožku in jih nato seštejemo. Ta metoda je precej zanimiva tudi zato, ker si jo ni težko shematično zapomniti. Za začetek si poglejmo primer, kako zmnožimo števili 53 in 41. Števili podpišemo. Najprej zmnožimo enice 1 ■ 3 = 3. Nato izračunamo 5 ■ 1 + 3 ■ 4 = 17, kar nam pove, da imamo v zmnožku 17 desetič. Izračunamo še 5 ■ 4 = 20 (20 stotic), z zamikom v levo podpišemo in seštejemo dobljene vmesne zmnožke ter dobimo rezultat 2173. Shematično lahko to množenje predstavimo »preko diagonal«: 5 3 5 4 1 41 4 3 5 41 3 17 17 20 17 20 2173 www.dmfa-zaloznistvo.si www.presek.si SLIKA 1. Primer množenja dvomestnih števil 53 ■ 41 Tromestni števili 351 in 817 zmnožimo na naslednji način: 4 1 1 3 3 3 3 14 PRESEK 44 (2016/2017)1 MATEMATIKA 3 5 1 8 1 7 3 5 8 1 5 1 3 5 1 3 5 17 8-7 S 1 3 5 1 8 1 7 36 36 34 7 36 34 43 7 36 34 43 24 286767 SLIKA 2. Primer množenja tromestnih števil 351 • 817 Pri tem smo upoštevali, dajel • 7 = 7,5 • 7 + 1 • 1 = 36, 3 • 7 + 5 • 1 +1 • 8 = 34, 3 • 1 + 5 • 8 = 43 in 3 • 8 = 24. Lahko množimo tudi števila z različnim številom decimalnih mest, tako da krajšemu številu dodamo vodilne ničle. Na sliki 3 je izračunan zgled za množenje štirimestnega števila 7593 s trimestnim številom 152. Iz spodnje vrstice lahko razberemo rezultat 1154136. 7 5 9 3 0 1 5 2 7 5 9 3 0 1 5 2 7 5 9 3 0 1 5 2 7 5 9 3 0 1 5 2 7 5 9 3 0 1 5 2 7 5 9 3 0 1 5 2 7 5 9 3 0 1 5 2 7 5 9 3 0 1 5 2 6 33 58 48 40 7 0 1154136 SLIKA 3. Primer množenja 7593 • 152 Izraza lahko zmnožimo in preuredimo člene: ■ a • b = 1000 000 (a4b4) + 100 000 (a4b3 + a3b4) + 10000 (a4b2 + a3b3 + a2b4) + 1 000 (a4b1 + a3b2 + a2b3 + a1b4) + 100(a3b1 + a2b2 + a1b3) + 10 (a2b1 + a1b2) + 1 (a1b1), kar potrjuje pravilnost zgoraj opisanega postopka. Analogna ideja deluje tudi v splošnem dokazu množenja do n-mestnih števil. Formalno to zapišemo na naslednji način. Naj bo a = anan-1 • • • a2a1 = X110l-1af in b = bnb nbn-1 b2b1 = £ JI 110l-1bf. Potem je a b = I X 10i-1af ) • I £ 10i-1bi \i=1 2n 2 Vi=1 Zgoraj opisani postopek deluje za poljubno velika števila. Zaradi nazornosti dokažimo pravilnost tega postopka le za množenje štirimestnih števil. Naj bo a4a3a2a1 dečimalni zapis števila a in naj bo b4b3b2b1 decimalni zapis števila b. Števili a in b lahko tedaj zapišemo kot ■a = 1000a4 + 100a3 + 10a2 + 1a1, b = 1000b4 + 100b3 + 10b2 + 1b1. Produkt a • b je tedaj enak ■ a • b = (1000 a4 + 100 a3 + 10 a2 + 1 a1)- • (1000 b4 + 100 b3 + 10 b2 + 1 b1). = X 10i X aiabib. i=0 ia + ib = i+2 Kako pa je z daljšimi številkami, je postopek bolj učinkovit od klasičnega? Hitro ugotovimo, da moramo za zmnožek dveh n-mestnih števil v vsakem primeru opraviti n2 krajših množenj, pri tem moramo pri klasičnem množenju opraviti do n(n - 1) prenosov cifer pri seštevanju in na koncu opraviti n seštevanj do n + 1 mestnih števil. V našem primeru moramo v vmesnih korakih sešteti do n dvomestnih števil, na konču pa opraviti še 2n - 1 seštevanj v povprečju krajših števil. Na podlagi tega lahko argumentiramo, daje tudi v primeru zelo dolgih množenj postopek učinkovit, v vsakem primeru pa je nekaj dela. Literatura [1] Fast Math Tricks - How to multiply 3 digit numbers - the fast way!, https://www.youtube. com/watch?v=pG3e8kQD0Kw, ogled: 27. 1. 2016. [2] Fast Multiplication Trick 5 - Trick to Directly Multiply the Big Numbers.wmv, https://www. youtube.com/watch?v=A7EOSApApw4, ogled: 27. 1. 2016. _XXX 3 8 7 7 7 7 PRESEK 44 (2016/2017)1 15