PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Wie werden Integer dividiert?

Pinoccio
2004-06-15, 18:48:36
Hallo,

mir lief heute in der Uni obige Frage über den Weg, habe leider im Netz nix gefunden, daher die Frage an die Cracks hier: Wie werden Integer intern in der CPU dividiert?

Bitte von sinnlosen Beiträgen abzusehen!

mfg
Muh-sagt-die-Kuh
2004-06-15, 18:58:36
Wenn ich mich recht entsinne funktioniert das durch wiederholte Subtraktion:

1. Initial: Quotient=0, Divisor: in 64-bit Divisor Register
Rest-Register initialisiert mit Dividend

2. Shift Quotient-Register um eine Bitposition nach links

3. Subtrahieren Divisor von Dividend:

falls Ergebnis positiv, dann schreibe eine 1 in least significant Bit des Quotient-Registers

anderenfalls: 0 in east significant Bit des quotient-Registers und alten Wert wieder herstellen

4. Rechtsshift des Divisors um ein Bit und gehe zu Schritt 2
Gast
2004-06-15, 19:26:24
Hab nach kurzem Googeln zb. das hier gefunden.

http://babbage.clarku.edu/~jbreecher/public/2002_comp_org/lectures/Chapter4.2-Mult-Div-Flt.ppt
Gast
2004-06-15, 19:30:05
http://science.kennesaw.edu/~khoganso/CS8421/cpu-instructions.ppt

Das ist auch nicht schlecht.
Pinoccio
2004-06-15, 20:13:16
@Muh-sagt-die-Kuh: hm, sowas dachte ich mir. Die Quellen die ich fand, gingen auch in diese Richtung. Danke.

@Gast: ppt? Iss nich dein Ernst?

mfg
Gast
2004-06-15, 20:28:20
Original geschrieben von Pinoccio
@Gast: ppt? Iss nich dein Ernst?

mfg Sebastian

Warum sollte das nicht mein Ernst sein?
Pinoccio
2004-06-15, 20:52:34
Weil:
1. ppt ist powerpoint, das hab ich nicht.
2. ppt ist schlecht (http://www.heise.de/newsticker/result.xhtml?url=/newsticker/meldung/42928&words=Powerpoint)
3. ppt ist groooß.

Reicht das?

mfg
HellHorse
2004-06-15, 23:35:22
Genau
Macht korrumpiert, PowerPoint korrumpiert absolut.
Zool
2004-06-16, 08:48:21
PPT-Files lassen sich auch mit OpenOffice lesen. Ansonsten gibt es vom M$ eien freiverfügbaren Powerpoint-Viewer.
zeckensack
2004-06-16, 18:44:27
http://www.forum-3dcenter.org/vbulletin/showthread.php?postid=1829626#post1829626
Pinoccio
2004-06-16, 20:00:32
Original geschrieben von zeckensack
http://www.forum-3dcenter.org/vbulletin/showthread.php?postid=1829626#post1829626

Ui, wie peinlich, ein Fred in dem ich sogar was gepostet hatte ...
Danke!
Und da hier offenbar so viel Profis rumhängen, wie sieht es da mit der Zeitkomplexität aus?
Bei n Bit Dividend und m Bit Divisor? O(n*m)? oder besser?

mfg
zeckensack
2004-06-16, 20:15:21
Original geschrieben von Pinoccio
Ui, wie peinlich, ein Fred in dem ich sogar was gepostet hatte ...
Danke!
Und da hier offenbar so viel Profis rumhängen, wie sieht es da mit der Zeitkomplexität aus?
Bei n Bit Dividend und m Bit Divisor? O(n*m)? oder besser?

mfg Sebastian Formal O(n), wobei n dem höchstwertigen Bit des Dividenden entspricht. Wenn ich mal meiner eigenen (zugegeben leicht blöden) Formulierung folge, dann O(n-m).

Ausufernd formal und blöd O(n-m+c) :naughty: