Množenje velikih števil

Množenje velikih števil

Preprost postopek za množenje števil (ki smo se ga učili že v osnovni šoli) dve števili med seboj zmnoži tako, da vsako števko drugega števila pomnoži s števkami prvega števila, pri tem dobi delne rezultate, ki jih podpisuje in na koncu sešteje v rezultat. Če imata števili po n števk, bo opisan postopek za izračun rezultata opravil n*n osnovnih operacij množenja števk.  Tak kvadratičen algoritem je za množenje velikih števil prepočasen, zato želimo poiskati hitrejšega.

Izziv: Napiši javansko metodo

   byte[] zmnozi(byte[] x, byte[] y)

za množenje velikih števil s časovno zahtevnostjo manjšo od n2  (kjer je n enak številu bitov večjega od števil, oziroma,  n = max(8*x.length, 8*y.length)).

Vhod: Števili x in y zapisani v binarni obliki.

Izhod: število z, za katerega velja z = x*y.

Primer: za izračun produkta 567 * 120 bo tabela x vsebovala 2 bajta (z vrednostima 2 in 55), tabela y en bajt (z vrednostjo 120), rezultat pa bo tabela s tremi bajti (1, 9, 200). Res,  saj velja:

   567 = 2 << 8 + 55

   567*120 = 68040 = 1 << 16 + 9 << 8 + 200.

 

Tehnična navodila za izdelavo algoritma:

  • Ocenjevanje vaših izdelkov bo potekalo s pomočjo sistema ALGator, zato svetujem, da sistem uporabljate tudi med razvojem vašega algoritma.
  • Za potrebe tega seminarja sem v ALGatorju izdelal projekt PROJ-BigIntegerMultiplication, ki vsebuje vse potrebne nastavitve in testne datoteke ter dva testna algoritma. Projekt prenesite na svoj računalnik in ga odpakirajte v mapo <algator_root>/data_root/projects.
  • V projektu z ukazom

 algator_admin -ca BigIntegerMultiplication s63######

 ustvarite nov algoritem. Pri tem 63###### nadomestite z vašo vpisno številko.

  • Vašo metodo za množenje števil dodajte v datoteko

algs/ALG-s63######/src/s63######Algorithm.java.

V tej datoteki popravite tudi metodo execute() in sicer tako, da bo klicala vašo metodo in vrnila rezultat. Primer "tehnično pravilne" rešitve (torej rešitve, ki sicer ne vrača pravilnega rezultata, a zadošča vsem zahtevam sistema ALGator), je prikazan v datoteki s63123456Algorithm.java.

  • Delovanje vašega algoritma v ALGatorju testirate v pomočjo testov, ki so vsebovani v projektu.  Predlagam, da najprej preverite le pravilnost delovanja algoritma in sicer tako, da poženete teste iz osnovne testne množice TestSet0. To storite z ukazom

algator_execute BigIntegerMultiplication -a s63###### -t TestSet0 -v 2

Ko bodo vsi testi pravilni (oznaka OK v izpisu), potem lahko poženete tudi teste iz drugih testnih množic. To storite z ukazom

algator_execute BigIntegerMultiplication -a s63###### -v 2

  • Rezultate izvajanja vašega algoritma lahko primerjate z rezultati izvajanja priloženih algoritmov (GradeSchool in Basic), ki sta že bila pognana, zato boste na spletni strani http://localhost:8081/ (stran odprete z ukazom algator_webpage) videli grafe, ki prikazujejo njuno učinkovitost. Za vaš algoritem pričakujem, da bo boljši od GradeSchool algoritma, saj ima ta kvadratično časovno zahtevnost. Bolj, ko se boste približali algoritmu Basic, boljšo oceno bo vaša rešitev dobila. Če bo kdo prispeval rešitev, ki bo boljša celo od algoritma Basic, bom seveda izredno navdušen, ocena za tako rešitev bo zelo visoka!
  • Še opozorilo:  obstoječa algoritma sta bila pognana na mojem računalniku, ki se po karakteristikah gotovo razlikuje od vašega, zato meritve, ki jih prikazujejo grafi, niso povsem primerljive z meritvami, ki jih boste izvedli nad svojim algoritmom. Zato priporočam, da tudi obstoječa algoritma poženete še enkrat na vašem računalniku. To storite z ukazom

algator_execute BigIntegerMultiplication -e

  • Algoritme bomo primerjali po dveh kriterijih – čas izvajanja v odvisnosti od velikosti vhoda (te podatke dobimo, ko poženemo algator_execute) ter velikost vhoda, ki ga algoritem reši v eni sekundi (kako velika števila še lahko zmnoži v eni sekundi). Podatke za drugi kriterij dobimo, če poženemo ukaz

algator_analyse FindLimit BigIntegerMultiplication -a s63###### -p N -v 2

Pozor: v svoji rešitvi ne smete uporabiti razreda BigInteger ali podobnega razreda iz kakšne druge knjižnice, ki bi vam olajšal delo (saj je v nasprotnem primeru pot do rešitve zelo preprosta)!

Rešitev izziva (torej vaš algoritem) oddate tako, da celotno vsebino mape algs/ALG-s63###### zazipate in oddate na učilnico kot eno datoteko. Vse vaše rešitve bom zbral na enem računalniku in nad njimi še enkrat pognal vse teste.  Glede na kvaliteto rešitve (to bom določil tudi na podlagi primerjave z ostalimi rešitvami) bo vaš delujoč algoritem uvrščen v enega od 4 kakovostnih razredov (super, dobro, solidno, za silo) in dobili boste od 3 do 10 točk.

Rok za oddajo rešitev je 31. 5. 2021.