Schriftliche Division zerlegen

prof_maad

Hallo alle miteinander.

Ich habe derzeit ein ziemliches Problem. Ich schreibe derzeit eine Klasse in C++, um mit beliebig großen Ganzzahlen zu rechnen. Also Addition, Subtraktion, Multiplikation und eben auch Division. Die ersten drei waren an sich kein Problem und funktionieren auch schon 1A, nur das letzte macht noch Probleme, und zwar große.

Das ganze basiert darauf, dass ich die Zahlen in Strings speichere und dann mit den schriftlichen Rechenmethoden aus der Grundschule rechne.
Nun ist bei der Division aber das Problem, dass man den Dividend stets durch den vollen Divisor teilen muss.
Soll heißen:
Wenn ich "a" durch "b" schriftlich teilen will, so muss ich dass gesamte "b" benutzen und kann es nicht wie etwa bei der schriftlichen Multiplikation vorher zerlegen. (Multiplikation: Der 1. von "b" wird mit dem 1. von "a" multipliziert etc.)

Genau dass geht jedoch nicht, da der Divisor ja auch mal 100 Stellen haben kann und soviel kann kein INT-Wert aufnehmen. (Weshalb ich mir ja die Klasse schreibe).

Nun meine eigentliche Frage:

Gibt es irgendeine Möglichkeit, die Rechnung so zu "zerlegen", dass der Divisor garantiert nicht größer als 1-2 Stellen wird?

Ich bin dankbar für jede schlaue Idee.

Danke im Voraus,

Prof. MAAD

Ja, siehe z.B. TAoCP, Vol. 2.

Dommel

hi,

könntest du statt einer Division nicht eine Subtraktion machen...
Soll heißen, dass du den Divisor so lange vom Dividenden abziehst, wie es geht(d.h. solange, bis eine Subtraktion ne negative Zahl ergeben würde)

Das kannst du dann ja noch so aufteilen, wie bei der schriftlichen Division; also dass du das nicht mit der kompletten Zahl machst, sondern immer nur mit Teilen des Dividenden, wie bei der schriftlichen Division halt...

So hab ichs zumindest mal gemacht und es hat auch ganz gut funktioniert...

Jester

Dommel: das wird aber teuer.

"Ganz große Zahl" / 3 oder so dürfte den Rechner dann ne Weile beschäftigen.

Dommel

Deswegen soll er es ja auch wie bei der schriftlichen Division machen, dann gehts zumindest schonmal n bischen schneller.

Bsp: 4532 / 3 = 1510

statt jetzt aber die 3 1510 mal abzuziehen macht er erst

4 / 3 = 1 R 1
15 / 3 = 5 R 0
3 / 3 = 1 R 0
2 / 3 = 0 R 2

jetzt hätte er die 3 nur 7 mal abgezogen

prof_maad

Danke erstmal für die schnellen Antworten.

Noch ne Frage zu Dommels Vorschlag:

Wie kommt du auf diesen Teil?:

4 / 3 = 1 R 1
15 / 3 = 5 R 0
3 / 3 = 1 R 0
2 / 3 = 0 R 2

Alles bis auf "15/3" kann ich mir ja noch erklären, aber wie kommst du auf die 15?

Danke im Voraus,

Prof. MAAD

Daniel E.

Wegen Rest eins. Schau dir die schriftliche Division noch mal an.

Genau dass geht jedoch nicht, da der Divisor ja auch mal 100 Stellen haben kann und soviel kann kein INT-Wert aufnehmen. (Weshalb ich mir ja die Klasse schreibe).

Wo ist den das Problem. Nimm doch einfach ein Object deiner eigenen Klasse um das Ergebnis aufzunehmen. (Dafür ist die Klasse doch da!?)

Dommel

MisterX schrieb:

Genau dass geht jedoch nicht, da der Divisor ja auch mal 100 Stellen haben kann und soviel kann kein INT-Wert aufnehmen. (Weshalb ich mir ja die Klasse schreibe).

Wo ist den das Problem. Nimm doch einfach ein Object deiner eigenen Klasse um das Ergebnis aufzunehmen. (Dafür ist die Klasse doch da!?)

Das Problem ist, dass auch bei der normalen schriftlichen Division geteilt werden muss. Und zwar mit Zahlen, die so groß wie der Divisor sind...

volkard

das beispiel war mist. durch ne einstellige zahl teilen geht halbschriftlich und ist nie ein problem.
ne 20-stellige durch ne 10-stellige, da wird es lustig.

ich empfehle dem ungeübten algorithmiker die in anlehnung an die russische bauernmethode folgendes vorgehen:

123456789/12345
erstmal die 12345 so lange verdoppeln, bis sie größer als die hälfte von 123456789 ist. also wird aus 12345 mal schnell 101130240. dann subtrahieren, halbieren, subtrahieren, halbieren...

sub:
 123456789
-101130240
 ---------
  22326549

halb:
  50565120

sub geht net. 

halb:
  25282560

sub geht net. 

halb: 
  12641280

sub:
 22326549
-12641280
 --------
  9685269

und so weiter.

naja, und immer, wenn subtrahierne ging, fällt ne 1 raus, ansonsten ne 0 und die rausgefallenen ziffern sind das ergebnis in binärdarstellung.

wenn ich recht abschätze, braucht man O(n^2) schritte, also wird einem noch nicht mal übel, wenn man das verfahren mit dem aus der schule vergleicht.

Dommel

@volkard:

hab deinen Algo mal mit der Hand ausprobiert:

52312 / 168 = 311 => 100110111

Allerdings bekomme ich folgendes:
100110111011001

