DE69032890T2 - Verfahren und Gerät zur Ausführung der Quadratwurzelfunktion mit Hilfe eines Multiplizierers rechteckigen Seitenverhältnisses - Google Patents

Description

TECHNISCHES GEBIET DER ERFINDUNG
• Diese Erfindung betrifft allgemein das Gebiet der Durchführung von mathematischen Funktionen unter Verwendung von elektronischen Vorrichtungen. Insbesondere betrifft die vorliegende Erfindung ein Verfahren und eine Vorrichtung zur Durchführung der Quadratwurzel-Funktion in einem System, bei dem eine Rechteckseitenverhältnis-Multiplizierschaltung verwendet wird.
HINTERGRUND DER ERFINDUNG
• Die Arithmetik-Einheit ist eine der wichtigsten Komponenten von jedem integrierten elektronischen Datenverarbeitungssystem. Arithmetik-Einheiten führen eine große Vielzahl von mathematischen Funktionen mit Operanden durch, die von anderen Teilen eines integrierten Systems geliefert werden. Die Basisfunktionen, Addition, Subtraktion und Multiplikation, werden heute schnell und effizient in Arithmetik-Einheiten durchgeführt. Gleichwohl sind die derzeit verfügbaren Techniken zur Durchführung der exakten Quadratwurzel-Funktion bezüglich Effizienz und Geschwindigkeit noch nicht vollständig zufriedenstellend.
• Der Begriff exakte Quadratwurzel wird verwendet, um Ergebnisse zu beschreiben, die zu denen äquivalent sind, die mittels des herkömmlichen unabgekürzten Quadratwurzel-Prozesses erzeugt werden; d. h., ein positiver Wert für die Partialwurzel und ein "Rest", der, wenn nicht negativ, genau kleiner als das Zweifache der Partialwurzel plus eine Einheit in der letzten Stelle ist (oder das Zweifache der Wurzel minus eins, wenn negativ), so daß, mit endlicher Präzision, die Summe aus der quadrierten Partialwurzel und dem Rest genau gleich dem Operanden ist.
• Eine exakte Quadratwurzel schafft ein Ergebnis, das brauchbarer ist als eine angenäherte Quadratwurzel mit begrenztem Fehler. Die exakte Quadratwurzel schafft die Basis zur Implementierung von unendlich präzisen Rundungen, wie durch IEEE-754- 1985 spezifiziert. Außerdem schaffen die Partialwurzel und der Rest, aus denen die exakte Quadratwurzel gebildet ist, einen Anfangspunkt zur Einleitung einer nachfolgenden Bestimmung einer exakten Quadratwurzel mit höherer Präzision ohne Bezugnahme auf den ursprünglichen Operanden. Keines dieser Merkmale wird aus einer angenäherten Quadratwurzel mit begrenztem aber unbestimmten Fehler erhalten.
• Eine Technik zum Auffinden der exakten Quadratwurzel ist eine binäre Version des herkömmlichen unabgekürzten Quadratwurzel-Verfahrens. Dieses Verfahren leidet unter dem Nachteil, daß jede Iteration lediglich 1 bis 3 Bits zur Partialwurzel beiträgt und viele Iterationen erfordert, wenn die Präzision des Operanden erhöht wird. Gleichwohl wird dadurch eine exakte Quadratwurzel erzeugt, die für eine präzise Rundung geeignet ist.
• Ein weiteres, derzeit verfügbares System verwendet ein Quadratwurzel-Verfahren unter Verwendung einer Newton-Raphson- Näherungstechnik. Bei diesem System wird eine Näherung des Reziprokwertes der Wurzel unter Verwendung eines iterativen Prozesses berechnet, um einen Näherungswert für den Reziprokwert in einem Hochpräzisionsformat zu erhalten. Die Hochpräzisions- Reziprokwert-Näherung wird dann mit dem Hochpräzisions-Operanden multipliziert, um eine Hochpräzisions-Abschätzung der Wurzel zu erhalten. Lediglich eine Grenze des unbestimmten Fehlers der geschätzten Wurzel ist bekannt, und diese Information ist für die Implementierung einer präzisen Rundung nicht ausreichend. Um eine exakte Quadratwurzel zu erhalten, wird die Unbestimmtheit in dem Fehler durch eine zweite Hochpräzisions-Multiplikation beseitigt. In dem zweiten Hochpräzisions-Multiplikationsschritt wird die genäherte Wurzel mit sich selbst multipliziert, und eine exakte Differenz zwischen dem Operanden und der genäherten quadrierten Wurzel wird berechnet. Diese Information ist dann ausreichend, um die Wiedergewinnung des Restes zu ermöglichen, und/oder um geeignete, präzise Rundungsprozeduren zu erhalten. Deshalb erfordert die exakte Newton-Raphson-Quadratwurzel zwei Hochpräzisions-Multiplikationen, die zeitraubend sind.
• IEEE TRANSACTIONS ON COMPUTERS, Vol. C-21, No. 8, 08.72, Seiten 837-847, C. V. Ramamoorthy: "Some properties of Iterative Square-Rooting Methods Using High-Speed Multiplication" offenbart Verfahren zur schnellen Durchführung einer Quadratwurzel- Berechnung, die Multiplikationen und keine Divisionen verwenden. Jeder Algorithmus wird nach Konvergenz-Geschwindigkeit, Effizienz und Implementierung beurteilt. Einer der bereits bekannten Algorithmen wird als der F-Algorithmus bezeichnet; er arbeitet mit gerundeten Werten des Reziprokwertes.
• Daher ist die Forderung nach einem System erwachsen, bei dem ein Quadratwurzel-Prozeß verwendet wird, der zu einer exakten Quadratwurzel führt, für geeignete präzise Rundungsprozeduren verwendet werden kann, aber weniger zeitraubend und effizienter ist als früher entwickelte Systeme.
ZUSAMMENFASSUNG DER ERFINDUNG
• Gemäß der vorliegenden Erfindung ist eine Schaltung zur Berechnung einer exakten Quadratwurzel eines Operanden nach Anspruch 1 und ein Verfahren zur Berechnung einer exakten Quadratwurzel eines Operanden nach Anspruch 8 vorgesehen.
• Das Quadratwurzel-System der vorliegenden Erfindung bestimmt zunächst eine Näherung des Reziprokwertes der Wurzel, verändert und trunkiert ihn; anschließend als der gerundete Reziprokwert bezeichnet, genau auf eine Anzahl von Bits, die benötigt wird, um im wesentlichen die kleinere Seite einer Rechteckseitenverhältnis-Multiplizierschaltung zu füllen. Das Quadratwurzel-System erzeugt dann Wurzelzahlenwerte, die einer sehr großen Basis entsprechen. Diese Großbasis ist im wesentlichen gleich der Anzahl von Bits von der kleineren Seite des Rechteck-Multiplizierers. Die Präzision, die für den gerundeten Reziprokwert erforderlich ist, ist begrenzt auf eine Zahl in dieser Großbasis zuzüglich geeigneter Schutzbits. Es ist wichtig, daß der Fehler in dem gerundeten Reziprokwert unbestimmt bleiben kann, da für den Prozeß bezüglich des Fehlers des Reziprokwert-Betrages lediglich eine Grenze benötigt wird, wodurch eine zeitraubende Eigenschaft des Newton-Raphson-Prozesses zur Bestimmung von exakten Quadratwurzeln vermieden wird. Jeder Wurzelzahlenwert wird bestimmt, indem der gerundete Reziprokwert der Wurzel in dem Rechteck-Multiplizierer mit dem Rest multipliziert und das Ergebnis geeignet trunkiert wird. Die Wurzelzahlenwerte werden seriell mit zugehörigen genauen Restwerten bestimmt. Jeder Wurzelzahlenwert, der durch die Technik bestimmt wird, ist einer von zumindest zwei möglichen Werten in dem Großbasissystem, wo der neue, vorzeichenbehaftete Restwert kleiner als eine Einheit des Wertes in der letzten Stelle des bestimmten Wurzelzahlenwertes ist. Solche vorzeichenbehafteten Restwerte sind dann ausreichend für die vereinfachte Implementierung von präzisen Rundungen, wie durch die IEEE-754-1985 spezifiziert. Durch diese Verwendung eines Rechteck-Multiplizierers sind keine nachfolgenden Hochpräzisions-Multiplikationsschritte erforderlich.
• Ein wichtiger technischer Vorteil der vorliegenden Erfindung liegt in der Tatsache begründet, daß eine Rechteckseitenverhältnis-Multiplizierschaltung verwendet wird. Die Verwendung des Rechteck-Multiplizierers spart Zeit an vielen Stellen des Quadratwurzel-Prozesses. Jeder der Multiplikationsschritte, die verwendet werden, um die Wurzelzahlenwerte zu bilden, sind sehr viel einfachere kurz-mal-lang-Multiplikationen. Noch wichtiger, die Multiplikation und anschließende Subtraktion, die erforderlich sind, um den neuen exakten Rest zu bilden, können alle durch eine einzige Anwendung des Rechteck-Multiplizierers erreicht werden. Weitere Zeiteinsparungen resultieren aus der Tatsache, daß die erste Schätzung des Reziprokwertes der Wurzel nur mit der Präzision der kürzeren Seite des Rechteck-Multiplizierers geschätzt werden muß. Dies erspart die Multiplikationsschritte, die bei den Newton-Raphson-Iterationen erforderlich sind, um die Genauigkeit der Schätzung auf eine Hochpräzisionsbreite zu erweitern, und ebenso die Einsparung der nachfolgenden Hochpräzisions-Multiplikationen, die verwendet werden, um die Unbestimmtheit in der Wurzel-Näherung zu vermeiden.
KURZBESCHREIBUNG DER ZEICHNUNGEN
• Ein besseres Verständnis der vorliegenden Erfindung kann unter Bezugnahme auf die detaillierte Beschreibung und die Ansprüche erreicht werden, wenn diese zusammen mit den beiliegenden Zeichnungen betrachtet werden, in denen:
• Fig. 1 ein Flußdiagramm ist, in dem das Verfahren der Durchführung der Quadratwurzel-Funktion dargestellt ist, das in dem Arithmetik-System der vorliegenden Erfindung verwendet wird;
• Fig. 2 ein Flußdiagramm ist, das eine Abwandlung der Newton- Raphson-Abschätztechnik darstellt, die verwendet wird, um den Reziprokwert der Wurzel anzunähern, der in dem Quadratwurzel-System der vorliegenden Erfindung verwendet wird;
• Fig. 3 ein Blockdiagramm des Arithmetik-Systems der vorliegenden Erfindung ist;
• Fig. 4a-4c Beispiele des herkömmlichen Quadratwurzel-Verfahrens sind, bei denen Basis-10-Zahlen verwendet werden; und
• Fig. 5 ein Beispiel des Quadratwurzel-Verfahrens der vorliegenden Erfindung ist, bei dem Basis-10-Zahlen verwendet werden.
DETAILLIERTE BESCHREIBUNG DER ERFINDUNG
• Die Arithmetik-Einheit der vorliegenden Erfindung verwendet ein neues Verfahren zur Durchführung der Quadratwurzel-Funktion. Dieses Verfahren ist in Form eines Flußdiagramms in Fig. 1 gezeigt. Das gezeigte Verfahren ist speziell für den Betrieb in einer Arithmetik-Einheit geeignet, die einen Rechteckseitenverhältnis-Multiplizierer enthält. Die Arithmetik-Einheit der vorliegenden Erfindung kann beispielsweise einen Rechteck-Multiplizierer enthalten, der ein Seitenverhältnis von 19 · 69 Bits hat. Dieser Multiplizierer kann verwendet werden, um die exakte Quadratwurzel von 68-Bit-Zahlen durchzuführen, indem vier 17-Bit-Wurzelzahlen erzeugt werden. Die gewünschte 68-Bit-Hochpräzisions-Partialwurzel mit nicht-negativem Rest ist in dem Verfahren der vorliegenden Erfindung so dargestellt, daß sie vier 17-Bit-Zahlen enthält, die die Großbasis 2¹&sup7; verwenden.
• Das in Fig. 1 gezeigte Verfahren wird verwendet, um die Quadratwurzel eines Operanden y zu berechnen. Der Operand y ist normalisiert, so daß 1/4 &le; y < 1 und der Wert von dessen Exponent eine gerade Zahl ist. Die Quadratwurzel-Funktion erfolgt durch Näherung des Reziprokwertes der Wurzel mit einer Präzision, die kleiner ist als die Präzision des Operanden, um einen gerundeten Reziprokwert R zu erhalten. Wurzelzahlenwerte di werden seriell bestimmt und akkumuliert, um eine Partialwurzel D zu erzeugen. Reste werden erzeugt und in einem Register z abgespeichert. Das Verfahren wird unter Bezugnahme auf einen Matrix- Multiplizierer beschrieben, der ein Seitenverhältnis von 19 · 69 Bits hat. Es ist jedoch offensichtlich, daß das Quadratwurzel- Verfahren der vorliegenden Erfindung für eine große Bandbreite von Rechteckseitenverhältnis-Multiplizierern anwendbar ist. Der spezielle Rechteck-Multiplizierer, der hier beschrieben wird, ist ein Ausführungsbeispiel, das zum Zweck der Erläuterung der vorliegenden Erfindung ausgewählt wurde und nicht dazu dienen soll, den beanspruchten Schutzbereich der vorliegenden Erfindung einzuschränken.
• Unter Bezugnahme auf Fig. 1 beginnt das Verfahren bei Schritt 10, in dem das Rest-Register z mit dem Wert des Operanden y geladen und, das Wurzel-Register auf Null gesetzt wird. Es ist offensichtlich, daß bei dem Verfahren vorausgesetzt wird, daß der Operand eine 68-Bit-Zahl ist, die normalisiert ist, um kleiner als Eins zu sein, und das höchstwertigste Bit des 69-Bit-Rest-Registers z, das das einzige Bit ist, das sich links des Binärbasispunktes befindet, ist zunächst gleich 0. Das Verfahren fährt dann bei Schritt 12 fort, wo der kurze Reziprokwert R der Wurzel mit einer Genauigkeit von (N + k) Bits bestimmt wird. N ist so bestimmt, um der Zahl von Bits in der Großbasis zu entsprechen, die mit den Wurzelzahlen in Beziehung steht. Hier ist N = 17, und k ist eine begrenzte Zahl von Schutzbits, beispielsweise ist hier k = 2. Gemäß dem vorliegenden Ausführungsbeispiel nähert der gerundete Reziprokwert R den exakten Reziprokwert auf eine Genauigkeit von mehr als 18 Bits. Der gerundete Reziprokwert R ist immer größer oder gleich dem wahren Reziprokwert 1/ y, wobei der wahre Reziprokwert größer als Eins und kleiner oder gleich Zwei ist. Der Näherungsschritt 12 verwendet eine Abwandlung der Newton-Raphson- Näherungstechnik, die genauer unter Bezugnahme auf Fig. 2 beschrieben wird.
• Ein erster Wurzelzahlenwert wird in Schritt 14 berechnet, indem der Operand, jetzt im Rest-Register z, mit dem gerundeten Reziprokwert R multipliziert wird, wodurch ein Produkt mit einer Breite von 88 Bits erzeugt wird, mit zumindest einer führenden Null. Das Produkt aus dem gerundeten Reziprokwert und dem Operanden hat dann einen Zahlenfehlereinstellfaktor 81, der dazu addiert wird. Bei einem Ausführungsbeispiel der vorliegenden Erfindung, bei dem ein Multiplizierer mit einem Seitenverhältnis von 19 · 69 Bits verwendet wird, ist &delta;&sub1; gleich 3/8 von einer Einheit relativ zu einer Einheit in der letzten Stelle, auf die der Wurzelzahlenwert trunkiert ist. Die Zahlenfehlereinstellfaktoren &delta;&sub1;, &delta;&sub2;, &delta;&sub3; und &delta;&sub4; sind statisch erzeugte Korrekturfaktoren, die addiert werden, um Fehler auszugleichen, die aus dem Trunkieren des Produkts resultieren, um die vorzeichenbehafteten 17-Bit-Wurzelzahlenwerte zu bilden. Der Zahlenfehlereinstellfaktor &delta;i wird nur dann addiert, um den Wurzelzahlenwert zu bilden, wenn der berechnete Wurzelzahlenwert positiv ist, wobei zu beachten ist, daß die Wurzelzahlenwerte nach dem ersten negativ sein können. Diese Begrenzung beim Addieren von &delta;i erfolgt aufgrund der Tatsache, daß der Zahlentrunkierfehler die Größe reduziert und daher wirkt, um den Wurzelwert für positive Wurzelzahlenwerte zu reduzieren, und wirkt, um den Wurzelwert für negative Wurzelzahlenwerte zu erhöhen. Verschiedene Zahlenfehlereinstellfaktoren werden wahlweise in der ersten Wurzelzahlenwert-Berechnung addiert, im Gegensatz zu den zweiten, dritten und vierten Wurzelzahlenwert-Berechnungen. Bei dem vorliegenden Ausführungsbeispiel sind die Zahlenfehlereinstellfaktoren &delta;&sub2;, &delta;&sub3;, &delta;&sub4; alle gleich 1/2 einer Einheit in der letzten Stelle relativ zum Trunkieren und werden in den zweiten, dritten und vierten Wurzelzahlenwert-Berechnungen nur dann addiert, wenn die resultierenden Wurzelzahlenwerte positiv sind. In Schritt 14 wird die Summe aus dem Produkt des z-Registers, das für Wurzelzahlenwerte nach dem ersten um 1 Stelle nach rechts verschoben ist, und des gerundeten Reziprokwertes und aus dem genäherten Zahlenfehlereinstellfaktor &delta;i dann trunkiert, um einen einzigen vorzeichenbehafteten 17-Bit-Wurzelzahlenwert zu bilden. Der Begriff Zahl wird hier unter Bezugnahme auf die große Basis 2¹&sup7; verwendet und entspricht, nicht hinsichtlich Normalisierung, einem positiven oder negativen Integer-Wert mit einer Größe von 2¹&sup7; - 1 oder weniger. Im Fall eines Rechteckseitenverhältnisses von 19 · 69 Bits sind vier Wurzelzahlenwerte für die komplette 68-Bit-Wurzel von einem 68-Bit-Operanden erforderlich. Daher sind vier Durchläufe durch den Multiplizierer erforderlich, um die vier Wurzelzahlenwerte zu erzeugen. Gemäß dem vorliegenden Ausführungsbeispiel wird die i-te vorzeichenbehaftete 17-Bit- Integer-Zahl genommen, die bestimmt worden ist, um einen Binärbasispunkt 17(i-1) aufzunehmen, der bei der Spezifizierung des entsprechenden Wurzelzahlenwertes zur Linken von dessen am meisten links gelegenen Bit angeordnet ist. Dies entspricht der Tatsache, daß die unendlich präzise Wurzel einen Wert in dem Bereich 1/2 &le; y < 1 haben würde, und so d&sub1; = 0,1 b&sub2; b&sub3; ... b&sub1;&sub7; der erste erzeugte Wurzelzahlenwert und d&sub2; = ± 0,000000 000000 00000 b&sub1;&sub8; b&sub1;&sub9; b&sub2;&sub0; ... b&sub3;&sub4; der zweite erzeugte Wurzelzahlenwert ist.
• Das Verfahren geht weiter zu Schritt 16, wo das Rest-Register z für die Berechnung von dem nächsten Wurzelzahlenwert aktualisiert wird. Der neue z-Registerwert ist gleich der Differenz zwischen dem aktuellen Rest, der aus dem z-Register erhalten wird, und dem Produkt des neuen Wurzelzahlenwertes und einem Betrag, der gleich der Summe der zweifachen Partialwurzel und dem neuen Wurzelzahlenwert ist.
• Das Verfahren fährt dann bei Schritt 18 fort, wo die neue Partialwurzel für i = 1, 2, 3, 4 akkumuliert wird. Auf diese Weise, wie jeder Wurzelzahlenwert bestimmt wird, wird die anfängliche Null-Partialwurzel D auf eine Präzision von 17 weiteren Bits akkumuliert und abgespeichert.
• Das Verfahren kehrt dann zu Schritt 14 zurück, wo der nächste Wurzelzahlenwert erzeugt wird, indem das Produkt von einer Hälfte des neuen Restes und dem gerundeten Reziprokwert genommen, unter Vorbehalt der Zahlenfehlereinstellfaktor addiert und trunkiert wird. Auf diese Weise werden die Wurzelzahlenwerte der Reihe nach zusammen mit zwischenliegenden Partialwurzeln und exakten Resten erzeugt. Am Ende des Prozesses ist der exakte Rest einer Hochpräzisions-Partialwurzel für die weitere Verarbeitung verfügbar. Obwohl Partialwurzel und Restpaar aufgrund der Tatsache, daß der Rest entweder positiv oder negativ sein kann, an diesem Punkt nicht eindeutig ist, kann an diesem Punkt eine präzise Rundung durch eine geeignete bedingte Rundungslogik durchgeführt werden. Gemäß dem hier offenbarten Ausführungsbeispiel wird ein Korrekturschritt durchgeführt, um das Erfordernis einer bedingten Rundungslogik zu vermeiden.
• Bei Verwendung des 19 · 69 Bit Rechteck-Multiplizierers bei einem Ausführungsbeispiel der vorliegenden Erfindung erfordert der Quadratwurzel-Prozeß das Erzeugen von vier Wurzelzahlenwerten, um eine Hochpräzisions-Quadratwurzel-Funktion zu vervollständigen. Jede Wurzelzahl fordert einen kombinierten Multiplikations- und Additionsschritt und einen kombinierten Multiplikations- und Subtraktionsschritt entsprechend Schritt 14 bzw. Schritt 16.
• Ein wichtiger technischer Vorteil des Rechteck-Multiplizierers der vorliegenden Erfindung, der detaillierter unter Bezugnahme auf Fig. 3 diskutiert wird, besteht darin, daß der Multiplizierer außerdem einen zusätzlichen Additions-Anschluß hat. Der zusätzliche Additionsanschluß ermöglicht es, einige Multiplikations- und Additionsschritte in einem Durchlauf durch den Rechteck-Multiplizierer durchzuführen. Folglich können die Operation, die in Schritt 16 gezeigt ist, die ein 17 · 69 Bit- Produkt und eine Differenz umfaßt, ebenso wie die Operationen, die in Schritt 14 gezeigt sind, die einige 19 · 69 oder einige 20 · 69 Bit-Produkte mit Addition einer vorbestimmten Konstanten umfassen, in einem einzigen Durchlauf durch den Rechteck-Multiplizierer erreicht werden.
• Das Partialwurzel- und Restpaar kann eindeutig gemacht werden, indem die Partialwurzel und der Rest durch eine Korrektursequenz geführt werden, die durch Schritt 20 in Fig. 1 dargestellt ist. Wegen der Schritte, die bei der Abschätzung des Reziprokwertes in Schritt 12 durchgeführt werden, ist die Korrektursequenz selbst sehr einfach. In diesem Ausführungsbeispiel muß der endgültige Rest kleiner sein als ein positiver Wert, der gleich dem Produkt aus 2&supmin;&sup6;&sup8; und der doppelten endgültigen Partialwurzel ist, plus Einheit in der letzten Stelle, und größer sein als ein negativer Wert, der gleich dem Produkt aus -2&supmin;&sup6;&sup8; und der zweifachen endgültigen Partialwurzel ist, minus Einheit in der letzten Stelle. Wenn der Rest negativ ist, dann umfaßt die erneute Berechnung des Restes das Addieren eines passend verschobenen Wertes zu dem Rest, der gleich der doppelten endgültigen Partialwurzel ist, minus eine Einheit in der letzten Stelle. Die endgültige Partialwurzel wird dann um eine Einheit in der letzten Stelle dekrementiert. Diese einfache Korrektursequenz ist möglich, da die Annäherung des Reziprokwertes, der in Schritt 12 erzeugt wurde, auf eine solche Weise erzeugt wird, daß der gerundete Reziprokwert, wenn er mit dem Rest multipliziert wird, Wurzelzahlenwerte erzeugt, die immer entweder dem genauen trunkierten Wert für den Wurzelzahlenwert oder eine Einheit zu groß in der letzten Stelle des Wurzelzahlenwertes sind, wenn trunkiert. Da die Näherung sorgsam auf diese beiden möglichen Ergebnisse beschränkt ist, wird die exakte Quadratwurzel-Funktion durchgeführt, da die resultierende Partialwurzel und der Rest von einer Quadratwurzel-Operation so ist, daß die einfache Korrektursequenz, die oben beschrieben wurde, zu einer eindeutigen Hochpräzisions-Partialwurzel mit einem nicht-negativen Rest führt. Es sei angemerkt, daß es eine Vereinfachung dieser Lehre ist, daß angenommen wird, daß ein Nicht-Null-Rest auf einen positiven Wert korrigiert werden muß, um eine eindeutige Wurzel zu erzeugen. Eine eindeutige Wurzel kann auch erzeugt werden, indem ständig ein negativer Rest erzwungen wird. Jede eindeutige Partialwurzel- und Restpaar kann als das Ergebnis der exakten Quadratwurzel-Funktion betrachtet werden.
• Eine neue Version der Newton-Raphson-Abschätztechnik, die verwendet wird, um den obengenannten gerundeten Reziprokwertbetrag zu berechnen, ist in Form eines Flußdiagramms in Fig. 2 dargestellt. Das Verfahren beginnt bei Schritt 22, wo eine Verweistabelle verwendet wird, um einen reziproken Startwert y' zu finden, der näherungsweise gleich dem Reziprokwert der Quadrat wurzel des Operanden y ist. Es soll verstanden werden, daß das Verfahren voraussetzt, daß der reziproke Startwert y' in ein typisches Gleitkommaformat normalisiert ist, so daß y' größer oder gleich eins und kleiner als zwei ist, und y' eine Anzahl von Bits hat, die kleiner oder gleich der kleineren Dimension des Rechteckseitenverhältnis-Multiplizierers ist. Wie oben erläutert, kann die Verweistabelle infolge der Beschränkung der Größe der Tabelle lediglich eine kleine Zahl von Bits erreichen. y' wird daher als ein Startwert verwendet, und die Zahl der genauen Bits bei der Näherung wird durch einen iterativen Prozeß erhöht. In dem vorliegenden Ausführungsbeispiel ist der Startwert y' so gewählt, daß er eine ausreichende Genauigkeit hat, um vor der Addition des reziproken Fehlereinstellfaktors einen angenäherten Reziprokwert mit einem Fehler von weniger als 2&supmin;²² zu erzeugen.
• Das Verfahren geht zu Schritt 24 weiter, wo der erste Schritt des iterativen Prozesses verwendet wird, um y" zu berechnen. y" wird berechnet, indem ein erstes Ergebnis als das Produkt aus y und y' berechnet wird. Das erste Ergebnis wird dann auf 69 Bits trunkiert und mit y'/2 multipliziert und von 3/2 subtrahiert, um ein zweites Ergebnis zu bilden. Das zweite Ergebnis wird auf 69 Bits trunkiert und mit y' multipliziert, um ein drittes Ergebnis zu bilden. Das dritte Ergebnis wird auf 69 Bits trunkiert, um den Wert für y" zu erhalten. Das Verfahren geht dann bei Schritt 26 weiter, wo die Berechnung eines angenäherten Reziprokwertbetrages y''' auf ähnliche Weise durch eine zusätzliche Iteration der Newton-Raphson-Näherungsgleichung berechnet wird, wie gezeigt ist, wobei für y" der zuvor berechnete Wert von y" verwendet wird, trunkiert auf 17 Bits zur Verwendung in der kürzeren Seite des Multiplizierers. Es soll verstanden werden, daß y' oder y" als der angenäherte Reziprokwertbetrag verwendet werden kann, wenn ein Multiplizierer mit unterschiedlicher Größe in einem anderen Ausführungsbeispiel der Erfindung verwendet werden würde, was eine kleinere Zahl von genauen Bits in dem gerundeten Reziprokwert R erfordert. Das verfahren umfaßt Schritt 28, wo der endgültige Betrag des gerundeten Reziprokwertes erhalten wird, indem der Betrag des angenäherten Reziprokwertbetrages y''' zu dem reziproken Fehlereinstellfaktor Epsilon addiert und das Ergebnis geeignet trunkiert wird. Epsilon ist eine statisch erzeugte Größe, die von der Basis der Wurzelzahlenwerte abhängig ist. Epsilon ist gleich der Summe aus zwei Termen. Der erste Term ist gleich 2-(N+k-1), wobei wie vorstehend diskutiert, N gleich der Zahl von Bits der Basis der Wurzelzahlenwerte und k eine vorbestimmte Zahl von Schutzbits ist. Der zweite Term ist groß genug bestimmt, um das Ergebnis der Newton-Raphson-Näherung so zu beeinflussen, um größer zu sein als der wirkliche Reziprokwert. Gleichwohl muß der zweite Term außerdem ausreichend klein sein, so daß die Bestimmung von einem Wurzelzahlenwert in 14 zu einem Rest führt, der kleiner ist als eine Einheit in der letzten Stelle des bestimmten Wurzelzahlenwertes. Für ein Ausführungsbeispiel der vorliegenden Erfindung, bei dem eine Multiplizierer-Matrix mit einem Seitenverhältnis von 19 · 69-Bits verwendet wird, ist Epsilon gleich siebzehnvierundsechzigstel von einer Einheit in der N-ten Stelle des angenäherten Reziprokwertes, der im vorliegenden Ausführungsbeispiel mit N = 17, k = 2, 1 &le; y''' < 2 gleich 2&supmin;¹&sup8; + 2&supmin;²² ist. Der gerundete Reziprokwert R, der durch Trunkieren erhalten wird, ist entweder ein 19-Bit-Wert in dem Bereich 1 < R < 2 oder ein 20-Bit-Wert, der durch R = 10.00... 0b&sub1;&sub8; gegeben ist, der dann in dem in Fig. 1 dargestellten Verfahren verwendet werden kann, um zu einer Partialwurzel und zu einem Rest zu führen, der in der Lage ist, zu einem eindeutigen exakten Ergebnis zu führen, und zwar durch die einfache Korrekturtechnik, die vorstehend unter Bezugnahme auf Schritt 20 in Fig. 1 diskutiert wurde.
• Jede Iteration der Newton-Raphson-Gleichung kann lediglich drei Durchläufe durch einen Rechteckseitenverhältnis-Multiplizierer erfordern, wenn der Multiplizierer einen zusätzlichen Addierer-Anschluß hat. Der erste Durchlauf bildet das Produkt y · y'. Der zweite Schritt bildet das Produkt und die Differenz (3/2) - (y'/2) · (y · y'), Der dritte Durchlauf vervollständigt die Iteration durch Bilden von y' · {(3/2) - (y'/2) · (y · y')}. Wie vorstehend diskutiert, kann der zweite Term (3/2) - (y'/2) · (y · y') wegen des Beinhaltens von einem zusätzlichen Addierer-Anschluß in einem einzigen Durchlauf durch den Rechteck-Multiplizierer berechnet werden. Die Ergebnisse dieser aufeinanderfolgenden Multiplikationen können jeweils auf die Länge der langen Seite des Rechteck-Multiplizierers trunkiert werden, wenn lediglich eine Näherung des Reziprokwertes genau auf einen Fehler von weniger als ein Teil in 223 erforderlich ist.
• Es soll verstanden werden, daß das Verfahren zur Durchführung der Quadratwurzel-Funktion der vorliegenden Erfindung nicht von dem bestimmten Verfahren abhängt, das zur Berechnung des gerundeten Reziprokwertes R verwendet wird. Die zuvor beschriebene Abwandlung des Newton-Raphson-Prozesses ist lediglich ein mögliches Verfahren zum Erzeugen dieses Wertes. Zum Beispiel wäre eine Version der Newton-Raphson-Näherungstechnik, bei der eine einzige Iteration oder mehr als zwei Iterationen verwendet wird, um den angenäherten Reziprokwert zu erzeugen, in einem System geeignet, das einen Multiplizierer verwendet, der einen gerundeten Reziprokwert benötigt, der weniger oder mehr Bits an Genauigkeit hat als das hier beschriebene Ausführungsbeispiel. Außerdem, wenn ein Ausführungsbeispiel der vorliegenden Erfindung eine kleinere Zahl von Genauigkeits-Bits in dem gerundeten Reziprokwert benötigt, dann wäre eine direkte Tabellensuche von entweder dem angenäherten Reziprokwert vor der Addition des reziproken Fehlereinstellfaktors oder eine direkte Tabellensuche des gerundeten Reziprokwertes praktisch, der bereits den Fehlereinstellfaktor enthält.
• Fig. 3 ist ein Blockdiagramm eines Schaltungs-Ausführungsbeispiels, das in der Lage ist, das Verfahren zur Durchführung der Quadratwurzel-Funktion der vorliegenden Erfindung durchzuführen. Unter Bezugnahme auf Fig. 3 verwendet eine Schaltung, die allgemein mit 30 bezeichnet ist, einen Systembus 32 zur Kommunikation zwischen einem Mikroprozessor [nicht gezeigt] und einem Arithmetik-Koprozessor, der die Schaltung 30 enthält. Ein Systembus 32 kann beispielsweise Datenleitungen, Adressleitungen und Steuerleitungen von dem Mikroprozessor enthalten. Mit dem Systembus 32 sind ein D-Speicher 34, ein Zahlen-Speicher 36, ein Reziprokwert-Speicher 33 und ein E-Speicher 38 gekoppelt. Allgemein empfangen der D-Speicher 34, der Reziprokwert-Speicher 33 und der Zahlen-Speicher 36 Operanden von dem Mikroprozessor und speichern die Operanden ab, die in einer Arithmetik-Operation verwendet werden, und der E-Speicher 38 dient dazu, die Ausgabe der Operation zu speichern.
• Der Reziprokwert-Speicher 33 empfängt neunzehn Bits von dem Systembus 32 und gibt achtzehn Bits geringer Ordnung an einen Multiplexer 44 aus. Das führende Bit wird an einen Schieber 52 ausgegeben, der zwischen dem Rückführregister 54 und dem Eingang zu dem Addierer 48 gekoppelt ist. Der Zahlen-Speicher 36 empfängt siebzehn Bits von dem Systembus 32 und gibt die siebzehn Bits an den Multiplexer 44 und an den Multiplexer 35 aus. Der Ausgang des Multiplexers 35 ist durch drei separate Datenpfade mit einem Addierer 37 gekoppelt. Der D-Speicher 34 empfängt neunundsechzig Bits von dem Systembus 32 und gibt die neunundsechzig Bits an den Addierer 37 aus. Die Ausgabe des Addierers 37 wird einem Multiplexer 40 zugeführt.
• Aktionen, die für die Vorzeichen der beteiligten Beträge wichtig sind, werden entweder von der Hintergrundsteuerung gehandhabt oder indem alle Bits als vorzeichenbehaftete Bits von einer redundanten Binärimplementierung genommen werden.
• Der Multiplexer 35 kann betrieben werden, um eine Zahl, die in dem Zahlen-Speicher 36 gespeichert ist, in den Addierer 37 einzugeben, so daß die Zahl geeignet in drei separate Gruppen von Bit-Positionen ausgerichtet werden kann. Der verbleibende Eingang zum Multiplexer 40 ist mit der Ausgabe des Rückführ- Registers 54 gekoppelt, und der Ausgang von dem Multiplexer 40 wird der langen Seite der Multiplizierer-Matrix 42 zugeführt.
• Die Multiplizierer-Matrix 42 enthält einen Baum mit drei Addierer-Matrizen. Um eine kurz-mal-lang-Multiplikation unter Verwendung der Arithmetik-Schaltung 30 zu vervollständigen, wird der Multiplikand in den D-Speicher 34 geladen, und der Multiplikator wird in den Zahlen-Speichen 36 oder Reziprokwert-Speicher geladen. Der Multiplikator enthält den "kurzen" Operanden mit 18 Bits. Der Multiplikand enthält den "langen" Operanden mit 69 Bits. Der Multiplikand durchläuft den ersten Multiplexer 40 und wird der Multiplizierer-Matrix 42 zugeführt. Die 18 Bits des Multiplikators werden von dem zweiten Multiplexer 44 in die kurze Seite der Multiplizierer-Matrix 42 geleitet. Die Ausgabe von der Multiplizierer-Matrix ist 87 Bits breit und bildet eine Eingabe in einen ersten Addierer 46. Um die kurz-mal-lang-Multiplikation bis über die 18 Bit hinaus zu erweitern, dient der zweite Anschluß des ersten Addierers 46 als der zusätzliche Addierer-Anschluß des Multiplizierers, der zuvor beschrieben wurde. Der zweite Anschluß des ersten Addierers 46 ist mit der Ausgabe von einem zweiten Addierer 48 gekoppelt, der an seinen Eingängen einen konstanten Anschluß 50 und die Ausgabe des Rückführ-Registers 54 hat. Neunundsechzig Bits der Ausgabe von dem Rückführ-Register 54 sind außerdem mit einem zweiten Eingangsanschluß des ersten Multiplexers 40 gekoppelt, wodurch ein 18 · 69-Bit-Produkt des Rückführ-Registers 54 ermöglicht wird, wobei der zweite Multiplexer 44 unter Vorbehalt wieder mit dem Inhalt des Rückführ-Registers 54 summiert wird, der durch den Schieber 52 geführt wird, was zu einem 19 · 69-Bit-Gesamtprodukt am Ausgang des ersten Addierers 46 führt.
• Wenn die Quadratwurzel des Operanden gleich oder etwa ein halb beträgt, dann wird der gerundete Reziprokwert gleich oder etwas größer als zwei sein. Das führt dazu, daß der gerundete 19-Bit-Reziprokwert in unserer Normalisierung überläuft, was zu einer 0 in der höchstwertigsten Bitposition führt. Dieser Zustand wird durch Überwachung des höchstwertigsten Bits erfaßt und bewirkt, daß der Schieber 52 um Eins nach links schiebt, was zur Folge hat, daß der doppelte Inhalt des Rückführ-Registers 54 addiert wird, um diese bestimmten 20 · 69 Bit-Multiplikationen korrekt zu handhaben.
• Ein wichtiger technischer Vorteil des Addierers 46 besteht in seiner Fähigkeit, einen Überlauf und eine Sättigung der resultierenden Summe zu erfassen. Während der Berechnung der Wurzelzahlenwerte können das Produkt eines gerundeten Reziprokwertes und der Rest ein Überlaufen erzeugen, wodurch eine Zahl mit einer Größe von mehr als 2¹&sup7;-1 angezeigt wird. Daher kann die Sättigungs-Eigenschaft des Addierers 46 verwendet werden, um eine maximale Summe zu schaffen, die einer 1 an allen 86 Ausgangsbits zu der Rechten von dem implementierten Binärbasispunkt des Addierers 46 entspricht, was einem Zahlenwert von 2¹&sup7; - 1 entspricht.
• Die Ausgabe des ersten Addierers 46 ist mit dem Eingang von einem ersten Schieber 55 gekoppelt. Der erste Schieber 55 dient dazu, die Ausgabe von dem ersten Addierer 46 um eine Stelle nach rechts oder links zu schieben. Diese Verschiebung wird verwendet, um die maximale Anzahl von signifikanten Datenbits, die auf dem Datenpfad strömen, zu halten, und zur Ausrichtung, um den Rest mit Einhalb zu multiplizieren, was unter Bezugnahme auf Schritt 14 in Fig. 1 diskutiert wurde.
• Die Ausgabe des ersten Schiebers 55 wird in ein Ergebnis- Register 56 eingegeben. Die Ausgabe des Ergebnis-Registers 56 wird zu zwei separaten Orten geführt. Die Ausgabe wird zunächst in einen zweiten Schieber 58 geleitet, der zwischen dem Ergebnis-Register 56 und dem Eingang zu dem Rückführ-Register 54 gekoppelt ist, von dem es danach für weitere Berechnungen zur Multiplizierer-Matrix 42 oder zu Addierern 48 oder 46 geleitet werden kann. Der Schieber 58 wird verwendet, um Werte auf dem Datenpfad um 17 Bits nach links zu schieben. Der Schieber 58 wird verwendet, um noch einmal so viele signifikante Datenbits wie möglich auf dem Datenpfad zu halten, indem Bits, deren Wert bekannt ist, herausgeschoben werden. Wegen der Eigenschaften des Verfahrens der vorliegenden Erfindung sind die ersten 17 Bits des Ergebnisses des Subtraktionsschrittes, durch den der nachfolgende Rest erzeugt wird, immer 0. Dies ist wegen der Tatsache, daß die Anfangsbits der Operanden dieses Subtraktionsschrittes immer abgeschnitten werden. Diese 0-Bits werden daher nach links herausgeschoben, um zu ermöglichen, daß 17 zusätzliche signifikante Datenbits auf den Datenpfad bleiben.
• Die Ausgabe des Ergebnis-Registers 56 wird in den E-Speicher 38 eingegeben, der, wie vorstehend beschrieben wurde, mit dem Systembus 32 gekoppelt ist. Der Systembus 32 ist ebenfalls mit einer Akkumulator-Schaltung gekoppelt, die allgemein mit 70 bezeichnet ist. Der Akkumulator 70 enthält einen Addierer 72, wobei einer von dessen Anschlüssen mit dem Systembus 32 gekoppelt ist. Der verbleibende Anschluß des Addierers 72 ist mit einem Schieber 74 gekoppelt. Die Ausgabe des Addierers 72 wird in ein Wurzel-Register 76 eingegeben, das ebenfalls mit dem Eingang des Schiebers 74 gekoppelt ist. Die Ausgabe des Wurzel- Registers 76 ist außerdem mit dem Systembus 32 gekoppelt. Diese Verbindung schafft einen Datenpfad, über den die Partialwurzel zu dem D-Speicher 34 für die Berechnung des nachfolgenden Restes zurückgeführt werden kann, wie unter Bezugnahme auf Schritt 16 diskutiert wurde, der in Fig. 1 gezeigt ist.
• Wie vorstehend beschrieben, ist die Basisoperation, die verwendet wird, um das neue Quadratwurzel-Verfahren der vorliegenden Erfindung durchzuführen, die Multiplikations-Operation. Es ist jedoch wichtig, zwischen verschiedenen Typen von Multiplikations-Operationen zu unterscheiden. Bei Verfahren gemäß Stand der Technik zur Durchführung von Quadratwurzel-Funktionen wurde eine Ganzlängen-, Hochpräzisions-Näherung des Reziprokwertes der Wurzel berechnet und dann eine Hochpräzisions-, "lang-mal-lang"-Multiplikation durchgeführt. Eine zusätzliche Hochpräzisions-Multiplikation wurde dann verwendet, um das Ergebnis zu korrigieren. Das Quadratwurzel-Verfahren der vorliegenden Erfindung benötigt keine Hochpräzisions-Multiplikationen. Die Multiplikations-Operationen, die für das vorliegende Verfahren erforderlich sind, sind sehr viel einfachere und schnellere "kurz-mal-lang"-Multiplikationen.
• Das Verfahren zur Durchführung der exakten Quadratwurzel- Funktion der vorliegenden Erfindung wird vielleicht am besten verstanden, wenn es in Verbindung mit dem herkömmlichen unabgekürzten Quadratwurzel-Verfahren untersucht wird. Die beiden Verfahren können am einfachsten verglichen werden, wenn Beispiele verwendet werden, bei denen die Quadratwurzeln mit der etwas vertrauteren Basis 10 berechnet werden.
• Fig. 4a zeigt in tabellarischer Form die Schritte, die erforderlich sind, um das herkömmliche unabgekürzte Quadratwurzel-Verfahren durchzuführen. Fig. 4b zeigt das unabgekürzte Verfahren, das verwendet wird, um die Quadratwurzel von Zwei zu berechnen, und Fig. 4c zeigt das unabgekürzte Verfahren, das verwendet wird, um die Quadratwurzel von 20 zu berechnen. Beide Beispiele werden mit der Basis 10 berechnet.
• Unter Bezugnahme auf Fig. 4a umfaßt Schritt 1 das Gruppieren der Argumente in Zahlenpaare. An diesem Punkt muß angemerkt werden, daß der Dezimalpunkt nicht innerhalb eines Zahlenpaares stehen darf. Man muß erkennen, daß der Exponent des Argumentes respektiert werden muß. Dies kann in dem nachfolgenden Beispiel dadurch gesehen werden, daß die Quadratwurzel von Zwei nicht die gleichen signifikanten Zahlen wie die Quadratwurzel von 20 enthält. In Schritt 2 wird die erste Zahl der Wurzel erzeugt, indem das größte vollständige Quadrat aufgerufen wird, das kleiner oder gleich dem ersten Zahlenpaar ist, und die Wurzel von diesem vollständigen Quadrat als die erste Zahl verwendet wird. In dem gezeigten Beispiel ist das größte vollständige Quadrat, das kleiner oder gleich Zwei ist, gleich Eins, und daher ist die erste Wurzelzahl der Quadratwurzel von Zwei gleich Eins. Das größte vollständige Quadrat, das kleiner als 20 ist, ist 16, und daher ist die erste Zahl der Wurzel von 20 gleich Vier.
• In Schritt 3 wird der Rest als die Differenz zwischen dem ersten Zahlenpaar und der ersten quadrierten Wurzelzahl berechnet. In Schritt 4 wird das nächste Zahlenpaar heruntergeholt, um den neuen Rest zu bilden. Es ist ein Merkmal des unabgekürzten Quadratwurzel-Verfahrens, daß sowohl der Rest als auch der neue Rest durch diese begrenzte Anzahl von Zahlen definiert ist, wobei nachfolgende Zahlen des ursprünglichen Operanden mit einer Geschwindigkeit von einem neuen Zahlenpaar pro Zyklus in die Berechnung eingebracht werden. Bei der Quadratwurzel von zum Beispiel Zwei ist der neue Rest gleich 100, und bei der Quadratwurzel von zum Beispiel 20 ist der neue Rest gleich 400, wie gezeigt ist. In Schritt 5a wird ein Versuchsdivisor berechnet, der gleich zweimal der Basis mal der Partialwurzel ist. Bei der Quadratwurzel von zum Beispiel Zwei ist der erste Versuchsdivisor gleich 20. Bei der Quadratwurzel von zum Beispiel 20 ist der erste Versuchsdivisor gleich 80.
• In Schritt 5b wird die nächste Wurzelzahl berechnet, indem der neue Nicht-Null-Rest durch den Versuchsdivisor dividiert wird, der Quotient abgerundet und Eins subtrahiert wird. Wenn der neue Rest gleich null ist, dann wird die nächste Wurzelzahl auf Null gesetzt. In beiden Beispielen, nämlich der Quadratwurzel von Zwei und der Quadratwurzel von 20, wird die nächste Wurzelzahl als Vier berechnet, was zu einer Partialwurzel von 1,4 bei 2 und 4,4 bei 20 führt, wie gezeigt ist. In Schritt 6 wird der nächste Rest berechnet. Der nächste Rest ist gleich dem Produkt aus der nächsten Wurzelzahl und der Summe aus dem Versuchsdivisor und der nächsten Wurzelzahl. Bei der Quadratwurzel von zum Beispiel Zwei wird der nächste Rest berechnet, um gleich Vier zu sein. Bei der Quadratwurzel von zum Beispiel 20 wird der nächste Rest berechnet, um 64 zu sein. An dieser Stelle kann der nächste Rest negativ sein. Es ist ein Merkmal der unabgekürzten Quadratwurzel, daß die Berechnung von Schritt 5b nicht immer die geeignete nächste Zahl erkennt. In diesem Fall wird die aktuelle Abschätzung der nächsten Zahl um Eins dekrementiert, und Schritt 6 wird wiederholt.
• Das Verfahren kehrt dann zu Schritt 4 zurück, wo das nächste Zahlenpaar heruntergeholt wird, um den neuen Rest zu bilden. Das unabgekürzte Verfahren kann dann unendlich fortgesetzt werden, um so viele Zahlen der Quadratwurzel zu erzeugen, wie gewünscht ist. Aus den in Fig. 4a dargestellten Beispielen kann gesehen werden, daß das herkömmliche unabgekürzte Quadratwurzel- Verfahren eine große Anzahl von komplexen arithmetischen Operationen erfordert, um jede Zahl der Wurzel zu erzeugen. Die iterativen Schritte, die zum Erzeugen von jeder Wurzelzahl erforderlich sind, benötigen Arithmetik-Prozessor-Zeit für zumindest eine Multiplikations-Operation, eine Divisions-Operation und eine Anzahl von zusätzlichen Verschiebe- und Additions-Operationen.
• In Fig. 4b wird das herkömmliche unabgekürzte Quadratwurzel-Verfahren verwendet, um die Quadratwurzel von Zwei zu berechnen. In der linksseitigen Spalte ist die Summation von dem Zweifachen der vorhergehenden Zahlen plus der letzten zu berechnenden Zahl (unterstrichen) gezeigt. Dieser Term zusammen mit der nun zu bestimmenden letzten Zahl (unterstrichen), die als Null genommen wird, bildet den Versuchsdivisor, der unter Bezugnahme auf Schritt 5 in Fig. 4a diskutiert wurde. Die Tatsache, daß die Division in Schritt 5b durchgeführt werden muß, bevor die letzte Zahl zu dem Versuchsdivisor addiert werden kann, erklärt, warum ein negativer Rest in Schritt 6 auftreten kann und das Dekrementieren der Wurzelzahl und die Neuberechnung in Schritt 6 erzwingt.
• Fig. 4c zeigt das herkömmliche unabgekürzte Quadratwurzel- Verfahren, das verwendet wird, um die Quadratwurzel von 20 als eine Teilwurzel mit 9 Zahlen Genauigkeit und mit positivem Rest zu berechnen.
• Ein Basis-10-Beispiel des Verfahrens zur Durchführung der exakten Quadratwurzel-Funktion gemäß der vorliegenden Erfindung ist in Fig. 5 gezeigt. Fig. 5 zeigt die Berechnung der Quadratwurzel von 0,02 unter Verwendung des Verfahrens, das durch das in Fig. 1 gezeigte Flußdiagramm dargestellt ist. Das in Fig. 5 gezeigte Beispiel verwendet Großbasis-Zahlen (large radix digits) der Basis 100. Die Großbasis-Zahlen des Operanden werden ihrerseits in Zahlenpaare gruppiert, wobei jede Gruppe dann vier Dezimalstellen hat. Zunächst ist der Reziprokwert der Quadratwurzel von Zwei ungefähr gleich 7,08. Dies entspricht der Berechnung des gerundeten Reziprokwertes, wie vorstehend diskutiert. Die erste Zahl der Wurzel wird berechnet, indem der Operand 2 mit 7,08 multipliziert wird, was zu 0,1416 führt, dann wird der kleine Zahlenfehlereinstellfaktor addiert, und ein Trunkieren führt zu 0,14 als der erste Wurzelzahlenwert. Dieser erste Wurzelzahlenwert wird quadriert und von dem anfänglichen Operanden subtrahiert, um zu dem neuen Rest 0,0004 zu führen. Die nachfolgenden Reste in Fig. 5 sind mit einem Basispunkt gezeigt, der zwei zusätzlichen führenden Nullen entspricht, die in jedem Zyklus entfernt sind, um darzustellen, wie die Reste erscheinen, wenn sie in dem z-Register nach links geschoben werden, um mehr Zahlen auf dem Datenpfad zu halten, wie unter Bezugnahme auf den Schieber 58 in Fig. 3 diskutiert wurde. Eine Hälfte dieses Restes wird dann mit dem gerundeten Reziprokwert multipliziert, der Zahlenfehlereinstellfaktor wird addiert, wobei ein Trunkieren dann zu dem nächsten Wurzelzahlenwert von gleich 0,0014 führt. Dieser Wurzelzahlenwert wird dann zu dem Zweifachen der vorhergehenden Partialwurzel addiert, um zu der Summe von 0,2814 zu führen. Der Wurzelzahlenwert 0,0014 wird dann mit der Summe 0,2814 multipliziert, um zu 0,00039396 zu führen. Dieses Produkt wird dann von dem vorhergehenden Rest subtrahiert, um zu dem nächsten Rest von gleich 0,00000604 zu führen. Dieser Prozeß fährt fort für die Erzeugung der letzten beiden Wurzelzahlenwerte von gleich 0,000021 bzw. 0,00000036. Der Prozeß endet mit der Partialwurzel 0,14142136 und dem entsprechenden negativen Rest von - 0,0000000010642496. Der negative Rest wird durch einen Schritt, der in Fig. 5 nicht dargestellt ist, positiv gemacht, indem ein Wert addiert wird, der durch das 10&supmin;&sup8; -fache der Summe der zweifachen Partialwurzel minus Einheit in der letzten Stelle gegeben ist, was zu einem endgültigen Rest von 0,0000000017641775 führt, was der dekrementierten endgültigen Partialwurzel 0,14142135 entspricht.
• Das Verfahren in Fig. 5 zeigt, daß durch Verwendung eines einzigen kurz-mal-lang-Multiplikationsschrittes jeder der Wurzelzahlenwerte seriell erzeugt und die entsprechenden neuen exakten Reste bestimmt werden. Das Verfahren erfordert die Akkumulation von dem Zweifachen der vorhergehenden Partialwurzel plus dem neuen Wurzelzahlenwert als Multiplikand. Der gerundete Reziprokwert wird so berechnet, daß der Rest, der auf die Berechnung von jedem Wurzelzahlenwert folgt, einem Wert entspricht, der kleiner als eine Einheit in der letzten Stelle des vorhergehenden Wurzelzahlenwertes ist.
• Das Verfahren, das durch das Basis-10-Beispiel dargestellt ist, wie in Fig. 5 gezeigt, ist direkt anwendbar auf die in Fig. 3 gezeigte Schaltung, wobei der einzige Unterschied darin besteht, daß die in Fig. 3 gezeigte Schaltung Operanden im binären, vorzeichenbehafteten Zahlenformat verwendet. Außerdem ist die Zahlenlänge der Wurzelzahlen, die durch die in Fig. 3 gezeigte Schaltung erzeugt werden, siebzehn Bits lang. Dies entspricht einer Basis von 2¹&sup7; = 131072.
• Um das Quadratwurzel-Verfahren der vorliegenden Erfindung unter Verwendung der Schaltung 30 durchzuführen, wird die Näherung des Reziprokwertes erzeugt, wie vorstehend erläutert, und in dem Reziprokwert-Speicher 33 gespeichert. Der Operand wird in das Rückführ-Register 54 geladen, indem er unverändert von dem Systembus 32 durch die Schaltung 30 geführt wird. Das Rückführ- Register 54 wirkt somit als das z-Register, auf das unter Bezugnahme auf Fig. 1 Bezug genommen wurde.
• Um den ersten Wurzelzahlenwert zu erzeugen, wird der Operand durch den Multiplexer 40 aus dem Rückführ-Register 54 ausgewählt und mit dem gerundeten Reziprokwert multipliziert. Die 18 Bits niedriger Ordnung des gerundeten Reziprokwertes werden durch einen Multiplexer 44 in die Multiplizierer-Matrix 42 geladen, wobei das Produkt in einen Anschluß des Addierers 46 eingegeben wird. Der Operand wird außerdem zu dem Schieber 52 geführt, um eine Multiplikation mit dem führenden Bit des gerundeten Reziprokwertes zu ermöglichen, wodurch ein Ergebnis an einem Eingangsanschluß des Addierers 48 erzeugt wird. Der andere Eingangsanschluß des Addierers 48 empfängt den Zahlenfehlereinstellfaktor &delta;&sub1; von dem konstanten Anschluß 50. Die Summe, die von dem Addierer 48 ausgegeben wird, wird zu dem Produkt von dem Multiplizierer 42 in dem Addierer 46 addiert, der das Ergebnis zu dem Schieber 55 ausgibt. Die siebzehn höchstwertigsten Bits des Ergebnisses bilden den ersten Wurzelzahlenwert. Der erste Wurzelzahlenwert wird dann in den Zahlen-Speicher 36 und den D-Speicher 34 geladen. Der Wurzelzahlenwert wird ebenfalls durch den Addierer 72 in das Wurzel-Register 76 geladen.
• Der erste Rest wird berechnet, indem zuerst der erste Wurzelzahlenwert quadriert wird. Dies wird erreicht, indem der erste Wurzelzahlenwert in die lange Seite der Multiplizierer- Matrix 42 geladen wird. Dieses Laden wird erreicht, indem der erste Wurzelzahlenwert aus dem D-Speicher 34 durch Addierer 37 und Multiplexer 40 geführt wird. Der Multiplexer 35 gibt eine Null in den Addierer 37 aus, so daß der erste Wurzelzahlenwert unverändert bleibt, wenn er durch den Addierer 37 geführt wird. Der erste Wurzelzahlenwert wird außerdem vom Zahlen-Speicher 36 durch den Multiplexer 44 in die kurze Seite der Multiplizierer- Matrix 42 geladen. Die Multiplizierer-Matrix 42 führt dann das Quadrieren des ersten Wurzelzahlenwertes durch. Der Operand wird von dem Rückführ-Register 54 durch den zweiten Addierer 48 in den ersten Addierer 46 geleitet, wo das Quadrat des ersten Wurzelzahlenwertes subtrahiert wird. Die Differenz, die von dem ersten Addierer 46 ausgegeben wird, wird in dem Schieber 55 um eine Stelle nach rechts geschoben und zum Ergebnis-Register 56 geleitet und bildet eine Hälfte des neuen Restes, der dann in dem dritten Schieber 58 um 17 Bits nach links geschoben wird. Wie oben beschrieben, sind die ersten siebzehn Bits des Restes alle Null, was aus der Tatsache resultiert, daß die Anfangsbits der Operanden der Subtraktionsoperation abgeschnitten sind. Der verschobene Rest wird dann in das Rückführ-Register 54 geladen, um die Berechnung des nächsten Wurzelzahlenwertes zu ermöglichen. Der aktuelle Wert, der in das Register 54 geladen ist, ist aufgrund von dessen Ausrichtung durch den Schieber 55 in Vorbereitung für die nächste Wurzelzahlenwert-Berechnung in Schritt 14 gleich einer Hälfte des Restes. Das Ergebnis von dem Wurzel-Register 76 wird nun zu dem D-Speicher 34 geleitet, der mit einem Bit ausgerichtet ist, um einen Wert zu schaffen, der gleich dem Zweifachen der Partialwurzel ist, um zur Berechnung des neuen Restes bei der nachfolgenden Iteration in Schritt 16 für den Addierer 37 verfügbar zu sein.
• Jeder nachfolgende Wurzelzahlenwert wird berechnet, indem der gerundete Reziprokwert, der durch den Multiplexer 44 in die Multiplizierer-Matrix 42 geladen ist, wobei das führende Bit des gerundeten Reziprokwertes in den Schieber 52 eingegeben ist, mit einer Hälfte des Restes multipliziert wird, der in dem Rückführ- Register 54 enthalten ist, und in den Schieber 52 und durch den Multiplexer 40 in die lange Seite der Multiplizierer-Matrix 42 geladen wird. Die Zahlenfehlereinstellfaktoren &delta;&sub2;, &delta;&sub3; und &delta;&sub4; werden von dem konstanten Anschluß 50 eingegeben und unter Vorbehalt zu dem führenden Teil des Produktes in dem Addierer 48 addiert, wobei das Ergebnis dann zu der Ausgabe von dem Multiplizierer 42 in dem Addierer 46 addiert wird.
• Insbesondere für die zweite Wurzelzahlenwert-Berechnung ist &delta;&sub2; gleich einer halben Einheit in der letzten Stelle, auf die das Ergebnis trunkiert wird, und wird addiert, um den Fehler zu entfernen, der als ein Ergebnis des Trunkierens auf siebzehn Bits erzeugt wurde. Die siebzehn höchstwertigsten Bits von entweder der Summe des Produktes und &delta;&sub2;, wenn das Produkt positiv ist, oder lediglich den siebzehn höchstwertigsten Bits des Produktes, wenn das Produkt negativ ist, bilden den zweiten Wurzelzahlenwert. Wenn jede Zahl erzeugt ist, dann wird sie in den Zahlen- Speicher 36 und in den Akkumulator 70 geladen, wo sie zu der Partialwurzel im Addierer 72 addiert wird, nachdem die Partialwurzel im Schieber 74 um siebzehn Stellen nach links geschoben wurde. Die Partialwurzel wird dann in das Wurzel-Register 76 geladen, aber zu diesem Zeitpunkt nicht in den D-Speicher 34 geladen, da die nächste Rest-Berechnung den vorherigen Partialwurzelwert verwenden muß. Der nächste Rest kann daher berechnet werden, indem der neue Zahlenwert, der in dem Zahlen-Speicher 36 gespeichert ist, zu einem Wert addiert wird, der gleich dem Zweifachen der vorherigen Partialwurzel ist, die für den Addierer 37 aus dem D-Speicher 34 verfügbar ist. Der Multiplexer 35 kümmert sich um die Ausrichtung der Zahlen, abhängig davon, ob es die zweite, dritte oder vierte berechnete Zahl ist. Der Addierer 37 ist erforderlich, um den Übertrag von der Partialwurzel aufzunehmen, der entstehen kann, wenn die Zahl, die in dem Zahlen-Speicher 36 geladen ist, eine negative Zahl ist.
• Der Wert (2D + di), der von dem Addierer 37 ausgegeben wird, wird in die lange Seite der Multiplizierer-Matrix 42 eingegeben, und die Zahl di wird durch den Multiplizierer 44 in die kurze Seite der Multiplizierer-Matrix 42 geführt. Der Wert von einer Hälfte des Restes, der sich im Rückführ-Register 54 befindet, wird in dem Schieber 52 verdoppelt, was zu dem Rest führt, wie er in den Addierer 46 eingegeben wird. Folglich kann dann das Produkt, das aus der Multiplizierer-Matrix 42 ausgegeben wird, von dem Rest in dem Addierer 46 subtrahiert werden. Auf diese Weise wird der neue Rest in einem einzigen Berechnungsschritt berechnet, und zwar aufgrund der Einbindung von einem zusätzlichen Addiereranschluß, der in dem Addierer 46 verwirklicht ist, in der Schaltung 30. Für die Berechnung des dritten und vierten Wurzelzahlenwertes ist der Wert der Zahlenfehlereinstellfaktoren &delta;&sub3; und &delta;&sub4;, die addiert werden, wenn die aktuelle Wurzelzahl positiv ist, ebenfalls gleich einer halben Einheit in der letzten Stelle, auf die das Ergebnis trunkiert wird.
• Diese Schritte werden wiederholt, bis vier Wurzelzahlenwerte akkumuliert sind und ein exakter Rest verfügbar ist. Wie vorstehend diskutiert, führt die Schaltung 30 dann basierend auf dem Betrag des letzten Partialrestes eine Korrektursequenz durch. Wenn der letzte Partialrest negativ ist, dann kann die Korrektur des Restes, wie in Schritt 20 angegeben, erreicht werden, indem die letzte Partialwurzel durch den Addierer 37 und Multiplizierer 42 unverändert zu dem Addierer 46 geleitet wird, um zu dem Wert von einer Hälfte des Restes addiert zu werden, der durch den Schieber 52 erhalten wird, wobei die Subtraktion von der Einheit in einer geeigneten letzten Position von dem konstanten Anschluß 50 in dem Addierer 48 vor der Addition in dem Addierer 46 durchgeführt wird. Der resultierende Wert, der gleich einer Hälfte des letzten Restes ist, wird in dem Schieber 55 um eine Stelle nach links geschoben, um den letzten Rest vorzusehen, um zu dem Ergebnis-Register 56 ausgegeben zu werden. Die letzte Partialwurzel nach dem Übertrag befindet sich in dem Wurzel-Register 76, da die Akkumulator-Schaltung 70 die erforderlich Schaltung enthält, um die Partialwurzel, die sich in dem Wurzel-Register 76 befindet, abhängig zu dekrementieren.
• Zusammenfassend schafft die vorliegende Erfindung ein Verfahren zur Durchführung einer exakten Quadratwurzel, das das Annähern des Reziprokwertes der Wurzel und das serielle Erzeugen von Großbasis-Wurzelzahlenwerten und exakten Resten umfaßt. Ein Reziprokwert-Fehlereinstellfaktor wird zu der Näherung des Reziprokwertes addiert, und Zahlenfehlereinstellfaktoren werden in jeder positiven Wurzelzahlenwert-Berechnung vor dem Trunkieren addiert, um sicherzustellen, daß irgendein Fehler in einem bestimmten Wurzelzahlenwert auf weniger als eine Einheit des Fehlers in der letzten Stelle der trunkierten Zahl begrenzt wird. Dies dient dazu, um sicherzustellen, daß der Fehler in der Zahl in der Berechnung der restlichen Wurzelzahlenwerte kompensiert werden kann. Das bestimmte Schaltungs-Ausführungsbeispiel, das hier beschrieben ist, benutzt eine Rechteck-Multiplizierer- Matrix mit einem Seitenverhältnis von 18 Bits mal 69 Bits einschließlich eines zusätzlichen Addiereranschlusses. Der Rechteck-Multiplizierer dieser Schaltung ist besonders geeignet für die Quadratwurzel-Operation der vorliegenden Erfindung, da die kurze Seite der Multiplizierer-Matrix im wesentlichen die gleiche Anzahl von Bits wie ein einzelner Wurzelzahlenwert hat.
• Obwohl die Erfindung in Verbindung mit dem bestimmten Schaltungs-Ausführungsbeispiel beschrieben wurde, ist es selbstverständlich, daß das Verfahren zur Durchführung der exakten Quadratwurzel-Funktion der vorliegenden Erfindung ebenfalls mit einer großen Anzahl von Multiplizierern weit variierenden Seitenverhältnissen verwendet werden kann, bei denen entweder vorzeichenbehafteten Zahlen oder nicht-redundante Formate verwendet werden, ebenso wie Schaltungen, die keine Matrix-Multiplizierer benutzen.

Claims (12)

1. Schaltung zur Berechnung einer exakten Quadratwurzel eines Operanden, aufweisend:

eine Schaltung zum Erhalten eines aufgerundeten Reziprokwerts der Quadratwurzel des Operanden (12 in Fig. 1) durch Hinzufügen eines reziproken Fehlereinstellfaktors zu einem angenäherten Reziprokwert zum Erhalten einer Summe und zum Trunkieren der Summe, um den aufgerundeten Reziprokwert zu erhalten, wobei der Reziprokwert-Fehlereinstellfaktor so gewählt ist, daß er einen akkumulierten Fehler in dem angenäherten Reziprokwert und den Fehler in dem aufgerundeten Reziprokwert ausgleicht, um Wurzelzahlenwerte zu erzeugen, die im akkumulierten Zustand eine Partialwurzel bilden und die immer höchstens eine Einheit an der letzten Stelle größer als oder genau gleich wie ein exakter Wert der Quadratwurzel ist, der auf eine vorgegebene Anzahl von Bits trunkiert wurde;

eine Schaltung zum Berechnen eines ersten Wurzelzahlenwerts durch (a) Multiplizieren des aufgerundeten Reziprokwerts durch den Operanden, (b) Addieren eines ersten Zahlenfehlereinstellfaktors, und (c) Trunkieren auf eine vorgegebene Anzahl von Bits des ersten digitalen Fehlereinstellfaktors, der dazu dient, den durch die Trunkierung (14 in Fig. 1) eingeführten Fehler auszugleichen;

eine Schaltung zum Berechnen eines ersten Rests als Differenz zwischen dem Operanden und dem Quadrat des ersten Wurzelzahlenwerts (16 in Fig. 1);

eine Schaltung zum iterativen Berechnen von aufeinanderfolgenden Wurzelzahlenwerten, wobei jeder aufeinanderfolgende Wurzelzahlenwert berechnet wird durch (a) Bilden eines ersten Produkts durch Multiplizieren des aufgerundeten Reziprokwerts durch ein Halb von (i) im Falle eines ersten sukzessiven Wurzelzahlenwerts dem ersten Rest, oder (ii) im Falle von zweiten und nachfolgenden sukzessiven Wurzelzahlenwerten einem vorgegebenen Rest, (b) wenn das erste Produkt positiv ist, Hinzufügen eines zweiten digitalen Fehlerausgleichsfaktors, und (c) Trunkieren des ersten Produkts auf eine vorgegebene Anzahl von Bits zum Erzeugen der sukzessiven Wurzelzahlenwerte, wobei für positive erste Produkte der Zahlenfehlereinstellfaktor so verwendbar ist, daß er einen Fehler ausgleicht, der durch die Trunkierung (14 in Fig. 1) eingeführt wurde;

eine Schaltung zum iterativen Erzeugen für jeden sukzessiven Wurzelzahlenwert eines zweiten Produkts von (a) dem sukzessiven Wurzelzahlenwert und (b) einer Summe von dem sukzessiven Wurzelzahlenwert und zweimal (i) im Falle des ersten sukzessiven Wurzelzahlenwerts von dem ersten Wurzelzahlenwert, oder (ii) im Falle des zweiten und nachfolgender sukzessiver Wurzelzahlenwerte, von einer Partialwurzel (16 in Fig. 1);

eine Schaltung zum iterativen Berechnen, für jeden sukzessiven Wurzelzahlenwert, eines sukzessiven Rests als Differenz zwischen (a) im Falle des ersten sukzessiven Wurzelzahlenwerts, dem ersten Rest, oder (b) im Falle des zweiten und anschließender sukzessiver Wurzelzahlenwerte, einem vorhergehenden Rest, und (c) dem zweiten Produkt, wobei der erste und nachfolgende Wurzelzahlenwerte und der jeweils erste und nachfolgende Reste so berechnet werden, daß jeder Rest eine Größe hat, die weniger als einer Einheit an der letzten Stelle des entsprechenden Wurzelzahlenwerts (16 in Fig. 1) entspricht; und

Schaltung zum Berechnen der Partialwurzel, wobei die Partialwurzel eine Summe aller richtig verschobenen Wurzelzahlenwerte (18 in Fig. 1) entspricht.

2. Schaltung nach Anspruch 1, wobei der erste Wurzelzahlenwert einen negativen ersten Rest zur Folge hat, wenn der erste Wurzelzahlenwert größer als ein exakter Wert der Quadratwurzel ist, die auf eine vorgegebene Anzahl von Bits trunkiert ist, wobei der erste negative Rest zur Folge hat, daß der zweite Wurzelzahlenwert negativ ist, wodurch die partielle Wurzel einen kleineren Wert als der Wert des ersten Wurzelzahlenwerts erhält.

3. Schaltung nach Anspruch 1, wobei die Schaltung zum Berechnen einer Partialwurzel eine Schaltung zum Berechnen einer Summe der geeignet verschobenen Wurzelzahlenwerte umfaßt, wobei die Summe eine Partialwurzel einer Partialwurzel und eines Rest-Paars bildet und wobei das Paar die exakte Quadratwurzel des Operanden bildet.

4. Schaltung nach Anspruch 1, wobei die Schaltung zum Erhalten des aufgerundeten Reziprokwerts aufweist:

eine Nachschlage-Tabellenschaltung zum Speichern einer Anzahl von reziproken Kernwerten (22 in Fig. 2);

eine Abfrageschaltung, die mit der Nachschlage-Tabellenschaltung gekoppelt ist, um einen bestimmten reziproken Kernwert zu holen, der etwa gleich wie der Reziprokwert der Quadratwurzel des Operanden ist (22 in Fig. 2);

eine Schaltung zum Berechnen einer ersten reziproken Annäherung, die gleich dem Produkt des partikulären reziproken Kernwerts und der Differenz von drei Halben und einem zweiten Term ist, wobei der zweite Term das Produkt des partikulären Kernwerts und eines dritten Terms ist, wobei der dritte Term das Produkt von einem Halb des Operanden und dem partikulären reziproken Kernwert ist (24 in Fig. 2); und

eine Schaltung zum Berechnen einer zweiten Reziprokwert-Annäherung, die gleich dem Produkt der ersten Reziprokwert-Annäherung und der Differenz von drei Halben und einem vierten Term ist, wobei der vierte Term das Produkt der ersten Reziprokwert-Annäherung und eines fünften Terms ist, wobei der fünfte Term das Produkt von einem Halb des Operanden und der ersten Reziprokwert-Annäherung ist (26 in Fig. 2).

5. Schaltung nach Anspruch 4, wobei die Schaltung zum Gewinnen des aufgerundeten Reziprokwerts ferner aufweist:

eine Schaltung zum Berechnen des gerundeten Reziprokwerts, der gleich der trunkierten Summe einer früheren Reziprokwert-Annäherung und eines Reziprokwert-Fehlerausgleichsfaktors (28 in Fig. 2) ist, der so gewählt ist, daß er einen akkumulierten Fehler in der vorhergehenden Reziprokwert-Annäherung und den Fehler des gerundeten Reziprokwerts ausgleicht, um Wurzelzahlenwerte zu liefern, die, wenn sie zur Bildung einer Partialwurzel akkumuliert werden, zu einer Partialwurzel führen, die höchstens in einer Einheit an der letzten Stelle größer als oder genau gleich wie der exakte Wert der Quadratwurzel ist, die auf eine vorgegebene Anzahl von Bits trunkiert wurde.

6. Schaltung nach Anspruch 5, wobei die frühere Reziprokwert- Annäherung gleich der zweiten Reziprokwert-Annäherung ist.

7. Schaltung nach Anspruch 5, wobei der Reziprokwert-Fehlereinstellfaktor gleich der Summe aus einem ersten und einem zweiten Term ist, wobei der erste Term gleich 2-k an der N- ten-Stelle ist, wobei N gleich der Zahl von Bits der Basis der Wurzelzahlenwerte ist und wobei k eine vorgegebene Anzahl von Schutzbits ist, wobei der zweite Term groß genug ist, um den gerundeten Reziprokwert derart zu verzerren, daß der gerundete Reziprokwert größer als ein exakter Reziprokwert der Quadratwurzel des Operanden ist und wobei der zweite Term klein genug ist, damit der erste und zweite Rest weniger als eine Einheit an der letzten Stelle der jeweils ersten und zweiten Wurzelzahlenwerte sind.

8. Verfahren zum Berechnen einer exakten Quadratwurzel eines Operanden, mit den Schritten:

Berechnen eines gerundeten Reziprokwerts (12 in Fig. 1) durch Addieren eines Reziprokwert-Fehlerausgleichsfaktors zu einem angenäherten Reziprokwert, um eine Summe zu erhalten und Trunkieren der Summe, um den gerundeten Reziprokwert zu kriegen, wobei der Reziprokwert-Fehlerausgleichsfaktor so gewählt ist, daß er einen akkumulierten Fehler in dem angenäherten Reziprokwert ausgleicht und den gerundeten Reziprokwert verzerrt, um Wurzelzahlenwerte zu liefern, die bei Akkumulierung zur Bildung einer Partialwurzel immer höchstens eine Einheit an der letzten Stelle größer oder genau gleich groß sind wie ein exakter Wert der Quadratwurzel, die auf eine vorgegebene Anzahl von Bits trunkiert ist;

Eingeben des gerundeten Reziprokwerts des Operanden (12 in Fig. 1) an einem ersten Eingang einer Multipliziererschaltung;

Eingeben eines Restwerts, der anfänglich gleich wie der Operand ist (10 in Fig. 1), an einem zweiten Eingang der Multiplizierschaltung;

iteratives Berechnen einer ersten und einer gewünschten Zahl von aufeinanderfolgenden Wurzelzahlenwerten (14 in Fig. 1) von einem ersten und von nachfolgenden Wurzelzahlenprodukten, die jeweils durch Multiplizieren des gerundeten Reziprokwerts des Operanden mit einem ersten Term erhalten wurden, der gleich wie ein Halb des Restwertes ist, und zwar für das erste Wurzelzahlenprodukt, wobei der erste Term gleich wie der Operand ist;

Addieren eines ersten Zahlenfehlerausgleichsfaktors zu dem ersten Wurzelzahlenprodukt, und selektives Addieren eines zweiten Wurzelzahlenwerts zu jedem nachfolgenden Wurzelzahlenprodukt, wenn ein solches Wurzelzahlenprodukt positiv ist (14 in Fig. 1);

Trunkieren des Produkts auf eine vorgegebene Anzahl von Bits zur Erzeugung des Wurzelzahlenwerts, für positive Wurzelzahlenprodukte, wobei der Zahlenfehlerausgleichsfaktor so anwendbar ist, daß er einen durch die Trunkierung eingeführten Fehler ausgleicht;

iteratives Berechnen einer Partialwurzel als Summe aller richtig verschobenen Wurzelzahlenwerte (18 in Fig. 1); und

iteratives Berechnen, für jeden nachfolgenden Wurzelzahlenwert, eines nachfolgenden Rests (16 in Fig. 1) als Differenz zwischen (a) dem Restwert und (b) einem Produkt von (i) dem Wurzelzahlenwert und (ii) von einer Summe der Wurzelzahlenwerte und einem zweiten Term, der gleich wie zweimal die vorhergehende Partialwurzel ist, wobei der zweite Term anfänglich gleich Null ist, und wobei die aufeinanderfolgenden Wurzelzahlenwerte und die aufeinanderfolgenden Reste so berechnet werden, daß jeder Rest eine Größe hat, der kleiner als eine Einheit in der letzten Stelle eines vorhergehenden Wurzelzahlenwerts ist (14 in Fig. 1).

9. Verfahren nach Anspruch 8, wobei die Wurzelzahlenwerte zu einem negativen Rest führen, wenn die Wurzelzahlenwerte größer als der exakte Wert sind, wobei der negative Rest bewirkt, daß ein nachfolgender Wurzelzahlenwert negativ ist, wodurch ein Produkt aus der nachfolgenden Wurzelzahl und einem Term, der die Summe der nachfolgenden Wurzelzahl und zweimal der vorhergehenden Partialwurzel so anwendbar ist, daß es die Größe des negativen Rests reduziert.

10. Verfahren nach Anspruch 8, wobei der Schritt des Berechnens eines gerundeten Reziprokwerts des Operanden die Schritte aufweist:

Herausziehen eines Kernwerts für einen Reziprokwert aus einer Tabelle, die eine Anzahl von Werten enthält;

Berechnen einer ersten Reziprokwert-Annäherung, die gleich dem Produkt des partikulären Reziprokwert-Kernwerts und der Differenz von drei Halben und einem zweiten Term ist, wobei der zweite Term das Produkt des partikulären Reziprokwert-Kernwerts und eines dritten Terms ist, wobei der dritte Term das Produkt von einem Halb des Operanden und dem partikulären Reziprokwert-Kernwerts ist; und

Berechnen einer zweiten Reziprokwert-Annäherung, die gleich dem Produkt der ersten Reziprokwert-Annäherung und der Differenz von drei Halben und einem vierten Term ist, wobei der vierte Term das Produkt der ersten Reziprokwert- Annäherung und eines fünften Terms ist, wobei der fünfte Term das Produkt von einem Halben des Operanden und der ersten Reziprokwert-Annäherung ist.

11. Verfahren nach Anspruch 10, wobei der Schritt des Berechnens eines gerundeten Reziprokwerts des Operanden ferner die Schritte aufweist:

Berechnen des gerundeten Reziprokwerts, der gleich der trunkierten Summe von einer früheren Reziprokwert-Annäherung und einem Reziprokwert-Fehlerausgleichsfaktors ist, der so gewählt ist, daß er einen akkumulierten Fehler in der früheren Reziprokwert-Annäherung ausgleicht und den gerundeten Reziprokwert verzerrt, um Wurzelzahlenwerte zu erzeugen, die, wenn sie zur Bildung einer Partialwurzel akkumuliert werden, zu einer Partialwurzel führen, die in maximal einer Einheit an der letzten Stelle größer gleich oder exakt gleich wie der exakte Wert der Quadratwurzel ist, die auf eine vorgegebene Anzahl von Bits trunkiert ist.

12. Verfahren nach Anspruch 11, wobei der Reziprokwert-Fehlerausgleichsfaktor gleich der Summe aus einem ersten und einem zweiten Term ist, wobei der erste Term gleich wie 2-k an der N-ten-Stelle ist, wobei N gleich der Anzahl von Bits der Basis der Wurzelzahlenwerte und k eine vorgegebene Anzahl von Schutzbits ist, und wobei der zweite Term groß genug ist, um den gerundeten Reziprokwert so zu verzerren, daß der gerundete Reziprokwert größer als ein exakter Reziprokwert der Quadratwurzel des Operanden ist und wobei der zweite Term klein genug ist, um zu bewirken, daß die Reste weniger als einer Einheit an der letzten Stelle von einem vorhergehenden Wurzelzahlenwert entsprechen.