[go: up one dir, main page]

DE2058612A1 - Verfahren und Schaltung zur Bildung eine Reziprowertes - Google Patents

Verfahren und Schaltung zur Bildung eine Reziprowertes

Info

Publication number
DE2058612A1
DE2058612A1 DE19702058612 DE2058612A DE2058612A1 DE 2058612 A1 DE2058612 A1 DE 2058612A1 DE 19702058612 DE19702058612 DE 19702058612 DE 2058612 A DE2058612 A DE 2058612A DE 2058612 A1 DE2058612 A1 DE 2058612A1
Authority
DE
Germany
Prior art keywords
bits
reciprocal
register
accuracy
mantissa
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
DE19702058612
Other languages
English (en)
Inventor
Huei Ling
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of DE2058612A1 publication Critical patent/DE2058612A1/de
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/52—Multiplying; Dividing
    • G06F7/535—Dividing only

Landscapes

  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Complex Calculations (AREA)
  • Document Processing Apparatus (AREA)

Description

International Business Machines Corporation, Armonk, u.y. 10 504
Verfahren und Schaltung zur Bildung eines Keziprokwertes
Die Erfindung betrifft ein Verfahren zur Gewinnung des Reziproken einer Zahl D und eine Schaltung zur Ausübung dieses Verfahrens.
Aufgabe der Erfindung ist es« ein verfahren und eine Schaltung so auszugestalten, daß schnelle Arbeitsweise bei möglichst geringem Aufwand an Maschinenausriistung möglich ist.
Das erfinderische Verfahren ist gekennzeichnet durch die Verfahrensschritte :
(1) Gewinnen der nach links justierten Mantisse von D1 mit dem Wert d^;
(2) mathematisches Ausrichten der justierten Mantisse um eine Standardform der Zahl zu gewinnen, die eine vorbestimmte Anzahl von fuhrenden Bins-Bits enthält;
109826/1517
BAD ORIGINAL
- 2 - P 15 930 ·
(3) gewinnen einer Genauigkeitssteuerzahl;
(4) gewinnen eines Näherungswertes des Reziproken der nach links justierten Mantisse d^
(5) multiplizieren des Näherungswertes mit der Genauigkeitssteuerzahl um die Bits des Reziprokwertes mit der gewünschten. Genauigkeit zu gewinnen; und
(6 ) verschieben der Bits des Reziprokwertes um die tatsächliche Linksausrichtung der Mantisse,
Die erfinderische Schaltung ist dadurch gekennzeichnet* daß ^ vorgesehen sind,
ein Tabellenleser zur Überprüfung der Bits der Mantisse dm der Zahl D und Lieferung einer Information für die erforderliche mathematische Rechnung» um die Mantisse in eine Standardform mit einer vorbestimmten Zahl von führenden Eins-Bits umzuwandeln;
ein Addiererblock (400), der über Verschiebe- und Additionsregister (300), die auf Grund des Ausgangs des Tabellenlesers bestimmte mathematische Rechnung definieren an den Tabellenleser (200) ausgangsseitig angeschlossen ist.
eine Genauigkeitssteuereinheit, die ausgangsseitig an den Addier erb locic angeschlossen ist und eine Genauigkeitssteuer— ' zahl als Punktion atr vorbestimmten Zahl der Genauigkeitsbits liefert?
eins Arithmetische Rückschaltstufe zur Ermittlung eines Annäherungswertes des gewünschten Reziprokwertes mit einer niedrigeren als der gewünschten Genauigkeit; und
ein Multiplizierer der an die Genauigkeitssteuereinheit und an die Rückschaltstufe angeschlossen ist und den genannten Annäherungswert mit der Genauigkeitssteuerzahl multipliziert um die Bits des gesuchten Reziprokwertes mit der gewünschten Genauigkeit zu ermitteln.
Die Erfindung wird nun anhand der beigefügten Zeichnung näher erläutert*
10 9 8 2 6/1517 BAD original
- 3 - P 15 930
In der Zeichnung zeigt:
Figur 1 ein Ausführungsbeispiel nach der Erfindung im
Blockschaltbild und
Figuren 2-4 jeweils besondere Details aus Figur 1 ausführlicher·
Zunächst wird zur Erleichterung des Verständnisses eine der Erfindung zugrunde liegende Theorie abgehandelt. Bei dem in den Figuren dargestellten AusfUhrungsbeispiel werden Dividend und Divisor normalisiert» und das bedeutet, daß das binäre Komma immer vor die binäre Eins höchster Ordnung gesetzt wird· Die nachfolgende Beschreibung stützt sich auf die Behandlung binärer Zahlen, die Erfindung ist aber darauf nicht beschränkt, sie ist auch in anderen Zahlensystemen anwendbar.
Im folgenden wird mit N der Zähler, mit D der Nenner und mit Q der Quotient bezeichnet. Es sei darauf hingewiesen, daß bei einer entsprechenden Skala die Zahlen N und D ganze Zahlen oder solche mit Gleitkomma sein können. Es gilt
M(J)
Da J eine unendliche Anzahl von Stellen enthalten kann, ist es nötig, die gültigen Stellen entsprechend der der Rechnung zugrunde gelegten Genauigkeit zusammenzufassen. Es gilt zum Beispiel Rs^ (i~2"*"n) wobei R das ungefähre Reziproke von D ist und η die Anzahl der gültigen Stellen ist.
Man kann durch die Handhabung von Blocks das Reziproke des Nenners errechnen. Es sei
(2), wobei d die Mantisse von D ist.
6/1517
und £ (d) ~ § (1 * d).
P 15 930 System)
Wir können d umschreiben
wobei mit d,g\ « (0, Spg„S- ··· ^n)* die Gleichung (2) umge schrieben werden kann ^u
0,75 (1 + d(2) - 0,5 f(ä(2)) (4).
Dividiert man beide Seiten der Gleichung (4) durch 1 + d(g)* 0 gibt si
(2)
Es wird gesetzt?
2S 5 3 (2S ) - 2f(2S ) (5.1)
2 1 1
2S s 3 (2S ) - 2f(2S ) (5.2)
3 2 2
2S = 3(2S ) - 2f(2S ) (5,3)
4 3 3
usw·
Dividiert man in Gleichung (5·ΐ) die beiden Seiten durch 1 * d
ergibt sich '
2S 3(2S ) f(2S )
2 = 1 - 2 1
1+d' 1+d 1+d
(2) (2) (2)
2S 23
0?) (2) 1
109826/1517
BAD ORIGINAL
- 5 - P 15 930
Setzt man Gleichung (4a) in Gleichung (6·1) ein, ergibt sich
2S
2 β
1* (2)
Dividiert man in Gleichung (5·2) beide Seiten durch 1 + d , ergibt sich ■ \ J
2S 2S
~~gi * Γ~ 2S · (6.2)
(2) (2) 2
Setzt man Gleichung (4a) in Gleichung (6.2) ein, ergibt sich
2S
TfcT (2)
- \ d ) S · 2 (2S S ♦) (6.2a)
und allgemein
2S 2S
ptl— β j~£
(2) (2)
i7a~- -W8=1 2(s >· (6·2η)
Aus Gleichung (6) erkennt man, daß» wenn die Standardfara des Kenners» das ist 1+d * acht führende binäre Binsen hat» dann
hat 2S sicher 16 führende Binsen. Da S 8 · 2P führende Einsen 1 P
hat, sofern die Genauigkeit den Grad η hat, ergibt sich η - 16P. Wenn ein einsiger 32-Bit-Quotient erforderlich ist» dann wird S
ausgewählt· Da 16-Bit-Haschinen und 32-Bit-Maschinen handelsüblich
sind» reicht S im allgemeinen aus· Man kann S und S umschreiben 1 1 2
109826/1517 ft.n„
SAD ORIGINAL
- β - P 15 930
— e i-i d, x (7)·
Ud 4 4 (2)
(2)
Diese Gleichung definiert die Annäherung erster Ordnung für cas Reziproke des normalisierten Anteils der 16-Bit-Genauigkeit. Bs gilt
(2)
Die oben genannte Gleichung definiert die Annäherung zweite:' Grades des Reziproken des normalisierten Anteils einer 32-Bi•L.Genauigkeit·
Bei größeren Maschinen ist manchmal-eine doppelte 64-Bit-Genau:iUj· keit erforderlich» und in diesem Fall kann man die Gleichung (β.''.: umschreiben zu
2S* / 3 . 1 d ) S · 2 2S S · ' (9)♦ . e I 2 *" ST 2 1 11
T+d
(2)
Diese Gleichung definiert die Annäherung dritter Ordnung des Reziproken des normalisierten Anteils einer 64-Bit-Genauigke: t» Die Gleichung (6·η) für vielfache Genauigkeit wird allgemein angewendet ·
Der normalisierte Nenner hat schließlich eine einzige führefuie Eins. Wenn wir ihn verwenden um S aufzufinden, dann kann 2S
1 1
in binärer Schreibweise von mindestens zwei führenden Einseu an eine beliebige Anzahl von führenden Binsen haben«
109826/1517 BADOR1QiNAL
- 7 - P 15 930
Die Genauigkeit von » ' ' ■ wird unvorhersagbar· Damit man
Ί*α (2)
eine Minimalzahl von erforderlichen Einsen innerhalb einer begrenzten Zeit in 2S. erhält« benötigt man mehr führende Einsen in 1 + df2) (zu*1 Beispiel 1,1111111000·..)· Der Grund dafür» daß 8 führende Einsen ausgewählt sind» liegt darin» daß man mit wenigen suchenden Tabellen auskommt. Die Tabelle enthält nur 256 Eingänge, und jeder Eingang liefert eine Anzeige über die Anzahl der erforderlichen Vorverschiebungen und Additionen· Die Operation wird beendet» indem vorausgeschaut wird, ehe 1 + d/g\ die Ausführungseinheit erreicht· Man kann aeigen, daß im ungünstigsten Fall nicht mehr als 5 Additionen mit festem Komma nötig sind (Durchschnitt 2,9 Additionen)· Der zweite Grund dafür» daß man 8 führende Einsen auswählt» liegt darin« daß man bei der erforderlichen Tabellengröße leicht die Tabelle durch eine logische Implementierung ersetzen kann· Die Erfindung läßt sich natürlich auch mit einer anderen Anzahl statt 8 führender Einsen verwirklichen· .
Es ist nicht tauglich» den gesamten Nenner von η-Bits nachzuprüfen, und man kann auch nicht eine logische Schaltung implementieren» um die Anzahl der erforderlichen Vorverschiebungen anzuzeigen· Prüft man nur die führenden 8 Bits um die Vorverschiebungen durchzuführen» dann kann sich Uberfüllung ergeben» indem sich für
1 + d ergibt 10»00000O0... statt 1»11111H· · Bevor man (2)
also fortfährt ist es nötig, die Überfüllung in die Standardform 1»111111 ··· umzuwandeln· Das kann mau einfach dadurch durchführen, daß man von der überfüllten Zahl die 8 Rechtsverschiebungen der überfüllten Zahl abzieht· Figur1 ι zeigt eine Übersicht des Datenflusses bei Verwix'klichung der Erfindung, und anhand der Figuren 2,3 und 4 wird die Erfindung etwas weiter im Detail beschrieben·
109826/1517
BAD ORIGINAL
- 8 - P 15 930
Bei aera nun zu beschreibenden Ausführungsbeispiel wird der Nenner in der Standardform verwendet. Nach Figur 1 werden Dividend und Divisor mit einem Normalisierer 10 nomalisiert. Zunächst wird der Dividend N « 2 % in dem Register KT11OO gespeichert und der Divisor D » 2 0^jn *m Register KT2 101 gespeichert«
Die Mantisse des Nenners wird um eine Position nach links verschoben, was bedeutet» daß dar Nenner mit 2 multipliziert wird,
also 1 + d2* was genau so groß ist wie 1, S2 ^3 ^n* Diese
Ψ Daten werden dann in den Standardaddiererblock 400 über die Datenleitung ill gegeben· Die 7 führenden Bits von U2" einfach f2"3'4°5°6*7*8 · gelangen als.Eingang in den Tabellenleser 200* Der Ausgang des Tabellenlesers gibt die nötigen Schritte von Rechtsverschiebungen und Additionen oder Rechtsverschiebungen und Subtraktionsinformationen an« Die Eingänge des Tabellenlesers 200 sind in der nachfolgenden Tabelle 1 aufgeführt. Diese Eingänge aeigen die Besiehungen zwischen den 7 führenden Bits (fi"2 &„ — &«) des Nenners und der erforderlichen Anzahl von Rechtsverschiebungen, Additionen, Subtraktionen, um die bei diesem Ausführungsbeispiel gewünschten 8 führenden Binsen zu erzie» . len. Für den siebten Eingang entsprechend der siebten Zeile der Tabelle 1 ergibt sich:
S2S3 S4S5S6^7S8 12 3 4 5 6 7
1010000 + + +
Daraus kann man ersehen, daß, da das erste + unter der "3" steht, man drei Rechtsverschiebungen und Addition benötigt« Da das nächste + unter der W4M steht, die einen Platz neben dem voraufgehenden + steht» muß man dafür einen Platz nach rechts schieben und wieder addieren* Da das nächste + unter der "5" steht, die neben dan vorausgehenden + steht, muß man eine Einheit nach rechts verschieben und wieder addieren» Da schließlich das -
109826/151 7
BAD
- 9 - P 15 930
drei Positionen vom vorausgegangenen Eingang entfernt ist» muß man drei Positionen verschieben und subtrahieren. Das Ergebnis sind die 8 führenden Einsen. Die Information wird, um die Standardform von 1 + d/g\ zu bilden, benötigt. Der Standardaddiererblock 400 wird auch in den Kegistern MJRn (+) 301 und MRnC-) 302 gespeichert·
109826/1517
- 10 - P 15 930
T A'BELLE 1 .
Die führenden 8 Bits des Kenners Tie erforderliche Anzahl von
ßechtsverschiebungen, Additionen oder Subtraktionen
12 3 4 5 6 7 8
Immer 0 gilt L 0 d1* 1 d
0 0 5d6 «7 0
0 1 0 0 0 0 0
1 1 0 0 0 0 0
0 0 0 0 0 0 0
1 1 0 0 0 0 0
0 0 1 0 0 0 0
0 1 1 0 0 0 0
1 0 1 1 0 0 0
1 0 1 1 O 0 0
0 1 0 1 0 0 0
O 1 1 1 0 0 O
0 0 0 1 0 O 0
0 0 1 1 0 O 0
1 1 0 1 O O 0
1 1 1 1 0 0 0
1 0 0 0 0 0 0
1 0 1 1 0 0 0
0 O 0 0 1 0 0
0 0 0 1 1 0 0
0 1 1 0 1 0 0
0 1 1 1 1 0 0
0 1 0 0 1 0 0
O 1 O 1 1 0 0
0 0 1 0 1 0 0
0 0 1 1 1 0 0
1 0 0 0 1 0 0
1 0 0 1 1 0 O
1 1 1 1 1 0 0
1 1 1 1 1 0 0
1 1 0 0 1 0 O
1 0 1 0 0
1 1 1 0
•fr
109826/1517
Fortsetzung Tabelle ι.
Die führenden 8 Bits des Nenners Immer gilt d- » 1
1 1 1 1 1 0 0
0 0 0 0 0 1 0
0 0 0 0 1 1 .0
0 0 0 1 0 1 0
0 0 0 1 1 1 0
0 0 1 0 0 1 0
0 0 1 0 1 1 0
0 0 1 1 0 1 0
0 0 1 1 1 1 0
0 1 0 0 0 1 0
0 1 0 0 1 1 0
0 1 0 1 0 1 0
0 1 0 1 1 1 0
0 1 1 0 0 1 0
0 1 1 0 1 1 0
0 1 1 ,1 0 1 0
0 1 1 1 1 1 O
1 0 0 0 0 1 0
1 0 0 0 1 1 0
1 0 0 1 0 1 0
1 0 0 1 1 1 0
1 0 1 0 0 1 0
1 0 1 0 1 1 0
1 0 1 1 0 1 0
1 0 1 1 1 1 0
1 1 0 0 0 1 0
1 1 0 0 1 1 0
1 1 0 1 0 1 0
1 1 0 1 1 1 0
1 1 1 0 0 1 0
1 1 1 0 1 1 0
1 1 1 1 0 1 0
P 15 930
Die erforderliche Anzahl von Rechtsverschiebungen» Additionen oder Subtraktionen
3 4 5 6 7 8
«fr
+ + -fr •fr -fr + «fr -fr •fr -
•fr ■fr -fr
•fr + - -fr -fr
•fr -fr
•fr
•fr
10 9 8 2 6/1517
Fortsetzung Tabelle 1
Die führenden 8 Bits des Kenners Immer gilt d- « 1
1 1 1 1 1 1 C
0 0 0 0 0 0 1
0 0 0 0 0 1 1
0 0 0 0 1 0 1
0 0 0 0 1 1 1
0 0 0 1 0 0 1
0 0 0 1 0 1 1
0 0 0 1 1 O 1
0 0 0 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 1 1
0 0 1 0 1 0 1
0 0 1 0 1 i 1
0 0 1 1 0 0 1
0 0 1 1 0 1 1
0 0 1 1 1 0 1
0 0 1 1 1 1
0 1 0 0 0 0 1
0 1 0 0 0 1 1
0 1 0 0 1 0 T
0 1 0 0 1 1 1
0 1 0 1 0 0 1
0 1 0 1 O 1 1
0 1 O 1 1 0 1
0 1 0 1 1 1 1
0 1 1 0 0 0 1
0 1 1 0 0 1 1
0 1 1 0 1 0 1
0 1 1 0 1 1 1
0 1 1 1 0 0 1
0 1 1 1 0 1 1
0 1 1 1 1 0 1
P 15 930
Die erforderliehe Anzahl von Rechtsverschiebungen, Additionen oder Subtraktionen
1 2 3 4 5 6 7 8
•fr ♦
0 1
10
6/1517
P 15 930
Fortsetzung Tabelle 1
■ Die führenden 8 Bits des Nenners Immer gilt
1 O O O O O 1
1 O O O O 1 1
1 O O O 1 O 1
1 O O O 1 1 1
1 O O 1 O O 1
1 O O 1 O 1 1
1 O O 1 1 O 1
1 O O 1 1 1 1
1 O 1 O O O 1
1 O 1 O O 1 1
1 O 1 O 1 O 1
1 O 1 O 1 1 1
1 O 1 1 O O 1
1 O 1 1 O 1 1
1 O 1 1 1 O 1
1 1 O O O O 1
1 1 O O O 1 1
1 1 O O 1 O 1
1 1 O O 1 1 1
1 1 O 1 O O 1
1 1 O 1 O 1 1
1 1 O 1 1 O 1
1 1 O 1 1 1 1
1 1 1 O O O 1
1 1 1 O O 1 1
1 1 1 O 1 O 1
1 1 i O 1 1 1
1 1 1 1 O O 1
1 1 1 1 O 1 1
1 1 1 1 1 O 1
1 1 1 1 1 1 1
Die erforderliche Anzahl von Rechtsverschiebungen» Additionen oder Subtraktionen 1 2 3 4 5 6 7 8
•t· +
1Q9826/1517
- 14 - P 15 930
Die in dem ersten Addierer 421 des Addiererblocks 400 gespeicherten Daten werden von der Schaltstufe MRnC+) 301 gesteuert in der Weise» daß, wenn beim Bit η die Schaltstufe MRn (+) eingeschaltet ist, eine Rechtsverschiebung und eine Addition stattfindet,
1 + d2 vorwärtsgeschaltet wird um 2~n (i + dg), und die Summe über die Datenleitung 411 an den nächsten Addierer 422 gelangt. Wenn dagegen beim Bit η die Schaltstufe MRnC-) 302 eingeschaltet ist, dann findet eine Rechtsverschiebung und eine Subtraktion statt, und der Inhalt des Addierers 422, nämlich (1 + d«) . wird um —η
2 (1 + d2) + verringert» und das Ergebnis (1 + d2)f gelangt
über das Datenkabel 412 an das Register 423 und über das Datenkabel 417 an den dritten Addierer 424· Der führende Bit von (1 · + dp)r» im Register 423 wird mittels eines Nulltesters ZT überprüft. Wenn der führende Bit LB im Register 423 null ist, dann gelangt der Inhalt des Registers 423 über das Datenkabel 416 an das Register 425 und ist die ,Standardform des Nenners.
Wenn der führende Bit (i+d2)£ eine Eins ist, dann ist das ein Zeichen dafür, daß Uberfüllung stattgefunden hat, und der Inhalt des Registers 423 wird um 2 (i+d2)p verringert und das Ergebnis über das Datenkabel 414 an das Register 425 gegeben. Der Inhalt des Registers 425 ist die Standardfonm des Nenners,1 + d(2)a Die~ ser Inhalt wird an die Genaui
zwar über das Datenkabel 415«
. des Registers 425 ist die Standardfonm des Nenners,1 + d(2) * ser Inhalt wird an die Genauigkeitssteuereinheit 500 gegeben und
Zunächst hat die Genauigkeitssteuereinheit die Funktion eines Schieberegisters· Die Genauigkeitssteuereinheit dient dazu» die Genauigkeitssteuerzahl zu entwickeln. Wenn nur eine 16-Bit-Genauigkeit erforderlich ist» dann ist^die Genauigkeitssteuerzahl 5» Wenn eine größere Genauigkeit, beispielsweise 32 oder 64 Bitgenauigkeit, erforderlich ist, dann wird die Genauigkeitssteuereinheit benutzt· Wenn die Zahl der Genauigkeitsbits festgelegt ist, zum Beispiel auf 32 Bits, dann werden die führenden 32 Bits des
109826/151 1
- 15 - P 15 930
Anteils d/gy des Registers 500 Über die Dätenleitung 530 an den Multiplizierer 530 gesandt und-Über die Datenleitung 511 an das Verschieberegister 502« Der Inhalt des Verschieberegisters 502 wird um 2 Positionen nach rechts verschoben» wobei die führenden zwei Bits auf Sins gesetzt werden« und dann wird der Inhalt an den Addierer 503 gegeben. Der Inhalt des Schieberegisters 502 wird komplementiert und um eine Position nach rechts verschoben» wobei der ganzzahlige Bit auf Eins gesetzt wird und dann wird der Inhalt über das Datenkabel 520 an das Register 602 der Rückschaltstufe gegeben· In dem Multiplizierer werden die führenden 32 Eits des Anteils des Inhaltes des Registers 500 mit ihrem eigener. Komplementär multipliziert* Das Produkt wird um zwei Positionen nach rechts geschoben und Über das Datenkabel 540 an den Addierer 503 gegeben. ,Der Inhalt des·Addierers 503 wird mit den einlaufenden Daten addiert» und das Ergebnis gelangt.über das Datenkabel 513 in das Verschieberegister 504· Der Inhalt des Registers 504 wird um eine Einheit nach rechts geschoben und komplementiert und das Ergebnis wird in dem Register 505 gespeichert· Der Inhalt des Registers 505 wird mit S1 bezeichnet» und es handele sich um die Genauigkeitssteuernupuer· Dieser Inhalt gelangt an die Ktickschalteinheit 600 und zwar über das Datenkabel 515-
Der Inhalt der Register 600 und 60S gelangt über das Datenkabel 630 an den Multiplizierer» Das Produkt Q1 wird um 2 CL vermehrt» wenn der führende Bit im Register 423 eingeschaltet war wie auf der Leitung 437 angezeigt« Dieses neue Q1 wird Q1m genannt (es handelt sich um ein modifiziertes Q1 bei dem die Überfüllsituation berücksichtigt worden ist) und gelängt über das Datenkabel 640 an den Addierer 621· Wenn das Register MRn(+) eingeschaltet war» dann findet eine Rechtsverschiebung und Addition statt, Q1m wird vermehrt im -im2""Ä 4 und das Ergebnis Q2 gelangt über das Datenkabel 611 an den nächsten Verschieber und Addierer 622. Wenn dagegen fJberfÜlluiig stattgefunden hat, dann kann der Ausgang durch das Komplementär auf der Leitung 437 direkt an das Verschiebe- und Addier-
109826/15 17
- 16 - P 15 930
register 621 gegeben werden«
Wenn das Register MRn(O eingeschaltet war, wird Q2 um 2~"nQ2 im Addierer 622 verringert· Das Ergebnis Q3 wird um eine Position nach links verschoben und gelangt über das Datenkabel 612 an das Register 623. Wenn das Register MRnC-) abgeschaltet war, dann wird der Inhalt des Registers 621, nämlich Q2 um eine Position nach links verschoben und dann Über das Datenkabel 615 an das Register 623 gegeben· Diese Rückschaltungen justieren wieder die Ausgänge Q1 oder Q1m um die ursprüngliche Handhabung zu berücksichtigen, die durch das Tabellenlesen·aura Zwecke der Gewinnung der Standardform des Nenners gegeben war* Der Inhalt des Registers 623» nämlich Q„r ist das Reziproke des normalisierten Anteils der Zahl d_. Um das Reziproke einer Zahl oder eines Quotienten von zwei Zahlen zu bilden* wird Q^ an die Q-R-Einheit 700 gegeben und zwar über das Datenkabel 614« Das Register R™ 100 erhält den Exponenten und die Mantisse des normalisierten Zählers· Der Mantissenanteil gelangt über das Datenkabel 730 an den Multiplizierer, während der Exponentenanteil über das Datenkabel 750 an das Quotientenregister 770 gelangt· Das Register R72 101 hält den normalisierten Exponenten und die Mantisse des Zählers« Der Mantissenanteil wurde dazu verwendet» das Reziproke der normalisierten Anteilszahl zu gewinnen. Der Exponentenanteil gelangt an das Reziprokregister und zwar über die Datenleitung 716·
Wenn nur eine ι6-Bit-Genauigkeit erforderlich istr dann kann der Durchlauf durch die Genauigkeitssteuereinheit unterlassen werden, und der Inhalt des Registers 602 kann um eine Position nach rechts verschoben werden (also S1* » 0,5) und direkt als Eingang in das Register 624 gegeben werden, sofern überfüllung vorlag oder in das Register 621 sofern keine. Überfüllung vorlag.
Die Q-R'-Einheit enthält zwei Schieberegister t nämlich das Quotientenregister 770 und das Reziprokregister 780. Die einlaufenden Daten Q4 gelangen an zwei Plätze, nämlich an den Multiplizierer
1 09826/ 15 17
BAD ORIGINAL
- 17. - P 15 930
über das Datenkabel 730 und an das Reziprokschieberegister 780» Wenn das Reziproke der Zahl gefordert wird, dann wird der Inhalt' des Registers 780 um £D Positionen nach rechtswerschoben. Das R^iproke der Zahl wif;d dadurch gebildet. Wenn der Quotient (Wähler/Nenner) gefordert wird, dann wird das Produkt von Q4. unä die Mantisse des Zählers über die Leitung 740 an das Quotientenregister 770 gegeben, und der Inhalt des Quotientenregisters wird um Ej^D Plätze nach links verschoben· Die Menge Bjj-Bq wird in einem Addierer, der als Teil des Registers 770 vorgesehen ist, gebildet. J)61. Quotient der zwei Zahlen ist nun gebildet.
Beispiel .
20*57
Bs soll der Quotient von »it 32 Bit Genauigkeit gefunden werden« In binärer Schreibweise lauten' die Zahlen N m 100000001001
D « 1010101010110101.
Nach Normalisierung und Linksausrichtung ergibt sich im'Register R™100 E^ » 12
M1n « 0,100000001001 im Register R12 101 Ep * 16
d^ β 0,1010101010110101 2 djjj s 1,010101010110101 ,
Dieser Anteil wird für das Tabellenlesen über die Datenleitung 111 verwendet. Die Ausgabe des Tabellenlesers gibt die erforderlichen Rechtsverschiebungsinformationen an· Diese Informationen werden in dem Register MRn(+) gespeichert, im Beispiel ist das Register MR_(+) eingeschaltet. Die Date 1 ♦ dg wird in dem Addierer 421 zu 2~· (1 + dg) addiert, und das Ergebnis für (1 + dß)+ lautet 10,0000000000011111·
Da das Register MRnC-) auf null steht, findet in dem zweiten Addierer 422 keine Operation statt, und (i+cl2)p ist genau so groß wie (1 + d2)+ und der Wert gelangt an das Register 423 um der. führenden Bit zu testen. Da der führende Bit des Registers 42?
109826/1517
- 18 - P 15 930 -
Eins ist» gelangt der Wert (i +-dg·)ρ an den dritten Addierer 424 und zwar über das Kabel 413· In dem Addierer 424 wird 1 + d/g\ gebildet» indem der Wert (1 ♦ dg) ^ um den Wert 2 (ι + ά2)£ verringert wird· Es ergibt sich
10,0000000000011111
-. 0,000000100000000000011111
1,111111100001111011100001 .
1 + d/2\ gelangt über das Datenkabel 414 an das Register 425* Da die Genauigkeit 32 Bits umfaßt, werden die 32 Bits in der Anteilsabteilung ö/g\ herangezogen, nämlich:
0,1111111000011110111000010000 0
und gelangen über das Dätenkabel 530 an den Multiplizierer 550 und werden auch über das Datenkabel 511 in das Register 502 eingespeist< Der Inhalt des Registers 502 wird um zwei Bits nach rechts verschoben, und die zwei ersten Bits werden auf Eins gesetzt. Die Zahl die sich dann ergibt, lautet:
0,11111111100001111011100001000000.
Diese Zahl wird in dem Register 503 gehalten* Der Inhalt des Registers 500 wird komplementiert und um einen Bit nach rechts verschoben und der ganzzahlige Bit wird auf Bins gesetzt. Es ergibt sich die Zahl
1,0000000011110000100011111
die über das Kabel $20 in das Register 602 gelangt· In dem Multiplizierer in dem dg mit dgf (dem Komplement) multipliziert wird, lautet nach Produkt
0,111111100001111011100001
X 0.000000011110000100011111
0,00000001110 111011001011011001010 (Hur die 32 führenden Bits werden in Betracht gezogen)·
Diese Date wird nach rechts verschoben und gelangt an den Addierer 503» der nun die folgenden zwei Zahlen enthält: 0,0000000001110 111011001011011001010 0,11111111100001111011100001·
1 09826/ 1517 ^0 original
- 19 - P 15 930
2S. wird gebildet durch Addieren dieser beiden Zahlen t und es ergibt sich
0,1111111111111111000111011111001010 (wobei wiederum nur die
32 Führungsbits in Betracht gezogen sind)·
Diese Date gelangt über das Datenkabel 513 an das Schieberegister 504· Der Inhalt des Schieberegisters 504 vird dann um einen Bit nach rechts vorschoben und komplementiert und gelangt über das Datenkabel 514 an das Register 505» Der Inhalt des Registers 505 ist die Genauigkeitssteuerzahl S1*. Da die Genauigkeit 32 Bits umfaßt, verden die 32 führenden Bits in Betracht gezogen» und der Inhalt des Registers 505 lautet:
0,10000000000000000111000100000111 »
Diese Date gelangt Über das Datenkabel 515 der Rückschalteinheit an das Register 600. Der Inhalt des Registers 600 und 602 lautet nun wie folgtt .
0,10000000000000000111000100000111 1,000000001111000010001111100 0.
Diese zwei Daten gelangen über das Datenkabel 630 an den Multiplizierer » und das Produkt Q1 wird zurück geleitet an das Verschiebe- und Additionsregister 624 und zwar über das Datenkabel 641· Das Produkt Q1 hat den Wert
0,1000000001111000101110010011000100.
Da der führende Bit LB in Register 423 eine Sins war« wird Q1 vermindert ua 2 Q1* und das Ergebnis Q1m ergibt sich zu 0,01111111111110000100000001111000 (wobei wieder nur die
Führungsbits in Betracht gezogen sind).
109826/1517 „.nuM.
ORIGINAL
- 20 - P 15 930
Q1 m gelangt dann an das Verschiebe- und Additionsregister 621 und zwar über das Datenkabel 6i4«Wemdas Register MR-1C+) eingeschaltet war, wird Q1m zu 2 Q1m addiert» und das Ergebnis Q2 lautet: 0,10111111IiIIOIOOOIIOOOOOIOIIOiOOO.
wenn das Register MRnC-) ausschaltet war» dann gilt Q3 ~ Q2, und der Inhalt des Registers 621 wird um eine Bitposition nach rechts verschoben und gelangt über das Datenkabel 615 an das Register 623· Der Inhalt des Registers 623 ist das Reziproke des normalisierten Anteils der Zahl Q4 und lautet:
* 1,011111111110100011000001011010000.
Diese Date gelangt über das Datenkabel 614 an das Reziprokverschieberegister 780 und über das Datenkabel 730 an den Multiplizierer·
Das Reziproke von ^ erhält man durch Verschiebung von Q^ um 16 Bits nach rechts,1 und es ergibt sich:
0,000000000000000101111111111010001100000101101000. Diese Zahl lautet in Dezimaleinheiten 0*00002288277.
Wenn man den Quotienten einer Division wünscht» dann gelangt Q« mit nm über das Datenkabel 730 an den Multiplizierer· Das Produkt gelangt zurück an das Quotientenregister 770 und zwar über das Datenkabel 740· Das Produkt lautet dann:
0,11000000110011000101001110100000110«
Den Quotienten erhält man durch Verschieben dieser Date um BN*"BD-Positionen nach links, wobei in diesem Pall En-E0 den Wert -4 hat. Die Verschiebung erfolgt also in umgekehrter Richtung, das heißt also» 4 Positionen nach rechts» Der Quotient g- lautet;
0,000011000000110011000101001110100000110010101.
Diese Zahl lautet in Dezimaleinheiten 0,0470698611.
109826/15 17
BAD ORIGINAL
- 21 - P 15 930
Um Zeit einzusparen» wird* wenn 1 + <3v2) 16 ^ätoende Binsen hat, die Berechnung in der Genauigkeitssteuereinheit übersprungen, so daß man eine Multiplikation einspart·
Bei dem eben beschriebenen Beispiel betrug die Genauigkeit 32 Bitpositonen» Wenn nur ι6-Bit-Genauigkeit erforderlich ist» dann kann man den Durchlauf durch die Genauigkeitssteuereinheit, wie oben beschrieben, eliminieren· Wenn andererseits eine H · 32 Bit-Genauigkeit erforderlich ist* dann finden n~Passagen durch die Genauigkeitssteuereinheit statt· ehe in der Rückschaltstufe fortgefahren wird· Dieser Sachverhalt ergibt sich aus Gleichung 6·η·
Wenn nur eine 8-Bit-Genauigkeit erforderlich ist, dann sind in
der Standardforra 1,111 nur 4 führende liullen erforderlich»
In diese» Fall wird die Tabelle 1 durch eine sehr einfache Tabelle 2 ersetzt·
*2S3&4 *. 12 3 4
0 0 0 + + ·.
0 0 1 + +
0 10 +
0 11 + +
10 0 +
10 1 4- +
t 1 0 +
111
Für HR1 ergibt sich
"«ι-WV+VVWW
oder einfacher
m2 m W
MR3 und MR- kann leicht entsprechend abgeleitet
worden·
109826/1517 ßAD ORIGINAL
- 22 - P 15 930
Die Erfindung verwendet ein Konvergenzverfahren, um den Quotienten einer Division oder den Reziprokwert einer Zahl zu errechnen.
Die Werte ^g ^3 54 65 δβ ^7 **8 der acht ■£>ölirenden Bits der Mantisse des Nenners werden in eine Tabelle beziehungsweise ein Tablo eingegeben und es wird dadurch die Anzahl der Verschiebungen, Additionen oder Subtraktionen ermittelt und in Registern MR(h-) und MR(-) gespeichert. Nachdem daraufhin diese Verschiebungen und Additionen oder Verschiebungen und Subtraktionen durchgeführt sind, wird die Standardform des Nenners gebildet. In einer einzigen weiteren Multiplikation wird der Semireziprolcwert des normalisierten Anteils gebildet und dann in einer Rückschaltstufe der Reziprokwert des normalisierten Anteils gebildet. Zur Bildung des Quotienten der Division benötigt man dann eine einzige weitere Multiplikation.
Die Erfindung kann dazu dienen, den Reziprokwert einer Zahl durch zrei Multiplikationsoperationen aufzufinden und den Quotienten zweier Zahlen durch drei Multiplikationen aufzufinden. Im Vergleich mit den bekannten schnellsten Verfahren und Schaltung der hier in Frage stehenden Art ermöglicht die Erfindung nicht nur eine Vergrößerung der Rechengeschwindigkeit sondern auch eine Verringerung der Maschinenausrüstung.
109826/1517
BAD ORiGlNAL

