8086-spyrnan '96

Hin árlega hrağaksturkeppni 8086 forrita




Hin árlega keppni nemenda í Stırkerfi I í ağ skrifa hrağvirk 8086 smalamálsforrit er nú ağ hefjast. Ağ şessu sinni er verkefniğ fólgiğ í şví ağ skrifa 32-bita slembitölufall sem notar ağferğina Multiply-With-Carry (MWC). Einnig á ağ skrifa ağalforrit sem kallar milljón sinnum á falliğ. Almenna formúlan fyrir MWC er hér ağ neğan:

xn = (a*xn-1 + cn-1) mod b

Í spyrnunni verğur b = 232 og a = 1675393560 (32-bita). Slembitalan xn er şví 32-bita og geymdi hlutinn (carry) cn líka. Í upphafi er gefiğ 64-bita sæğiğ (c0, x0). Şegar reiknağ er úr segğinni ağ ofan fær xn gildiğ sem hún gefur, en cn útkomuna úr

cn = (a*xn-1 + cn-1) div b

Í okkar tilfelli er gefur segğin (1675393560*xn-1 + cn-1) 64-bita útkomu. Şar sem b = 232 getum viğ sagt ağ xn fái neğri 32 bitana, en cn fái efri 32 bitana.

Í útreikningnum şurfiğ şiğ ağ margfalda 32-bita tölu (ş.e. xn-1) meğ annari 32-bita tölu (ş.e. 1675393560). Şağ er ekki hægt meğ einni skipun í 8086, svo şiğ verğiğ ağ skrifa forritsbút til ağ meğhöndla şağ. Şağ má hugsa sér nokkrar ağferğir til ağ framkvæma şá margföldun:

  1. Nota fjórar 16-bita margfaldanir, líkt şví şegar tvær tveggja stafa tugatölur eru margfaldağar saman.
  2. Nota şrjár 16-bita margfaldanir, byggt á eins konar "Strassen-ağferğ".
  3. Şar sem önnur talan er şekkt (a-iğ) şá er möguleiki ağ nota hliğrun og samlagningu.
  4. Einnig má hugsanlega nıta sér töflu viğ margföldunina.
Falliğ sem şiğ eigiğ ağ skrifa á ağ taka inn 32-bita x í DX,AX og 32-bita c í DI,SI. Skila á nıjum gildum í şessi fjögur gistu samkvæmt MWC-formúlunni. Falliğ má ekki breyta neinum öğrum gistum (nema ağ forğa şeim áğur). Ağalforritiğ ykkar á ağ kalla á falliğ 1.000.000 (ein milljón) sinnum og verğur ağ nota venjulega smalamálskall-skipun til şess (ş.e. CALL)

Til ağ prófa hvort falliğ ykkar vinnur rétt şá er hér ağ neğan tafla yfir fyrstu gildin ef c0 er 987654321 og x0 er 1234567890.

i cn xn
1 481583898 1086242913
2 423724851 3969951282
3 1548610351 8187875
4 3193950 3798636151
5 1481783237 1495764358

Reglur:

  1. Öll dırin í skóginum skulu vera vinir. Ekkert dır má éta annağ dır.
  2. Forritiğ verğur ağ finna næstu slembitölu meğ falli. Ağeins má nota 8086 skipanir í forritinu.
  3. Forritiğ má nota töflu, en verğur şá ağ fylla uppí hana sjálf. Forunnar töflur eru ekki leyfğar.
  4. Keppnisstjóri er Hjálmtır Hafsteinsson og sér hann um ağ taka tímann á forritunum, sem keyrğ verğa á 90MHz Pentium tölvum í tölvuveri VR-II.
  5. Allir nemendur í Stırikerfi I haustiğ '96 mega taka şátt í keppninni, en ağrir tölvunarfræğinemar geta einnig tekiğ şátt sem gestir, en şeir geta şó ekki sigrağ í keppninni.
  6. Sigurvegari keppninnar telst sá sem samdi forritiğ sem tekur stystan tíma og hlıtur hann (hún) verğlaun frá Opnum kerfum hf. (auk ağdáunnar íturvaxinna kvenna (karla)).


Tímamælingin fer fram í dæmatíma í Stırikerfi I föstudaginn 25. október kl. 14:00 í tölvuveri á annari hæğ VR-II. Allir sem áhuga hafa eru boğnir velkomnir.

hh@rhi.hi.is, október, 1996.