Divisionsalgorithmus - Division algorithm

Ein Divisionsalgorithmus ist ein Algorithmus , der bei gegebenen zwei ganzen Zahlen N und D ihren Quotienten und/oder Rest berechnet , das Ergebnis der euklidischen Division . Einige werden von Hand aufgetragen, während andere von digitalen Schaltungsdesigns und Software verwendet werden.

Divisionsalgorithmen fallen in zwei Hauptkategorien: langsame Division und schnelle Division. Langsame Divisionsalgorithmen erzeugen pro Iteration eine Stelle des endgültigen Quotienten. Beispiele für eine langsame Teilung sind die Wiederherstellung , die nicht ausgeführte Wiederherstellung, die nicht wiederherstellende und die SRT- Teilung. Schnelle Divisionsverfahren beginnen mit einer engen Annäherung an den endgültigen Quotienten und erzeugen bei jeder Iteration doppelt so viele Stellen des endgültigen Quotienten. Newton-Raphson- und Goldschmidt- Algorithmen fallen in diese Kategorie.

Varianten dieser Algorithmen ermöglichen die Verwendung von schnellen Multiplikationsalgorithmen . Daraus ergibt sich, dass für große ganze Zahlen die für eine Division benötigte Rechenzeit bis auf einen konstanten Faktor gleich der für eine Multiplikation benötigten Zeit ist, unabhängig davon, welcher Multiplikationsalgorithmus verwendet wird.

Die Diskussion bezieht sich auf das Formular , wo ${\displaystyle N/D=(Q,R)}$

• N = Zähler (Dividende)
• D = Nenner (Teiler)

ist die Eingabe, und

• Q = Quotient
• R = Rest

ist die Ausgabe.

Division durch wiederholte Subtraktion

Der einfachste Divisionsalgorithmus, der historisch in einen größten gemeinsamen Teileralgorithmus integriert ist, der in Euklids Elements , Buch VII, Proposition 1 vorgestellt wird, findet den Rest bei gegebenen zwei positiven ganzen Zahlen nur unter Verwendung von Subtraktionen und Vergleichen:

R := N
while R ≥ D do
  R := R − D
end
return R

Der Beweis, dass Quotient und Rest existieren und eindeutig sind (beschrieben bei Euklidische Division ), führt zu einem vollständigen Divisionsalgorithmus mit Additionen, Subtraktionen und Vergleichen:

function divide(N, D)
  if D = 0 then error(DivisionByZero) end
  if D < 0 then (Q, R) := divide(N, −D); return (−Q, R) end
  if N < 0 then
    (Q,R) := divide(−N, D)
    if R = 0 then return (−Q, 0)
    else return (−Q − 1, D − R) end
  end
  -- At this point, N ≥ 0 and D > 0
  return divide_unsigned(N, D)
end  
function divide_unsigned(N, D)
  Q := 0; R := N
  while R ≥ D do
    Q := Q + 1
    R := R − D
  end
  return (Q, R)
end

Dieses Verfahren erzeugt immer R ≥ 0. Obwohl es sehr einfach ist, benötigt es Ω(Q) Schritte und ist daher exponentiell langsamer als selbst langsame Divisionsalgorithmen wie die lange Division. Es ist nützlich, wenn Q bekanntermaßen klein ist (ein ausgabesensitiver Algorithmus ) und als ausführbare Spezifikation dienen kann.

Lange Teilung

Die lange Division ist der Standardalgorithmus, der für die Division von mehrstelligen Zahlen in Dezimalschreibweise mit Stift und Papier verwendet wird. Er verschiebt sich allmählich vom linken zum rechten Ende des Dividenden, wobei in jeder Stufe das größtmögliche Vielfache des Divisors (auf Ziffernebene) abgezogen wird; die Vielfachen werden dann die Ziffern des Quotienten und die letzte Differenz ist dann der Rest.