Claims (3)

  1. P 15 930 12.11,70
    ANSPRÜCHE
    (ι /. Verfahren zur Gewinnung des Reziproken einer Zahl D, gekennzeichnet durch die Verfahrensschritte:
    (1) Gewinnen der nach links justierten Mantisse von D, mit dem Wert d^;
    (2) mathematisches Ausrichten der justierten Mantisse um eine Standardform der Zahl zu gewinnen, die eine vorbestimmte Anzahl von führenden Eins-Bits enthält;
    (3) gewinnen einer Genauigkeitssteuerzahl;
    (4) gewinnen eines Näherungswertes des Reziproken der nach links justierten Mantisse d^
    (5) multiplizieren des Näherungswertes mit der Genauigkeitssteuerzahl um die Bits des Reziprokvertes mit der gewünschten Genauigkeit zu gewinnen; und
    (6) verschieben der Bits des Reziprokwertes um die tatsächliche Linksausrichtung der Mantisse.
    109826/151.7
    P 15 930
  2. 2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß zusätzlich die verschobenen Bits des Reziprokwertes mit einer Zahl N multipliziert v/erden um den Quotienten von N dividiert durch D zu gewinnen.
  3. 3. Schaltung zur Gewinnung des Reziprokwertes einer nach links justierten Zahl D» zur Ausbübung des Verfahrens nach Anspruch oder 2, dadurch gekennzeichnet, daß vorgesehen sind, ein Tabellenleser (200) zur Überprüfung der Bits der Mantisse dm der Zahl D und Lieferung einer Information für die erforderliche mathematische Rechnung um die Mantisse in eine Standardform mit einer vorbestimmten Zahl von führenden Eins-Bits umzuwandeln;
    ein Addiererblock (400), der über Verschiebe- und Additionsregister (300), die auf Grund des Ausgangs des Tabellenlesers bestimmte mathematische Rechnung definieren an den Tabellenleser (200) ausgangsseitig angeschlossen ist.
    eine Genauigkeitssteuereinheit (500) die ausgangsseitig an den Addiererblock (400) angeschlossen ist und eine Genauigkeitssteuerzahl als Funktion der vorbestimmten Zahl | der Genauigkeitsbits liefert;
    eine arithmetische Rückschaltstufe (600) zur Ermittlung eines Annäherungswertes des gewünschten Reziprokwertes mit einer niedrigeren als der gewünschten Genauigkeit; und
    einen Multiplizierer (550) der an die GenauigkeitsstGuereinheit (500) und an die Rückschaltstufe (600) angeschlossen ist und den genannten Annäherungswert mit der Genauigkeitssteuerzahl multipliziert um die Bits des gesuchten Reziprokwertes mit der gewünschten Genauigkeit zu ermitteln.
    10 9 8 2 6/1517
    BAD ORiGiNAL
    Leerseite
DE19702058612 1969-12-18 1970-11-28 Verfahren und Schaltung zur Bildung eine Reziprowertes Pending DE2058612A1 (de)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
US88623669A 1969-12-18 1969-12-18

Publications (1)

Publication Number Publication Date
DE2058612A1 true DE2058612A1 (de) 1971-06-24

Family

ID=25388674

Family Applications (1)

Application Number Title Priority Date Filing Date
DE19702058612 Pending DE2058612A1 (de) 1969-12-18 1970-11-28 Verfahren und Schaltung zur Bildung eine Reziprowertes

Country Status (5)

Country Link
US (1) US3633018A (de)
JP (1) JPS5229135B1 (de)
DE (1) DE2058612A1 (de)
FR (1) FR2071798A5 (de)
GB (1) GB1310376A (de)

Families Citing this family (30)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3777132A (en) * 1972-02-23 1973-12-04 Burroughs Corp Method and apparatus for obtaining the reciprocal of a number and the quotient of two numbers
DE2224329A1 (de) * 1972-05-18 1973-11-29 Siemens Ag Rechner zur statischen teilbarkeitserkennung und division von zahlen n, die durch drei, sechs und neun teilbar sind
US3828175A (en) * 1972-10-30 1974-08-06 Amdahl Corp Method and apparatus for division employing table-lookup and functional iteration
US4025773A (en) * 1974-07-19 1977-05-24 Burroughs Corporation Enhanced apparatus for binary quotient, binary product, binary sum and binary difference generation
US4047011A (en) * 1974-07-19 1977-09-06 Burroughs Corporation Modular apparatus for binary quotient, binary product, binary sum and binary difference generation
US4011439A (en) * 1974-07-19 1977-03-08 Burroughs Corporation Modular apparatus for accelerated generation of a quotient of two binary numbers
JPS5633734A (en) * 1979-08-25 1981-04-04 Aisuke Katayama Divisor conversion type high-speed division system
US4414642A (en) * 1981-04-09 1983-11-08 Bell Telephone Laboratories, Incorporated Apparatus for generating the inverse of binary numbers
JPS57172444A (en) * 1981-04-15 1982-10-23 Hitachi Ltd Approximate quotient correcting circuit
US4481600A (en) * 1982-03-26 1984-11-06 Hitohisa Asai Apparatus for speeding up digital division in radix-2n machine
DE3377029D1 (en) * 1982-06-15 1988-07-14 Toshiba Kk Apparatus for dividing the elements of a galois field
DE3274164D1 (en) * 1982-12-23 1986-12-11 Ibm Method and apparatus for division operations
US4594680A (en) * 1983-05-04 1986-06-10 Sperry Corporation Apparatus for performing quadratic convergence division in a large data processing system
JPS60142738A (ja) * 1983-12-30 1985-07-27 Hitachi Ltd 内挿近似を使用する除算装置
US4823301A (en) * 1987-10-22 1989-04-18 Tektronix, Inc. Method and circuit for computing reciprocals
JPH02156328A (ja) * 1988-12-08 1990-06-15 Toshiba Corp 逆数回路
US5249149A (en) * 1989-01-13 1993-09-28 International Business Machines Corporation Method and apparatus for performining floating point division
JPH0831029B2 (ja) * 1989-07-11 1996-03-27 日本電気株式会社 除算用近似逆数生成装置
US5825681A (en) * 1996-01-24 1998-10-20 Alliance Semiconductor Corporation Divider/multiplier circuit having high precision mode
US6128639A (en) * 1996-06-28 2000-10-03 Cray Research, Inc. Array address and loop alignment calculations
US6144980A (en) * 1998-01-28 2000-11-07 Advanced Micro Devices, Inc. Method and apparatus for performing multiple types of multiplication including signed and unsigned multiplication
US6115733A (en) * 1997-10-23 2000-09-05 Advanced Micro Devices, Inc. Method and apparatus for calculating reciprocals and reciprocal square roots
US6134574A (en) * 1998-05-08 2000-10-17 Advanced Micro Devices, Inc. Method and apparatus for achieving higher frequencies of exactly rounded results
US6115732A (en) * 1998-05-08 2000-09-05 Advanced Micro Devices, Inc. Method and apparatus for compressing intermediate products
US6223198B1 (en) 1998-08-14 2001-04-24 Advanced Micro Devices, Inc. Method and apparatus for multi-function arithmetic
US6269384B1 (en) 1998-03-27 2001-07-31 Advanced Micro Devices, Inc. Method and apparatus for rounding and normalizing results within a multiplier
US6393554B1 (en) 1998-01-28 2002-05-21 Advanced Micro Devices, Inc. Method and apparatus for performing vector and scalar multiplication and calculating rounded products
US20060129624A1 (en) * 2004-12-09 2006-06-15 Abdallah Mohammad A Method and apparatus for performing a divide instruction
US20070083586A1 (en) * 2005-10-12 2007-04-12 Jianjun Luo System and method for optimized reciprocal operations
US8681973B2 (en) * 2010-09-15 2014-03-25 At&T Intellectual Property I, L.P. Methods, systems, and computer program products for performing homomorphic encryption and decryption on individual operations

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3234369A (en) * 1961-12-13 1966-02-08 Ibm Square root device employing converging approximations
US3508038A (en) * 1966-08-30 1970-04-21 Ibm Multiplying apparatus for performing division using successive approximate reciprocals of a divisor

Also Published As

Publication number Publication date
GB1310376A (en) 1973-03-21
US3633018A (en) 1972-01-04
JPS5229135B1 (de) 1977-07-30
FR2071798A5 (de) 1971-09-17

Similar Documents

Publication Publication Date Title
DE2058612A1 (de) Verfahren und Schaltung zur Bildung eine Reziprowertes
DE2246968C2 (de) Einrichtung zur Multiplikation zweier Gleitkommazahlen
DE1549476C3 (de) Anordnung zur Ausführung von Divisionen
DE3143223C2 (de)
DE19758079A1 (de) Verfahren und Vorrichtung zur Galoisfeld-Multiplikation
DE69032890T2 (de) Verfahren und Gerät zur Ausführung der Quadratwurzelfunktion mit Hilfe eines Multiplizierers rechteckigen Seitenverhältnisses
DE68924386T2 (de) Verfahren und Gerät zur Radix-2**n-Division mit überlappender Quotientenbitauswahl und gleichzeitiger Rundung und Korrektur des Quotienten.
DE1549480A1 (de) Datenverarbeitungsanlage
DE10013068C2 (de) Potenzierungsoperationsvorrichtung
DE3852576T2 (de) Einrichtung und Verfahren für eine erweiterte Arithmetik-Logik-Einheit zur Beschleunigung der ausgewählten Operationen.
DE1499281B1 (de) Rechenmaschine fuer logarithmische Rechnungen
DE1549508B2 (de) Anordnung zur uebertragsberechnung mit kurzer signallaufzeit
EP0265555B1 (de) Verfahren und Schaltungsanordnung zur Addition von Gleitkommazahlen
DE3434777C2 (de)
EP1474741B1 (de) Vorrichtung und verfahren zum berechnen eines ergebnisses aus einer division
DE69130756T2 (de) Gleitkommamultipliziergerät mit drei Übertragsfortpflanzungsaddierern, welche in parallel arbeiten können
DE1125685B (de) Rechenmaschine
DE3132611C2 (de)
DE10050589B4 (de) Vorrichtung und Verfahren zur Verwendung beim Durchführen einer Gleitkomma-Multiplizier-Akkumulier-Operation
DE1103646B (de) Inkrement-Rechenmaschine
DE1524146C (de) Divisionseinrichtung
DE2150853C3 (de) Divisions-Vorrichtung für ein serielles Vier-Spezies-Rechenwerk
DE69130621T2 (de) Schneller digitaler Dividierer
DE1101818B (de) Rechenmaschine zur Ausfuehrung von Divisionen und Multiplikationen
DE2432979C3 (de) Mit gemischter Zahlendarstellung arbeitende Einrichtung zum Multiplizieren zweier komplexer Zahlen und Addieren einer dritten komplexen Zahl zum Produkt