Hitro množenje celih števil

Hitro množenje celih števil

Avtor: Sabina Šket

Uvod

Množenje je ena od osnovnih aritmetičnih operacij. Operator oziroma znak za množenje je pika v sredini, redkeje tudi križec.
Rezultat množenja imenujemo zmnožek ali produkt, števili a in b pa sta množenec in množitelj oziroma faktorja.

1. Različni načini množenja

Na internetu sem našla dosti načinov za hitrejše množenje števil. Predstavljeni so na naslednjih straneh (v filmčkih).

1.1. Film: različni triki

1.1.1. Množenje s 5


Nazaj

1.1.2. Množenje s 15


Nazaj

1.1.3. Množenje s 19


Nazaj

1.1.4. Množenje s 99


Nazaj

1.1.5. 'Mix metod'


Nazaj

1.2. Film: množenje števila 9 s pomočjo dlani

1.3. Film: dvomestna števila

1.4. Film: večmestna števila

1.5. Film: kvadriranje 'na roke'

1.6. Film: kubiranje 'na roke'

1.7. Egipčansko množenje

Prve visoke civilizacije so nastale približno leta 3500 pr. n. št. ob Nilu, Evfratu, Tigrisu in drugih velikih rekah. Njihov nastanek štejemo za prelomni trenutek, ki je ločil prazgodovino od starega veka.

Ker so ljudje morali zaradi vsakoletnih poplav polja na novo meriti in določati meje, da bi preprečili mejne spore, ali pa ker so morali izdelati načrt za gradnjo svetišča ali palače, se je začela razvijati matematika. Uvedli so posebne pismenke za števila. V Mezopotamiji so razvili šestdesetiški sistem, v Egiptu pa desetiškega. Znali so seštevati, odštevati, množiti in deliti. Sestavili so tablice za množenje in deljenje. Znali so računati z ulomki.

Postopek množenja
Množili so tako, da so drugi faktor zapisali kot vsoto potenc števila 2. Nato so z zaporednim podvojevanjem drugih faktorjev dobili zmnožke teh potenc z drugim faktorjem. Na koncu so sešteli ustrezne delne zmnožke.

1.7.1. Film_ egipčansko množenje

1.8. Nikhilamova metoda

2. Različni algoritmi v python-u za hitro množenje

Ideje algoritmov, ki so predstavljeni na naslednjih straneh:
Rekurzivne funkcije so iz računalniškega stališča precej potratne, ker vsakič, ko se izvede klic funkcije, se na računalniški sklad odloži trenutno stanje (torej vrednostih v registrih - spremenljivk, ki so trenutno v uporabi) in se jih takoj ob vrnitvi iz funkcije, naloži v registre - skratka precejšne delo je že samo zaradi shranjevanja trenutnega stanja ob klicu funkcije, tako, da če se le da, se rekurzijo pretvori v iterativno obliko. Recimo algoritem 'množenje2' je iterativna različica algoritma množenja1, in je prostorsko precej boljša kot rekurzivna verzija, saj tudi znotraj 'while zanke' ni nobenih klicov kakršnih koli funkcij, so samo množenja in seštevanja.

1. matematična razlaga ideje algoritma: Navadno eksponentno računanje traja XY ciklov in linearno narašča z velikostjo števil. Predstavljeni algoritmi linearno kompleksnost zmanjšajo, saj preskočijo npr. polovico ciklov, ker vedno delijo z 2.

2. računalniška razlaga ideje algoritma: računalniki hitreje računajo pri množenju ali deljenju z 2 kot katero drugo številko, ker lahko uporabljajo 'logical shift left' (<<) ali 'logical shift right' (>>), ki sta v 'assembly kodi' modernih procesorjev hitrejša ukaza od ukaza 'mul' (množenje).

potenciranje
Princip delovanja: 'algoritem računa' iz najmanj pomembnega bita, proti najbolj pomembnemu tako, da najprej prišteva 10, potem 100, potem 1000, itd.
primer; a=11, b=17