Bei Verwendung mit einem binären Radix bildet dieses Verfahren die Grundlage für den (vorzeichenlosen) ganzzahligen Division mit Rest-Algorithmus unten. Kurze Division ist eine abgekürzte Form der langen Division, die für einstellige Teiler geeignet ist. Chunking  – auch bekannt als partielle Quotientenmethode oder Hangman-Methode – ist eine weniger effiziente Form der langen Division, die möglicherweise leichter zu verstehen ist. Indem man erlaubt, mehr Vielfache zu subtrahieren, als man derzeit auf jeder Stufe hat, kann auch eine freiere Variante der langen Division entwickelt werden

Ganzzahldivision (ohne Vorzeichen) mit Rest

Der folgende Algorithmus, die binäre Version der berühmten langen Division , teilt N durch D , wobei der Quotient in Q und der Rest in R platziert wird . Im folgenden Pseudocode werden alle Werte als vorzeichenlose Ganzzahlen behandelt.

if D = 0 then error(DivisionByZeroException) end
Q := 0                  -- Initialize quotient and remainder to zero
R := 0                     
for i := n − 1 .. 0 do  -- Where n is number of bits in N
  R := R << 1           -- Left-shift R by 1 bit
  R(0) := N(i)          -- Set the least-significant bit of R equal to bit i of the numerator
  if R ≥ D then
    R := R − D
    Q(i) := 1
  end
end

Beispiel

Nehmen wir N=1100 ₂ (12 ₁₀ ) und D=100 ₂ (4 ₁₀ )

Schritt 1 : Setze R=0 und Q=0
Schritt 2 : Nimm i=3 (eins weniger als die Anzahl der Bits in N)
Schritt 3 : R=00 (links verschoben um 1)
Schritt 4 : R=01 (Einstellung von R (0) bis N(i))
Schritt 5 : R<D, also Anweisung überspringen

Schritt 2 : Setze i=2
Schritt 3 : R=010
Schritt 4 : R=011
Schritt 5 : R<D, Anweisung übersprungen

Schritt 2 : Setze i=1
Schritt 3 : R=0110
Schritt 4 : R=0110
Schritt 5 : R>=D, Anweisung eingegeben
Schritt 5b : R=10 (R−D)
Schritt 5c : Q=10 (Einstellung Q( i) zu 1)

Schritt 2 : i=0 setzen
Schritt 3 : R=100
Schritt 4 : R=100
Schritt 5 : R>=D, Anweisung eingegeben
Schritt 5b : R=0 (R−D)
Schritt 5c : Q=11 (Einstellung Q( i) zu 1)

Ende
Q=11 ₂ (3 ₁₀ ) und R=0.

Langsame Divisionsmethoden

Langsame Divisionsmethoden basieren alle auf einer Standard-Rekursionsgleichung

${\displaystyle R_{j+1}=B\times R_{j}-q_{n-(j+1)}\times D,}$

wo:

• R _j ist der j- te Teilrest der Division
• B ist die Radix (Basis, normalerweise 2 intern in Computern und Taschenrechnern)
• q _{n - ( j + 1)} ist die Ziffer des Quotienten in Position n - ( j + 1), wobei die Ziffernpositionen aus niedrigstwertigen 0 bis höchstwertigen durchnumeriert sind n -1
• n ist die Anzahl der Stellen im Quotienten
• D ist der Teiler

Teilung wiederherstellen

Das Wiederherstellen der Division arbeitet mit Festkomma- Bruchzahlen und hängt von der Annahme ab, dass 0 < D < N ist .

Die Quotientenziffern q werden aus der Ziffernmenge {0,1} gebildet.

Der grundlegende Algorithmus für die binäre (Radix 2) Wiederherstellung der Division ist:

R := N
D := D << n            -- R and D need twice the word width of N and Q
for i := n − 1 .. 0 do  -- For example 31..0 for 32 bits
  R := 2 * R − D          -- Trial subtraction from shifted value (multiplication by 2 is a shift in binary representation)
  if R ≥ 0 then
    q(i) := 1          -- Result-bit 1
  else
    q(i) := 0          -- Result-bit 0
    R := R + D         -- New partial remainder is (restored) shifted value
  end
