Zum Inhalt springen

Goldschmidt-Division

aus Wikipedia, der freien Enzyklopädie

Die Goldschmidt-Division ist ein Verfahren, um eine Division in einer digitalen Schaltung schnell und mit geringem Hardwareaufwand zu realisieren.<ref>Applications of Division by Convergence by Robert E. Goldschmidt. Massachusetts Institute of Technology, 1964.</ref> Dabei wird die Division auf eine Multiplikation zurückgeführt, womit bereits evtl. vorhandene Multiplizierer mitverwendet werden können.

Der Ansatz der Goldschmidt-Division ist die Betrachtung der Division als Bruch <math>\tfrac{Z}{N}</math>, welcher so lange mit dem Faktor <math>F_i</math> erweitert wird, bis der Nenner nahe genug an den Wert 1 konvergiert ist. Der Wert des Zählers entspricht somit dann dem Ergebnis der Division.

<math>Q = \frac{Z}{N} \frac{F_1}{F_1} \frac{F_2}{F_2} \frac{F_{\ldots}}{F_{\ldots}}.</math>

Die auszuführenden Schritte sind:

  1. Wähle einen geeigneten Faktor Fi.
  2. Multipliziere Zähler und Nenner mit Fi.
  3. Wenn der Nenner nahe genug an 1 herangekommen ist, gib den Zähler zurück, andernfalls fahre mit Schritt 1 fort.

Sind <math>Z</math> und <math>N</math> so skaliert, dass <math>0 < N < 1</math>, dann können die Erweiterungsfaktoren <math>F_i</math> einfach berechnet werden:

<math>F_{i+1} = 2-N_i.</math>

Damit ergibt sich:

<math>

\frac{Z_0}{N_0} = \frac{Z}{N}, \frac{Z_{i+1}}{N_{i+1}} = \frac{Z_i F_{i+1}}{N_i F_{i+1}}. </math>

Nach einer genügend großen Zahl von Iterationen <math>k</math> ist der gesuchte Quotient <math>Q=Z_k</math>.

Bei der Umsetzung als Schaltung können die Multiplikationen von Nenner und Zähler parallel durchgeführt werden, was eine schnelle Abarbeitung des Algorithmus ermöglicht. Die Goldschmidt-Division wird in den AMD-Athlon-CPUs und späteren Modellen verwendet.<ref>Stuart F. Oberman, "Floating Point Division and Square Root Algorithms and Implementation in the AMD-K7 Microprocessor", in Proc. IEEE Symposium on Computer Arithmetic, S. 106–115, 1999</ref><ref>Peter Soderquist and Miriam Leeser, "Division and Square Root: Choosing the Right Implementation", IEEE Micro, Band 17 No.4, S. 56–66, July/August 1997</ref>

Binomische Formel

Die Faktoren der Goldschmidt-Division können so gewählt werden, dass eine Vereinfachung mit der binomischen Formel möglich ist.

Angenommen <math>\tfrac{Z}{N}</math> wurde mit einer Zweierpotenz so skaliert, dass <math>N\in(\tfrac{1}{2},1]</math>.

Wir setzen <math>N = 1-x</math> und <math>F_{i+1} = 1+x^{(2^i)}</math>.

Dann gilt:

<math>

\begin{align} \frac{Z}{1-x} 

& = \frac{Z\cdot(1+x)}{1-x^2} \\
& = \frac{Z\cdot(1+x)\cdot(1+x^2)}{1-x^4} \\
& \vdots \\
& = \frac{Z\cdot(1+x)\cdot(1+x^2)\dotsm(1+x^{(2^{n-1})})}{1-x^{(2^n)}}

\end{align} </math>

Da <math>x\in[0,\tfrac{1}{2})</math> können wir nach <math>n</math> Schritten <math>1-x^{(2^n)}</math> zu 1 runden. Der maximale relative Fehler ist dabei <math>2^{-(2^n)}</math>, und wir erhalten eine Genauigkeit von <math>2^n</math> Digitalstellen. Dieser Algorithmus wird auch als die IBM-Methode bezeichnet.<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Michael Gregorius|Michael Gregorius: }}{{#if:|{{#if:Theorie des Logikentwurfs|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Theorie des Logikentwurfs}}]{{#if:PDF; 687 kB| (PDF; 687 kB)}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Theorie des Logikentwurfs}}}}|[{{#invoke:URLutil|getNormalized|1=https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Theorie des Logikentwurfs}}}}]}}{{#if:PDF; 687 kB| (PDF; 687 kB{{#if:michaelgregorius.de2003-09-1687f.{{#if: 2024-11-15 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:de|de||{{#if:de|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf}}%7C%7C}}}}{{#if:Theorie des Logikentwurfs|{{#if:{{#invoke:WLink|isValidLinktext|1=Theorie des Logikentwurfs|lines=0}}||}}}}{{#if: michaelgregorius.de| In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=michaelgregorius.de}}}}{{#if: | {{{hrsg}}}{{#if: 2003-09-1687f.|,|{{#if: 2024-11-15 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 2003-09-16| {{#if:{{#invoke:DateTime|format|2003-09-16|noerror=1}}
            |{{#invoke:DateTime|format|2003-09-16|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=2003-09-16|class=Zitationswartung}} }}{{#if: 87f.|,|{{#if: 2024-11-15 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 87f.| S. 87f.{{#if: |,|{{#if: 2024-11-15 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:87f.2003-09-16|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:2072599||(?)}}}}}}{{#if: 2024-11-15|;}}}}{{#if: 2024-11-15| {{#if:87f.2003-09-16{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2024-11-15 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2024-11-15|class=Zitationswartung}} }} {{#invoke:DateTime|format|2024-11-15|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:de|1}}}}|{{#if:michaelgregorius.de2003-09-1687f.{{#if: 2024-11-15 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if:PDF; 687 kB | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|de|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 2003-09-1687f.{{#if: 2024-11-15 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}de|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref>

Ähnliche Verfahren

Einzelnachweise

<references />

en:Goldschmidt division

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Goldschmidt-Division&oldid=2072599“