11*potenciranje(11,16)
   p=potenciranje(11,8)
      p=potenciranje(11,4)
         p=potenciranje(11,2)
            p=potenciranje(11,1)
               p=potenciranje(11,0)
               vračanje iz globine: 1
            vračanje iz globine: 11
         vračanje iz globine: 121
      vračanje iz globine: 14641
   vračanje iz globine: 214358881
vračanje iz globine: 505447028499293771
Rezultat: potenciranje(11,17)=505447028499293771

Razlaga; pri tem algoritmo želimo doseči to, da, če že ni produkta(v našem primeru spremenljivka b) sodo število, da ga lahko delimo s številom 2, kjer problem razpolovimo.

množenje1
, kjer je je to deljenje z 2 ter premik v desno za eno mesto. primer: a=11 b=17

množenje1(11,17)
    množenje1(11,8)
        množenje1(11,4)
            množenje1(11,2)
                množenje1(11,1)
                    množenje1(11,0)
                    vračanje iz globine: 0
                vračanje iz globine: 11
            vračanje iz globine: 22
        vračanje iz globine: 44
    vračanje iz globine: 88
vračanje iz globine: 187
Rezultat: množenje1(a, b)=187

Ideja algoritma je ta, da en produkt (b) 'navzdol' delimo z 2 (2^3, 2^2, 2^1, 2^1, 2^0), potem se program ustavi in vrne rezultat.

množenje2
, je to deljenje z 2 ter premik v desno za eno mesto.
deluje podobno kot množenje1.
primer: a=11, b=17

    x:11,y:17,p:0
    p:11,x:22 y:8
    x:44 y:4
    x:88 y:2
    x:176 y:1
    rezultat: 187
Rezultat: a=11 b=17 množenje1(a, b)=187

Algoritem si najprej zabeleži ostanek p:11, b deli z 2 in dobi 8 (ostanke ignorira). A pomnoži z 2 in dobi 22 ter nadaljuje: y=8/2 = 4, x=22*2 = 44, itd... na koncu pa samo sešteje končni x + ostanek od začetka.
Ideja algoritma; algoritem poskuša čimprej priti do potence števila 2 (2^0,2^1,2^2, 2^3,...) in 'delat' s temi, ostanek pa na koncu prišteti.

2.1. Film: python; potenciranje

2.2. Film: python; algoritem1

2.3. Film: python; algoritem2

2.4. Časovna zahtevnost algoritmov v python-u

Potenciranje
Ugotavljanje časovne zahtevnosti tega algoritma je malo zahtevnejše, kot pri naslednjih dveh algoritmih.
Če na hitro pogledamo, koliko korakov je potrebnih za izvedbo tega algoritma, ugotovimo, da v minimalnem času je časovna zahtevnost zaradi 'if stavka' (velja samo v primeru, če je b = 1), v pričakovanem času , zaradi 'b/2' ter v maksimalnem času, pa je , zaradi 'b-1'.
Iz tega bi sklepali, da je časovna zahtevnost , ker je to v najslabšem primeru, vendar to bi bilo zelo nenatančno zaradi tiste 'b/2' optimizacije. Zato v takšnih primerih pogledamo celoten algoritem, kako se obnaša (ne samo posamezne dele). Dobimo, da je kompleksnost , ker zanemarimo, da moramo na vsake toliko korakov za eno zmanjšat preden lahko razpolovimo.

Množenje 1
Časovna zahtevnost je , ker na vsakem koraku 'problem' razpolovimo.

Množenje 2
Pri tem algoritmu, pa zanemarimo dejstvo, da se izvede enkrat manj (konča se pri y = 1 in ne y = 0). Torej, potrebnih korakov je n-1, vendar ko izraz poenostavimo, postane n. Torej časovna zahtevnost tega algoritma je tudi .

algoritem2 je počasnejši od algoritma1. Pri prvem algoritmu, kjer je rekurzija, se na vsakem koraku množitelj deli na pol in pri tem se časovna zahtevnost zmanjša.

3. Wikipedija: Multiplication algorithm

Na spletni strani: //en.wikipedia.org/wiki/Multiplication_algorithm
so opisani različni načini za hitrejše množenje števil.

3.1. Metoda mreža

Ta metoda se predvsem uporablja v osnovnih šolah (Anglija). Uporabno je predvsem za števila, ki so večja od deset.
Primer uporabe Izračunaj koliko je 45x12 s pomočjo mreže

(http://www2.nauk.si/files/533/mreza1_0.png)

Ko zapolnimo tabelo, dobljene vrednosti med sabo seštejemo in dobimo rezultat.

(http://www2.nauk.si/files/533/mreza2.png)

Ta metoda je učinkovitejša od tradicionalne oz. klasične. Je bolj zanesljiva. Zato je verjetnost, da bi prišlo med samim postopkom do napak, manjša.

3.2. Standardni algoritem

Standardni algoritem oziroma 'dolgo množenje' je običajen algoritem za množenje večjih števil. Produkt števil se dobi tako, da eno od števil razdelimo na enice, desetice, stotice, itd. Ta števila posamezno pomnožimo z drugim množiteljem. Je običajni algoritem za množenje večjih števil z osnovo 10.

Primer:
Pomnoži števili 2345131 in 1210.

(http://www2.nauk.si/files/533/standard_0.png)

prostorska zahtevnost glede na 'bite' je .

Psevdo koda

(http://www2.nauk.si/files/533/dolgo_mn1.png)

Elektronska uporaba
Da pomnožimo dve n-mestni števili po tej metodi, potrebujemo prebližno operacij, torej časovna zahtevnost je .

3.3. Množenje z rešetko

Rešetke oziroma sito je algoritem, ki je ekvivalentno standardnemu algoritmu.

Postopek

  • mrežo zapolnimo tako, da desetice zapišemo v zgornji levi kot, enice pa v spodnji desni kot.
  • ko zapolnimo mrežo, seštevamo po diagonalah od desne proti levi in upoštevamo prenose.

Primer
S pomočjo opisanega postopka izračunajte produkt števil 234 in 13.

(http://www2.nauk.si/files/533/resetke1.png)


(http://www2.nauk.si/files/533/resetke2.png)


Torej; 234x13=3042

3.4. Binarno oz. dvojiško množenje

Dvojiški zapis je predstavitev kombinacije stanj v digitalnih računalnikih z vrednostmi 0 in 1. Vrednost 0 običajno ustreza stanju izključeno, vrednost 1 pa stanju vključeno.

Algoritem se imenuje tudi kmečko množenje, saj so ga uporabljali tisti, ki niso bili šolani oziroma so imeli slabši spomin. Algoritem so uporabljali tudi v starem Egiptu. V bistvu je algoritem enak klasični metodi, z razliko v tem, da se števila pretvorijo v binarni zapis.

(http://www2.nauk.si/files/533/bin1.png)

primer: Množenje števil 26 in 2:

(http://www2.nauk.si/files/533/dvojisko2_0.png)

1. število potence 2, ki je največje oziroma enako 26 je 16,
2. 26-16=10,
3. število potence 2, ki je največje oziroma enako 10 je 8,
4. 10-8=2,
5. število potence 2, ki je največje oziroma enako 2 je 2,
6. 2-2=0
Do zapisa števila 26, iz desetiškega v dvojiški sistem, lahko pridemo tudi po naslednjem postopku:

(http://www2.nauk.si/files/533/dvojisko_0.png)


torej 26=16+8+2. Zapis iz dvojiškega v desetiški sistem (se pa zapisuje od zadaj naprej):

Rešitev:





Prednost
Glavna prednost tega postopka je v tem, da se uporablja le seštevanje, odštevanje ter množenje z dva. Vendar se potrebuje veliko več korakov kot pri dolgem mmnoženju, zato je priporočljivo, da se ta algoritem uporablja na manjših podatkih.

3.5. Shift and add

Shift and add je 'postopek' za logični premik bitov v levo oziroma v desno s prištevanjem. V računalništvu je enostaven premik logičnih bitov enostavnejši, kot dejansko množenje oziroma deljenje.
V zgodovini, so računalniki uporabljali omenjeni algoritem za množenje manjših števil.

Primer:
Imamo binarno (dvojiško) število in vse bite premaknemo v desno, to dejansko pomeni, da delimo z 2, če pa vse bite premaknemo v levo za eno mesto, pa predstavlja množenje z 2.

Recimo, da premaknemo vse bite v levo za 3 mesta, to bi v bistvu pomenilo množenje z - kjer m predstavlja število premikov mest: m=3, torej množimo z 8.

binarno   desetisko
0001           1

premaknemo za 3 mesta v levo: 1 << 3
binarno   desetisko
1000           8

Množenje in deljenje s konstanto se izvede z zaporedjimi premiki v levo oziroma v desno, ter s prištevanjem.
Recimo, da želimo pomnožiti z 10 neko število x potlej je to recimo isto, kot bi želeli izvesti operacijo
x*10 = (x*8)+(x*2) = (x << 3) + (x << 1).
Izračunamo lahko tudi na drugačen način npr:
x*10=(x*5)*2 = (x*4+x)*2 = (x << 2 + x) << 1,
kjer premik x << 2 predstavlja množenje z 2^2=4, celoten oklepaj pa pomnožimo z << 1 --- kar predstavlja množenje z 2^1 = 2.

Množenje s praštevilom 17:
x * 17 = 1 * x + 16 * x = x + (x << 4)
recimo 5 * 17= 5 + (5 << 4) = 5 + 80 = 85
(5 << 4) - v binarni 'obliki' pomeni, da število 5 premaknemo za 4 mesta v levo.

3.6. Četrtina kvadratnega množenja

Imamo enačbo v kateri sta definirana dva ulomka. V števcu obeh ulomkov je definiran kvadrat poljubnega števila (izraza), v imenovalcu pa je definirano število 4. Ta dva ulomka je možno razstaviti tako, da izpostavimo .

Spodaj je definirana 'lookup' tabela (tabela za vpogled), s števili od 0 do 18, s katero si pomagamo za množenje števil do
9 x 9. Do podatkov v 'spodnji' vrstici tabele smo prišli tako, da smo števila n vstavili v formulo , ter dobljeni rezultat navzdol zaokrožili.

(http://www2.nauk.si/files/533/3-6.png)


Primer:
Želimo pomnožiti 7 in 5. Vsota števil je 12, razlika števil pa 2. Sedaj pa pogledamo v tabeli v zgornjo vrstico, kje se nahajata dobljeni števili. 'Pod' 12 je število 36 ter 'pod' 2 pa število 1. Razlika dobljenih števil, pa predstavlja produkt prvotnih števil. Torej 36-1=35, iz tega sledi 35=7*5.

3.7. Starodaven indijski algoritem za množenje števil blizu 'okrogle' številke

Ideja algoritma je v tem, da si izmislimo eno okroglo število v bližini števil, katerih bomo množili (najlažje: 10,100...), da bo množenje kasneje čimlažje.

Primer:
Predpostavimo, da želimo pomnožiti števili in , ki sta 'blizu' okroglega števila . Zapiše se:
in .
Produkt števil se izrazi s formulo:
, kjer sta x in y
in

Recimo, da želimo pomnožiti 5*17.
x=5, y=17, N=20 (lahko je poljubno, glavno, da je za x in y ista vsota)
x =N+x' => 5=20+x' => x'=-20+5 => x'=-15
y=N+y' => 17=20+y' => y'=-20+17 => y'= -3
Sedaj pa vrednosti vstavimo v formulo in dobimo:
5*17 = 20*(5+(-3))+(-15)*(-3) = 20*(2)+45 = 40+45 = 85

Do enakega rezultata bi prišli, če bi za število N 'vzeli' kakšno vmesno število, med 5 in 17, recimo N=12:
x = x' + N --> x' = x-N = 5-12 = -7
y = y' + N --> y' = y-N = 17-12 = 5
x*y = N*(x+y')+x'*y'
5*17 = 12 * (5+5)+(-7)*5 = 12*10 + (-35) = 120 - 35 = 85

3.8. Algoritmi za hitro množenje celih števil

Najpomembnejši algoritmi oziroma metode za 'hitro' množenje so;

  • Gaussova metoda
  • Karatsubovo množenje
  • Toom-Cook-ov algoritem
  • Fourierjeva transformacijska metoda
  • Linearno časovno množenje

3.8.1. Gausova kompleksna metoda

Kompleksno množenje običajno vključuje štiri množenja in dvoje seštevanj.

(http://www2.nauk.si/files/533/kompleksno_množenje.png)

Leta 1805 je Gauss odkril način za zmanjšanje število množenj na 3.

(http://www2.nauk.si/files/533/gauss_0.png)


Produkt (a+bi)(c+di) se lahko izračuna na naslednji način:




realni del =
imaginarni del =

Gaussov algoritem porabi le tri množenja in pet seštevanj, kar je dosti bolje od štirih množenj in pet seštevanj ali odštevanj. Množenje je 'dražje' od treh operacijah seštevanj oziroma odštevanj.

primer
(2 - 3i)(1 + 5i)
1. metodi:
(2-3i)(1+5i)=2*1 + 2*5i - 3i*1 - 3i*5i. Torej imamo štiri množenja.
Dobimo 2 + 10i - 3i + 15 = 17 + 17i.
2. metoda:
k1 = 1 * (2 - 3) = -1, k2 = 2 * (5 - 1) = 8, k3 = -3 * (1 + 5) = -18
realni del = k1 - k3 = -1 - (-18) = 17
imaginarni del = k1 + k2 = -1 + 8 = 7

3.8.2. Karatsubin algoritem

Karatsubin algoritem je algoritem za hitro množenje. Tipa algoritma je, deli in vladaj.
Izumil ga je Anatolii Alexeevitch Kaaratsuba leta 1960 in objavil leta 1962.

recimo, da želimo pomnožiti števili x in y.
1. izberemo tak m, da lahko zapišemo števili x in y kot
in
.
Ponavadi delamo v desetiškem sistemu (računalniki recimo v dvojiškem), zato vzamemo B=10, m pa izberemo tako, da sta in manjša od B^m=10^m.

2. izračunamo:





3. rezultat je:
, če vzameš za B=10.

Primer
Zmnožek števil x=11.486 in y=7.182 po definiranem postopku:
1. B=10, m=3 =>
11.486 = 1000 * 11 + 486, kjer je ter
7.182 = 1000 * 7 + 182, kjer je ter
2. a = 11*7 = 77
b = 486*182 = 88.452
c = (11+486)*(7+182) = 497*198 = 93.933
k = 93.933 - 77 - 88.452 = 5.404
3. rezultat je:




Zakaj je algoritem dober (učinkovit)?
Načeloma rabimo za množenje dveh števil (ki jih razdelimo na dva dela tako kot zgoraj) 4 množenja:
, s tem algoritmom pa množimo samo 3 krat. Ko računamo a, b in c.

Psevdo koda:

(http://www2.nauk.si/files/533/KA_koda_0.png)

Časovna zahtevnost
Časovna zahtevnost je torej je metoda hitrejša od 'dolgega množenja'.

3.8.3. Toom-Cook algoritem

Algoritem je namenjen množenju velikih števil. Števili, ki ju množimo najprej razdelimo na k delov dolžine največ l in nato množimo po delih. Recimo, da hočemo zmnožiti števili m in n.

Postopek je naslednji:
1. delitev
Najprej določimo bazo tako, da lahko m in n razcepimo na največ k delov. Ustrezen l izberemo velikokrat kar s formulo
.
Tako razcepimo število m na števila in število n na števila , kjer so vsa ta števila največ dolžine l.

Primer:
naj bo m=12342131 in n=541292928. Izberemo k=3 in po zgornji formuli izračunamo, da je l=3. Tako dobimo in ter , , . Opomba: velikokrat se zgodi, da ne moremo določiti samo enega ustreznega k, da lahko naredimo delitev (da bi zadostili zahtevi, da so vsi deli dolžine največ l). Zato moramo izbrati za vsako od števil m in n svoj k. Zato bomo od tukaj naprej predpostavili, da imamo za vsako od števil m in n svoj k. Ta dva k-ja bomo označili s km (za število m) in kn (za število n).
Z dobljenih števil tvorimo polinoma
in
, za katera velja
in .
Cilj: radi bi izračunali vrednost r(B), kjer je polinom r definiran kot r(x)=p(x)*q(x). Polinom r je torej oblike , kjer smo označili .

2. evaluacija
Vemo: vsak polinom stopnje d je natanko določen z vrednostmi v d+1 točkah.
Primer: premica (ki je polinom stopnje 1, je recimo natanko določena z dvema točkama).
V točki 1. iskani polinom r(x) bomo določili tako, da bomo poiskali njegove vrednosti v d = km+kn-1 točkah.
Najprej izberemo d 'čim lepših' točk, t.j. takih točk, da znamo dokaj enostavno izračunati vrednosti polinomov p(x) in q(x) v njih. Označimo te točke z .
Izračunamo vrednosti:
in
.

3. točkovno množenje
Izračunamo vrednosti:
. Tu izvedemo posamezno množenje s kakšnim drugim algoritmom, ki je primeren za množenje manjših števil.

4. Interpolacija
Koeficiente iskanega polinoma r(x) določimo tako, da rešimo sistem
, kjer b predstavlja stolpec z vrednostmi
, A je matrika

in x iskani vektor, katerega vrednosti, ki jih bomo izračunali, bodo ravno iskani koeficienti .
Sistem rešimo tako, da izračunamo inverz matrike A in izračunamo .
Sedaj, ko imamo znan polinom , je iskani rezultat, torej zmnožek števil m in n, enak vrednosti polinoma r v točki B.


Časovna zahtevnost:
Splošna časovna zahtevnost je;

3.8.4. Fourierjeva transformacija metode

1. Podobno kot pri Toom-Cook-ovim algoritmom predstavimo števili a in b, ki bi ju radi zmnožili, s polinomoma
in
, kjer je n čimvečja potenca števila dva.

Opomba: radi bi izračunali produkt r(x)=p(x)*q(x), kjer je polinom stopnje 2n. Želimo, da ima naš algoritem za množenje časovno zahtevnost . Za določitev polinoma r(x) moramo poznati njegove vrednosti v 2n+1 točkah. Za izračun vrednosti v teh 2n+1 točkah rabimo načeloma časa, s pomočjo Fourierove transformacije, pa bomo to pohitrili.

2. za vektorja in izračunamo fourierovo transformacijo kot pravi algoritem na strani:
//www.cs.rug.nl/~ando/pdfs/Ando_Emerencia_multiplying_huge_integers_using_fourier_transforms_presentation.pdf

(http://www2.nauk.si/files/533/FFT.png)


Bistvo je v tem, da je algoritem rekurziven (zato teče v času O(n*logn)) in izkorišča dejstvo, da če imamo neki koren števila 1, torej nek w, tak, da je , so potem števila različna. Prav tako so različna tudi števila , in velja enakost

za sode n (zato smo na začetku definirali, da je n potenca števila 2).

3. Če je fourierova transformacija in fourierova transformacija B, izračunamo vektor
.

4. Izračunamo inverzno fourierovo transformacijo

za vektor M. Rezultat a*b je potem vrednost polinoma r(x) v točki 10, torej .

Časovna zaktevnost algoritma je

3.8.5 Linearni časovno množenje

Uvod
Ponavadi imamo za dan problem več algoritmov. Imeti moramo kriterije za izbiro najboljšega. Ponavadi sta to prostorska in časovna zahtevnost. Ti povesta koliko sredstev potrebujemo za rešitev problema.
Pri prostorski zahtevnosti nas zanima koliko dodatnega prostora porabi algoritem za delovanje (poleg tistega, ki ga že zasedejo podatki).
Pri časnovni zahtevnosti merimo čase izvajanja algoritmov. Ker so različni računalniki različno hitri, ne napišemo konkretnega časa izvajanja, ampak zapišemo splošno formula naraščanja časa z velikostjo podatkov. Ponavadi se časovna zahtevnost zelo spreminja če so podatki:

  • Idealni – izvedba v minimalnem času
  • Normalni – izvedba v pričakovanem času
  • Zlobni – izvedba v maksimalnem času

Merjenje časa ne pove dosti o algoritmu, saj je porabljen čas odvisen od računalnika, jezika in prevajalnika. Zato opravimo analizo časovne zahtevnosti s štetjem karakterističnih operacij. Ta je sicer težja od meritev, a so podatki univerzalni. Ponavadi z analizo ugotovimo kritične dele algoritma in dobimo idejo za izbolšavo. Pogosto časovne zahtevnosti ne zapišemo v najbolj natančni obliki; npr. . Ko n povečujemo se funkcija približa funkciji . Zato uporabimo O notacijo in rečemo, da je algoritem reda . O notacija pove družino funkcij naraščanja
časa / prostora.

Osnovne časovne zahtevnosti:
Najbolj ugodne časovne kompleksnosti so npr. O(1)

  • - konstantni čas - pomeni, recimo da samo pogledamo v seznam.
  • - pomeni, da se moramo npr. sprehoditi čez celoten seznam in nekaj naredit z vsako vrednostjo.
  • - je recimo iskanje po binarnem drevesu (logaritem je z osnovo 2, kjer se na vsakem koraku odločimo ali gremo v levo ali v desno)
  • - če iščemo element v seznamu seznamov, kjer je v seznamu n podseznamov s po m elementi
  • - so eksponentni časi - zelo počasni algoritmi (zelo hitro naraščajo)

Skratka želimo, da je časovno kompleksnost čimboljša:
Na strani //en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities je po stolpcu 'Running time' urejene, od najhitrejše do najpočasnejše, časovne zahtevnosti.

Množenje v linearnem času pomeni, da bolj kot je kompleksno množenje, bolj bomo za rezultat čakali linearno glede na kompleksnost množenja.
Na grafu bi to izgledalo tako, da imamo na abscisi (x osi) recimo čas potreben za izvedbo množenja, na ordinati (y osi) pa koliko operacij potrebujemo za množenje. Na grafu bi bila linearna premica.

3.8.5.1. nadaljevanje

Knuth je opisal računski model, kjer sta dve n-bitni števili lahko zmnoženi v linearnem času.
Predpogoj za to je, da je lahko katerakoli celica pomnilnika (RAM-a) dostopna v konstantnem času.
To se izvede z FFT-jem, opisanim v enih od prejšnjih prosojnicah.

Časovna kompleksnost je , kjer M predstavlja potreben čas za množenje dveh log n - bitnih števil.
Če v naprej pripravimo 'look-up' tabelo (tabela, kjer si sproti shranjujemo rezultate, da nam ni potrebno ponovno računat) in jo napolnimo z izračunanimi vrednostmi do bitni, potlej M predstavlja čas vpogleda v to tabelo. Iz tega sledi, da časovna zahtevnost pade na konstantni čas.
Torej, če imamo to tabelo potlej 'pade' algoritem na linearno časovno zahtevnost za množenje števil.

4. Kviz

1. Kateri izmed naštetih algoritmov je algoritem za hitro množenje velikih števil?

Preveri

2. Kolikšna je časovna zahtevnost klasičnega algoritma?

Preveri

3. Ali je Karatsuba algoritem tipa Deli in vladaj?

Preveri

Pravilno

Odgovor je pravilen. Naprej

Narobe

Odgovor ni pravilen. Ponovno

Pravilno

Odgovor je pravilen. Naprej

Narobe

Odgovor ni pravilen. Ponovno

Pravilno

Odgovor je pravilen. Naprej

Narobe

Odgovor ni pravilen. Ponovno

5. Viri

0%
0%