end

-- Where: N = numerator, D = denominator, n = #bits, R = partial remainder, q(i) = bit #i of quotient

Die nicht ausgeführte Wiederherstellungsdivision ähnelt der Wiederherstellungsdivision, außer dass der Wert von 2R gespeichert wird, sodass D für den Fall von R < 0 nicht wieder hinzugefügt werden muss.

Nicht wiederherstellende Abteilung

Die nicht wiederherstellende Division verwendet die Ziffernmenge {−1, 1} für die Quotientenziffern anstelle von {0, 1}. Der Algorithmus ist komplexer, hat aber bei der Implementierung in Hardware den Vorteil, dass es nur eine Entscheidung und Addition/Subtraktion pro Quotientenbit gibt; es gibt keinen Wiederherstellungsschritt nach der Subtraktion, wodurch die Anzahl der Operationen möglicherweise bis zur Hälfte reduziert und schneller ausgeführt werden kann. Der grundlegende Algorithmus für die binäre (Radix 2) nicht wiederherstellende Division von nicht negativen Zahlen ist:

R := N
D := D << n            -- R and D need twice the word width of N and Q
for i = n − 1 .. 0 do  -- for example 31..0 for 32 bits
  if R >= 0 then
    q[i] := +1
    R := 2 * R − D
  else
    q[i] := −1
    R := 2 * R + D
  end if
end
 
-- Note: N=numerator, D=denominator, n=#bits, R=partial remainder, q(i)=bit #i of quotient.

Nach diesem Algorithmus liegt der Quotient in einer nicht standardmäßigen Form vor, die aus Ziffern von –1 und +1 besteht. Diese Form muss in binär umgewandelt werden, um den endgültigen Quotienten zu bilden. Beispiel:

Wandeln Sie den folgenden Quotienten in die Ziffernmenge {0,1} um:
Start:	${\displaystyle Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}}$
1. Bilden Sie den positiven Term:	${\displaystyle P=11101010\,}$
2. Maskieren Sie den negativen Term*:	${\displaystyle M=00010101\,}$
3. Subtrahieren: :${\displaystyle PM}$	${\displaystyle Q=11010101\,}$
*.( Vorzeichenbehaftete binäre Notation mit Einerkomplement ohne Zweierkomplement )

Wenn die −1-Ziffern von wie üblich als Nullen (0) gespeichert werden, dann ist das und die Berechnung ist trivial: Führen Sie ein Einerkomplement (bitweises Komplement) auf dem Original durch . ${\displaystyle Q}$${\displaystyle P}$ ${\displaystyle Q}$${\displaystyle M}$${\displaystyle Q}$

Q := Q − bit.bnot(Q)      -- Appropriate if −1 digits in Q are represented as zeros as is common.

Schließlich sind die von diesem Algorithmus berechneten Quotienten immer ungerade, und der Rest in R liegt im Bereich −D ≤ R < D. Zum Beispiel 5 / 2 = 3 R −1. Um in einen positiven Rest umzuwandeln, führen Sie einen einzelnen Wiederherstellungsschritt aus, nachdem Q von der Nicht-Standardform in die Standardform umgewandelt wurde:

if R < 0 then
  Q := Q − 1
  R := R + D  -- Needed only if the remainder is of interest.
end if

Der tatsächliche Rest ist R >> n. (Wie beim Wiederherstellen der Division werden die niederwertigen Bits von R mit der gleichen Rate verbraucht, wie die Bits des Quotienten Q erzeugt werden, und es ist üblich, für beide ein einziges Schieberegister zu verwenden.)

SRT-Abteilung

Die SRT-Division wurde nach ihren Schöpfern (Sweeney, Robertson und Tocher) benannt und ist eine beliebte Methode zur Division in vielen Mikroprozessorimplementierungen . Die SRT-Division ähnelt der Division ohne Wiederherstellung, verwendet jedoch eine Nachschlagetabelle, die auf dem Dividenden und dem Divisor basiert, um jede Quotientenziffer zu bestimmen.