Also sozusagen 6 Stellen zuviel. Habs jetzt halt so lange gemacht, bis bei ner Subtraktion 0 rauskam...
Woran liegt das??

PS: Wenn man die Zahl im Dezimalsystem dargestellt hat, ist diese Methode aber eigentlich nicht so toll, oder?? Man kann die Zahlen nämlich nicht durch 2 teilen, da man ja gerade ne Funktion zum Teilen schreiben will
Deine Methode ginge also nur, wenn man die Zahlen auch im Binärsystem hat...

Edit: Kleiner Rechenfehler
Jetzt kann man die ersten 9 Stellen von vorne oder von hinten nehmen... Komisch...

volkard

Dommel schrieb:

@volkard:
hab deinen Algo mal mit der Hand ausprobiert:
52312 / 168 = 311 => 100110111

Allerdings bekomme ich folgendes:
100110111011001

Also sozusagen 6 Stellen zuviel. Habs jetzt halt so lange gemacht, bis bei ner Subtraktion 0 rauskam...
Woran liegt das??

du sollst nicht so lange machen, bis ne 0 rauskommt, sondern nur so oft halbieren, wie du am anfang verdoppelt hast (oder isses einmal mehr)?

PS: Wenn man die Zahl im Dezimalsystem dargestellt hat, ist diese Methode aber eigentlich nicht so toll, oder?? Man kann die Zahlen nämlich nicht durch 2 teilen, da man ja gerade ne Funktion zum Teilen schreiben will

in der tat, da ist sie nicht so toll. um sie ans dezimalsystem anzupassen, muß man schon recht verzweifelt sein.

ich teile 52312 / 311.

311 plutimiziere ich solange mit 10 wie es geht, um noch <= 52312 zu bleiben. 
3110
31100

nu substrahiere ich die 31100 so oft wie möglich. 
52312 - 31100 = 21212
das war's schon. ich konnte [b]1[/b]-mal subtrahieren. 

nu substrahiere ich die 3110 so oft wie möglich. 
21212 - 3110 = ...
= 2552
das war's schon. ich konnte [b]6[/b]-mal subtrahieren. 

nu substrahiere ich die 311 so oft wie möglich. 
2552 ...
das war's schon. ich konnte [b]8[/b]-mal subtrahieren. 

ergebnius ist also [b]168[/b]

Jester

Dommel schrieb:

PS: Wenn man die Zahl im Dezimalsystem dargestellt hat, ist diese Methode aber eigentlich nicht so toll, oder?? Man kann die Zahlen nämlich nicht durch 2 teilen, da man ja gerade ne Funktion zum Teilen schreiben will

Hatten wir nicht weiter vorne festgestellt, daß Dividieren durch einstellige Zahlen eh einfach ist?

prof_maad

Hallo allemiteinander,

ich danke euch allen ganz doll für die Ideen.

Ich habe mich nun für Volkards letzte Methode entschieden und sie schon fertig implementiert.

Es funktioniert 1A. Vielen Dank für diese Idee.

Wer sich das Ergebnis, sprich meine fertige Klasse, mal angucken will:
http://profmaad.pr.funpic.de/onoint/

Danke euch allen,

Prof. MAAD

Dommel

Hab nochmal ne Verständnis-Frage:

Im Prinzip ist Volkards Algorithmus doch sehr ähnlich zum schriftlichen Dividieren, oder??

Der Unterschied besteht nur darin, dass er den Divisor "verschiebt", indem er mal 2 (bzw. 10 im Dezimalsystem) nimmt, und somit mit dem gesamten Dividenden rechnen kann. In der schriftlichen Division wirds halt nur anders herum gemacht, indem man den Divisor unverändert lässt und nur einen Teil des Dividenen betrachtet (ihn also teil, wenn man so will)...

henriknikolas

volkard schrieb:

Dommel schrieb:

@volkard:
hab deinen Algo mal mit der Hand ausprobiert:
52312 / 168 = 311 => 100110111

Allerdings bekomme ich folgendes:
100110111011001

Also sozusagen 6 Stellen zuviel. Habs jetzt halt so lange gemacht, bis bei ner Subtraktion 0 rauskam...
Woran liegt das??

du sollst nicht so lange machen, bis ne 0 rauskommt, sondern nur so oft halbieren, wie du am anfang verdoppelt hast (oder isses einmal mehr)?

PS: Wenn man die Zahl im Dezimalsystem dargestellt hat, ist diese Methode aber eigentlich nicht so toll, oder?? Man kann die Zahlen nämlich nicht durch 2 teilen, da man ja gerade ne Funktion zum Teilen schreiben will

in der tat, da ist sie nicht so toll. um sie ans dezimalsystem anzupassen, muß man schon recht verzweifelt sein.

ich teile 52312 / 311.
311 plutimiziere ich solange mit 10 wie es geht, um noch <= 52312 zu bleiben. 
3110
31100

nu substrahiere ich die 31100 so oft wie möglich. 
52312 - 31100 = 21212
das war's schon. ich konnte [b]1[/b]-mal subtrahieren. 

nu substrahiere ich die 3110 so oft wie möglich. 
21212 - 3110 = ...
= 2552
das war's schon. ich konnte [b]6[/b]-mal subtrahieren. 

nu substrahiere ich die 311 so oft wie möglich. 
2552 ...
das war's schon. ich konnte [b]8[/b]-mal subtrahieren. 

ergebnius ist also [b]168[/b]

Ich weiß, der Thread ist schon ein bisschen älter :D: , aber das ist genau das, was ich gesucht habe, vielen dank volkard ich war echt schon am verzweifeln