168300. lajstromszámú szabadalom • Kapcsolási elrendezés elektronikus adatfeldolgozó berendezésekhez bináris számok osztásának gyorsított elvégzésére
3 168300 4 számú többszöröseinek előállítása léptetéssel a regiszteren belül elvégezhető, addig a törtszámú szorzat előállításához külön regiszter vagy külön aritmetikai egység szükséges. A gyorsított eljárásnak különösen a sokhelyi- 5 értékű számoknál van nagy jelentősége, ahol pedig a további regiszterek vagy operátorok nagy terjedelme folytán a teljes rendszer terjedelme és költsége aránytalanul megnő. Célunk olyan módszer kialakítása volt, melynél 10 a műveleti idő csökkentése nem jár olyan nagymértékű fajlagos hardware-bővítéssel, mint az ismert megoldásoknál. A kialakított módosított eljárásnál az ismert módszerek közül felhasználjuk a „nem helyreállító módszert" (2. pont) és az osztó 15 többszörösével végzett összevont műveleteket (4. pont), de elkerüljük az ezekkel kapcsolatban említett hátrányokat. Az eljárás azon a felismerésen alapul, hogy ha választunk két egymás után következő egész számot —pl. (q— 1) és q— és az 20 osztót minden egyes részművelet előtt (kivéve esetleg egyetlen előkészítő lépést) vagy 2q-1 -el vagy 23-val megszorozzuk, akkor az osztás (az előkészítő lépéstől eltekintve) azonos módon végzett részműveletek sorozatára bontható, mely rész- 25 műveletek — mindegyike két hányadosbitet eredményez és — a részműveletek eredményeként létrejött újabb részmaradék teljesíti a következő részművelet el- 30 végzésének kiinduló feltételeit. A találmány alapjául szolgáló eljárás fix törtvesszős számok és lebegő törtvesszős számok mantisszájának osztására egyaránt alkalmas. Ismer- 35 tetésünknél pozitív operandusokat feltételezünk, de az operandusok negatív számábrázolása és előjelkezelése az eljárás lényegét nem érinti. A q kitevő értéke célszerűen megegyezik műveletenként az osztó vezető nulláinak számával, 40 mikoris az osztót 2^-szorosra normalizáljuk. Jelöljük az osztót D-vel és tekintsük a továbbiakban normalizált pozitív számnak. (A q-val végzett korrekciót, melyre a műveletvégzés előtt kerül sor, a művelet befejezése után természetesen ellenkező 45 értelemben is el kell majd végezni). Ha a q kitevőt ettől eltérő módon választjuk, szintén alkalmazhatjuk az eljárást, de a megvalósítás bonyolultabb. Már említettük, hogy a módszer helyreállítás nélküli, a részműveletek eredménye negatív is 50 lehet. A D osztó és az osztandó legmagasabb helyiértékű bitjei és a részmaradék előjele alapján végzett döntés jelöli ki a következő részműveleteket és az eredmény soron következő hányados- 55 -bitpárosát. A részmaradék előjelváltása a kijelölt művelet után jelzi, hogy az eleve kijelölt hányados-bitpáros értékét korrigálni kell. A kijelölt részművelet az alábbiak egyike lehet: 60 — a részmaradék négyszeresének képzése, — az osztó felének levonása a részmaradék négyszereséből, — az osztó értékének levonása a részmaradék négyszereséből, 65 — az osztó felének hozzáadása a részmaradék négyszereséhez, - az osztó értékének hozzáadása a részmaradék négyszereséhez. A részmaradék értékétől függetlenül (azaz a soronkövetkező nullák számától függetlenül) mindenkor 22 -vel szorozzuk a részmaradékot a következő részművelet előtt és mindig két bitet léptetünk a hányadosba. Ezt azonban úgy kell elvégezni, hogy a felszorzott részmaradékok ne nőhessenek adott korláton túl, azaz a műveletsor részeredményei ne képezzenek divergens sorozatot. A fentiekben felsorolt lehetséges részműveletek közül ezért - bizonyos kezdeti feltételek teljesülése esetén - az alábbiakban ismertetett módon lépésenként ki kell választani a megfelelő részműveletet, mellyel biztosítható, hogy a képezett részmaradékok aboszolut értékének négyszerese olyan K korlát alatt maradjon, melyen belül egy újabb, megfelelően megválasztott részművelettel ismét olyan részmaradékot kapunk, melynek négyszerese (Rj) ismét a K korlát alatt marad: IRÍK K-D (1) Kezdeti feltétel, hogy az osztandó is eleve ezen K korlát alatt legyen. Amennyiben ez a feltétel nem áll fenn, az osztó értékét le kell abból vonni, hogy így az osztandó is a korlát alá kerüljön (ez az említett előkészítő lépés). K értékére nézve belátható, hogy m j 1 K< 2 <1 — (2) i=o 4' ó ahol K a korlát elméleti értéke és m az osztandó helyiértékeinek száma. A részművelet általánosan így írható: Ri^-ÍRj^+É-D) (3) ahol É megfelelő értékét az I. táblázat szerint kiválasztva az (1) szerinti feltétel teljesül. (Az I. és II. táblázatokat az 1. ábra, a III. és IV. táblázatokat a 2. ábra tartalmazza). Az I. táblázat jelölései: Rj_i az előző részművelet felszorzott részmaradéka Rj a kijelölt részmüvelet eredménye (új részmaradék) felszorozva É az értékelési tartomány jele (értéke) H az értékelési tartomány határai. A H határok között a K értékének szerepeltetése csak formai, mert fentiek értelmében -helyes kiindulási esetén— az Rj_j abszolút értéke úgysem érheti el K értékét. A cél az, hogy az Rj/D viszony értékét az adott részműveletre valamely értékelési tartományba egyértelműen be tudjuk sorolni. Megjegyezzük, hogy amennyiben az I. táblázat szerinti elméleti határok pontosan tarthatók, tehát 2