Der wichtigste Unterschied besteht darin, dass für den Quotienten eine redundante Darstellung verwendet wird. Wenn Sie beispielsweise eine Radix-4-SRT-Division implementieren, wird jede Quotientenziffer aus fünf Möglichkeiten ausgewählt: { –2, –1, 0, +1, +2 }. Aus diesem Grund muss die Wahl einer Quotientenziffer nicht perfekt sein; spätere Quotientenziffern können leichte Fehler korrigieren. (Zum Beispiel sind die Quotientenziffernpaare (0, +2) und (1, −2) äquivalent, da 0×4+2 = 1×4−2.) Diese Toleranz erlaubt die Auswahl von Quotientenziffern mit nur wenigen die höchstwertigen Bits des Dividenden und Divisors, anstatt eine Subtraktion in voller Breite zu erfordern. Diese Vereinfachung ermöglicht wiederum die Verwendung einer Radix höher als 2.

Wie bei der nicht wiederherstellenden Division sind die letzten Schritte eine abschließende Subtraktion der vollen Breite, um das letzte Quotientenbit aufzulösen, und die Umwandlung des Quotienten in die Standard-Binärform.

Der berüchtigte Fehler bei der Gleitkomma-Division des Intel Pentium- Prozessors wurde durch eine falsch codierte Nachschlagetabelle verursacht. Fünf der 1066 Einträge waren fälschlicherweise weggelassen worden.

Schnelle Divisionsmethoden

Newton-Raphson-Division

Newton-Raphson verwendet die Newton-Methode , um den Kehrwert von zu finden und diesen Kehrwert mit zu multiplizieren, um den endgültigen Quotienten zu finden .${\displaystyle D}$${\displaystyle N}$${\displaystyle Q}$

Die Schritte der Newton-Raphson-Division sind:

1. Berechnen Sie eine Schätzung für den Kehrwert des Divisors .${\displaystyle X_{0}}$${\displaystyle 1/D}$${\displaystyle D}$
2. Berechnen Sie sukzessive genauere Schätzungen des Kehrwerts. Hier setzt man die Newton-Raphson-Methode als solche ein.${\displaystyle X_{1},X_{2},\ldots ,X_{S}}$
3. Berechnen Sie den Quotienten, indem Sie den Dividenden mit dem Kehrwert des Divisors multiplizieren: .${\displaystyle Q=NX_{S}}$

Um das Newton-Verfahren anzuwenden, um den Kehrwert von zu finden , ist es notwendig, eine Funktion zu finden , die eine Null bei hat . Die offensichtliche solche Funktion ist , aber die Newton-Raphson-Iteration dafür ist nicht hilfreich, da sie nicht berechnet werden kann, ohne den Kehrwert von bereits zu kennen (außerdem wird versucht, den genauen Kehrwert in einem Schritt zu berechnen, anstatt iterative Verbesserungen zuzulassen). Eine funktionierende Funktion ist , für die die Newton-Raphson-Iteration ${\displaystyle D}$${\displaystyle f(X)}$${\displaystyle X=1/D}$${\displaystyle f(X)=DX-1}$${\displaystyle D}$${\displaystyle f(X)=(1/X)-D}$

${\displaystyle X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-D \ über -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i}),}$

die nur aus Multiplikation und Subtraktion oder aus zwei verschmolzenen Multiplikations-Additionen berechnet werden kann . ${\displaystyle X_{i}}$

Aus rechnerischer Sicht sind die Ausdrücke und nicht äquivalent. Um unter Verwendung des zweiten Ausdrucks ein Ergebnis mit einer Genauigkeit von 2 n Bits zu erhalten, muss man das Produkt zwischen und mit der doppelten Genauigkeit von ( n Bits) berechnen . Im Gegensatz dazu muss das Produkt zwischen und nur mit einer Genauigkeit von n Bits berechnet werden , da die führenden n Bits (nach dem Binärpunkt) von Nullen sind. ${\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})}$${\displaystyle X_{i+1}=X_{i}(2-DX_{i})}$${\displaystyle X_{i}}$${\displaystyle (2-DX_{i})}$${\displaystyle X_{i}}$${\displaystyle X_{i}}$${\displaystyle (1-DX_{i})}$${\displaystyle (1-DX_{i})}$

Wenn der Fehler als definiert ist , dann: ${\displaystyle \varepsilon_{i}=1-DX_{i}}$

${\displaystyle {\begin{ausgerichtet}\varepsilon_{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\ &=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon_{i}} ^{2}.\\\end{ausgerichtet}}}$

Diese Quadratur des Fehlers bei jedem Iterationsschritt – die sogenannte quadratische Konvergenz des Newton-Raphson-Verfahrens – hat zur Folge, dass sich die Anzahl der richtigen Ziffern im Ergebnis bei jeder Iteration ungefähr verdoppelt , eine Eigenschaft, die bei den beteiligten Zahlen äußerst wertvoll wird viele Stellen haben (zB im großen Integer-Bereich). Dies bedeutet aber auch, dass die anfängliche Konvergenz der Methode vergleichsweise langsam sein kann, insbesondere wenn die anfängliche Schätzung schlecht gewählt ist. ${\displaystyle X_{0}}$

Für das Teilproblem der Auswahl einer anfänglichen Schätzung ist es zweckmäßig, eine Bitverschiebung auf den Divisor D anzuwenden , um ihn so zu skalieren, dass 0,5  D  ≤ 1; indem man dieselbe Bitverschiebung auf den Zähler N anwendet , stellt man sicher, dass sich der Quotient nicht ändert. Dann könnte man eine lineare Näherung in der Form ${\displaystyle X_{0}}$

${\displaystyle X_{0}=T_{1}+T_{2}D\approx {\frac {1}{D}}\,}$

um Newton-Raphson zu initialisieren. Um das Maximum des Absolutwerts des Fehlers dieser Näherung auf das Intervall zu minimieren , sollte man ${\displaystyle [0.5,1]}$

${\displaystyle X_{0}={48 \over 17}-{32 \over 17}D.\,}$

Die Koeffizienten der linearen Näherung werden wie folgt bestimmt. Der Absolutwert des Fehlers ist . Das Minimum des maximalen Absolutwerts des Fehlers wird durch das auf angewendete Chebyshev-Äquioszillationstheorem bestimmt . Das lokale Minimum von tritt wenn auf , was eine Lösung hat . Die Funktion an diesem Minimum muss ein entgegengesetztes Vorzeichen haben wie die Funktion an den Endpunkten, nämlich . Die beiden Gleichungen in den beiden Unbekannten haben eine eindeutige Lösung und , und der maximale Fehler ist . Bei dieser Näherung ist der Absolutwert des Fehlers des Anfangswertes kleiner als ${\displaystyle |\varepsilon_{0}|=|1-D(T_{1}+T_{2}D)|}$${\displaystyle F(D)=1-D(T_{1}+T_{2}D)}$${\displaystyle F(D)}$${\displaystyle F'(D)=0}$${\displaystyle D=-T_{1}/(2T_{2})}$${\displaystyle F(1/2)=F(1)=-F(-T_{1}/(2T_{2}))}$${\displaystyle T_{1}=48/17}$${\displaystyle T_{2}=-32/17}$${\displaystyle F(1)=1/17}$

${\displaystyle \vert \varepsilon_{0}\vert \leq {1 \over 17}\approx 0.059.\,}$

Es ist möglich, eine Polynomanpassung mit einem Grad größer als 1 zu erzeugen, indem die Koeffizienten unter Verwendung des Remez-Algorithmus berechnet werden . Der Kompromiss besteht darin, dass die anfängliche Schätzung mehr Rechenzyklen erfordert, aber hoffentlich im Austausch für weniger Iterationen von Newton-Raphson.

Da für diese Methode die Konvergenz exakt quadratisch ist, folgt

${\displaystyle S=\left\lceil\log_{2}{\frac {P+1}{\log_{2}17}}\right\rceil\,}$

Schritte reichen aus, um den Wert bis auf binäre Stellen zu berechnen . Dies ergibt 3 für einfache IEEE- Genauigkeit und 4 für doppelte Genauigkeit und doppelte erweiterte Formate. ${\displaystyle P\,}$

Pseudocode

Im Folgenden wird der Quotient von N und D mit einer Genauigkeit von P Binärstellen berechnet :

Express D as M × 2e where 1 ≤ M < 2 (standard floating point representation)
D' := D / 2e+1   // scale between 0.5 and 1, can be performed with bit shift / exponent subtraction
N' := N / 2e+1
X := 48/17 − 32/17 × D'   // precompute constants with same precision as D
repeat ${\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}$ times   // can be precomputed based on fixed P
    X := X + X × (1 - D' × X)
end
return N' × X

Für eine Gleitkommadivision mit doppelter Genauigkeit verwendet diese Methode beispielsweise 10 Multiplikationen, 9 Additionen und 2 Verschiebungen.

Variante Newton-Raphson-Division

Das Newton-Raphson-Divisionsverfahren kann wie folgt modifiziert werden, um etwas schneller zu sein. Nachdem Sie N und D so verschoben haben , dass D in [0.5, 1.0] ist, initialisieren Sie mit

${\displaystyle X:={\frac {140}{33}}+D\cdot \left({\frac {-64}{11}}+D\cdot {\frac {256}{99}}\right ).}$

Dies ist die beste quadratische Anpassung an 1/ D und ergibt einen Absolutwert des Fehlers kleiner oder gleich 1/99. Es wird gewählt, um den Fehler gleich einem neu skalierten Tschebyscheff-Polynom dritter Ordnung der ersten Art zu machen. Die Koeffizienten sollten vorberechnet und hartcodiert sein.

Verwenden Sie dann in der Schleife eine Iteration, die den Fehler würfelt.

${\displaystyle E:=1-D\cdot X}$

${\displaystyle Y:=X\cdot E}$

${\displaystyle X:=X+Y+Y\cdot E.}$

Der Y · E- Term ist neu.

Wenn die Schleife ausgeführt wird, bis X mit 1/ D auf seinen führenden P- Bits übereinstimmt , dann beträgt die Anzahl der Iterationen nicht mehr als

${\displaystyle \left\lceil\log_{3}\left({\frac {P+1}{\log_{2}99}}\right)\right\rceil}$

Das ist die Anzahl von Malen, die 99 gewürfelt werden muss, um 2 ^{P +1 zu erhalten} . Dann

${\displaystyle Q:=N\cdot X}$

ist der Quotient zu P Bits.

Die Verwendung von Polynomen höheren Grades entweder bei der Initialisierung oder der Iteration führt zu einer Verschlechterung der Leistung, da die erforderlichen zusätzlichen Multiplikationen besser für die Durchführung von mehr Iterationen ausgegeben würden.

Geschäftsbereich Goldschmidt

Die Goldschmidt-Division (nach Robert Elliott Goldschmidt) verwendet einen iterativen Prozess, bei dem sowohl der Dividenden als auch der Divisor wiederholt mit einem gemeinsamen Faktor F _i multipliziert werden , der so gewählt wird, dass der Divisor gegen 1 konvergiert. Dadurch konvergiert der Dividenden gegen den gesuchten Quotienten Q :

${\displaystyle Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots}}{F_{\ldots}}}.}$

Die Schritte für die Goldschmidt-Division sind:

1. Erzeuge eine Schätzung für den Multiplikationsfaktor F _i .
2. Multiplizieren Sie den Dividenden und den Divisor mit F _i .
3. Wenn der Divisor nahe genug an 1 liegt, geben Sie den Dividenden zurück, andernfalls fahren Sie mit Schritt 1 fort.

Unter der Annahme, dass N / D so skaliert wurde, dass 0 <  D  < 1 ist, basiert jedes F _i auf D :

${\displaystyle F_{i+1}=2-D_{i}.}$

Die Multiplikation von Dividende und Divisor mit dem Faktor ergibt:

${\displaystyle {\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1} }{F_{i+1}}}.}$

Nach einer ausreichenden Anzahl k von Iterationen . ${\displaystyle Q=N_{k}}$

Die Goldschmidt-Methode wird in AMD Athlon-CPUs und späteren Modellen verwendet. Er ist auch als Anderson Earle Goldschmidt Powers (AEGP)-Algorithmus bekannt und wird von verschiedenen IBM-Prozessoren implementiert. Obwohl es mit der gleichen Rate wie eine Newton-Raphson-Implementierung konvergiert, besteht ein Vorteil des Goldschmidt-Verfahrens darin, dass die Multiplikationen im Zähler und im Nenner parallel durchgeführt werden können.

Binomialsatz

Die Goldschmidt-Methode kann mit Faktoren verwendet werden, die Vereinfachungen durch den Binomialsatz erlauben . Angenommen, N/D wurde mit einer Potenz von zwei skaliert, so dass . Wir wählen und . Dies ergibt ${\displaystyle D\in ({\tfrac {1}{2}},1]}$${\displaystyle D=1-x}$${\displaystyle F_{i}=1+x^{2^{i}}}$

${\displaystyle {\frac {N}{1-x}}={\frac {N\cdot (1+x)}{1-x^{2}}}={\frac {N\cdot (1+ .) x)\cdot (1+x^{2})}{1-x^{4}}}=\cdots =Q'={\frac{N'=N\cdot (1+x)\cdot (1 +x^{2})\cdot \cdot \cdot (1+x^{2^{(n-1)}})}{D'=1-x^{2^{n}}\approx 1} }}$.

Nach den Schritten kann der Nenner mit einem relativen Fehler auf gerundet werden${\displaystyle n}$${\displaystyle (x\in [0,{\tfrac {1}{2}}))}$${\displaystyle 1-x^{2^{n}}}$${\displaystyle 1}$

${\displaystyle \varepsilon_{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}}$

was bei wann maximal ist , wodurch eine minimale Genauigkeit von Binärziffern bereitgestellt wird . ${\displaystyle 2^{-2^{n}}}$${\displaystyle x={1 \over 2}}$${\displaystyle 2^{n}}$

Großzahlige Methoden

Verfahren, die für die Hardwareimplementierung entwickelt wurden, skalieren im Allgemeinen nicht auf ganze Zahlen mit Tausenden oder Millionen von Dezimalstellen; diese treten beispielsweise häufig bei modularen Reduktionen in der Kryptographie auf . Für diese großen ganzen Zahlen transformieren effizientere Divisionsalgorithmen das Problem, um eine kleine Anzahl von Multiplikationen zu verwenden, die dann mit einem asymptotisch effizienten Multiplikationsalgorithmus wie dem Karatsuba-Algorithmus , der Toom-Cook-Multiplikation oder dem Schönhage-Strassen-Algorithmus durchgeführt werden können . Das Ergebnis ist, dass die Rechenkomplexität der Division dieselbe Größenordnung (bis zu einer multiplikativen Konstante) hat wie die der Multiplikation. Beispiele umfassen Reduktion auf Multiplikation durch das Newton-Verfahren, wie oben beschrieben , sowie die etwas schnellere Burnikel-Ziegler-Division , Barrett-Reduktion und Montgomery-Reduktionsalgorithmen . Das Newton-Verfahren ist besonders effizient in Szenarien, in denen man viele Male durch denselben Divisor dividieren muss, da nach der anfänglichen Newton-Inversion nur eine (abgeschnittene) Multiplikation für jede Division benötigt wird.

Division durch eine Konstante

Die Division durch eine Konstante D entspricht der Multiplikation mit ihrem Kehrwert . Da der Nenner konstant ist, ist auch sein Kehrwert (1/ D ). Somit ist es möglich, den Wert von (1/ D ) einmal zur Kompilierzeit zu berechnen und zur Laufzeit die Multiplikation N ·(1/ D ) statt der Division N/D durchzuführen . In der Gleitkomma- Arithmetik stellt die Verwendung von (1/ D ) kein Problem dar, aber in der Ganzzahl- Arithmetik wird der Kehrwert immer zu Null ausgewertet (vorausgesetzt | D | > 1).

Es ist nicht notwendig, spezifisch (1/ D ) zu verwenden; jeder Wert ( X / Y ), der sich auf (1/ D ) reduziert, kann verwendet werden. Für die Division durch 3 könnten beispielsweise die Faktoren 1/3, 2/6, 3/9 oder 194/582 verwendet werden. Wenn Y eine Zweierpotenz wäre, würde sich folglich der Divisionsschritt auf eine schnelle Bitverschiebung nach rechts reduzieren. Der Effekt der Berechnung von N / D als ( N · X )/ Y ersetzt eine Division durch eine Multiplikation und eine Verschiebung. Beachten Sie, dass die Klammern wichtig sind, da N ·( X / Y ) zu Null ausgewertet wird.

Wenn jedoch D selbst keine Zweierpotenz ist, gibt es kein X und kein Y , das die obigen Bedingungen erfüllt. Glücklicherweise liefert ( N · X )/ Y genau das gleiche Ergebnis wie N / D in ganzzahliger Arithmetik, auch wenn ( X / Y ) nicht genau gleich 1/ D ist , aber "nah genug", dass der durch die Näherung eingeführte Fehler . ist in den Bits, die durch die Schiebeoperation verworfen werden.

Als konkretes Festkomma-Arithmetik- Beispiel kann für 32-Bit-Ganzzahlen ohne Vorzeichen die Division durch 3 durch eine Multiplikation mit ersetzt werden2863311531/2 ³³, eine Multiplikation mit 2863311531 ( hexadezimal 0xAAAAAAAB), gefolgt von einer 33-Bit-Verschiebung nach rechts. Der Wert von 2863311531 wird berechnet als2 ³³/3, dann aufgerundet. Ebenso kann die Division durch 10 als Multiplikation mit 3435973837 (0xCCCCCCCD) gefolgt von der Division durch 2 ³⁵ (oder 35 Bitverschiebung nach rechts) ausgedrückt werden . OEIS liefert Folgen der Konstanten für die Multiplikation als A346495 und für die Rechtsverschiebung als A346496 .

Für die allgemeine -Bit-Ganzzahldivision ohne Vorzeichen, bei der der Divisor keine Zweierpotenz ist, wandelt die folgende Identität die Division in eine Zwei- Bit-Addition/Subtraktion, eine Bit-für- Bit-Multiplikation um (wobei nur die obere Hälfte des Ergebnisses verwendet wird) und mehrere Schichten, nach Vorberechnung und : ${\displaystyle x}$${\displaystyle D}$${\displaystyle x}$${\displaystyle x}$${\displaystyle x}$${\displaystyle k=x+\lceil\log_{2}{D}\rceil}$${\displaystyle a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}}$

${\displaystyle \left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {Nb}{2}}\right\rfloor +b }{2^{kx-1}}}\right\rfloor }$ wo ${\displaystyle b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor }$

In einigen Fällen kann die Division durch eine Konstante in noch kürzerer Zeit durchgeführt werden, indem das "Multiplizieren mit einer Konstanten" in eine Reihe von Verschiebungen und Additionen oder Subtraktionen umgewandelt wird . Von besonderem Interesse ist die Division durch 10, für die man den exakten Quotienten erhält, ggf. mit Rest.

Rundungsfehler

Rundungsfehler können aufgrund begrenzter Genauigkeit durch Divisionsoperationen eingeführt werden .

Siehe auch

• Galeerenabteilung
• Multiplikationsalgorithmus
• Pentium FDIV-Fehler

Anmerkungen

Verweise

Weiterlesen

• Savard, John JG (2018) [2006]. "Erweiterte Rechentechniken" . quadibloc . Archiviert vom Original am 2018-07-03 . Abgerufen 2018-07-16 .