Division mit Rest bei großen unsigned Integer
-
Hallo!
ich brauche mal etwas Hilfe. Und zwar programmiere ich derzeit eine Klasse, die große (unsigned) Integer speichern und verarbeiten kann.
Addition, Subtraktion, Multiplikation hab ich schon, habe mich da meistens nach "The art of computer programming" von Donald Knuth gerichtet.
Die Division bekomme ich aber einfach nicht hin.
Ich brauche irgendwas das schneller ist alsXInt slowdiv(const XInt& a, const XInt& b, XInt& r) { XInt q(XInt::xIntZero); r=a; while(isGeq(r,b)) { r -= b; q++; } return q; }Die Zahlen sind dabei durch ihre Dezimalziffern in einem int-Array gespeichert.
Bitte gebt mir ein paar Tips, wie ich es wenigstens etwas effizienter implementieren kann, der Algorithmus von Knuth will bei mir einfach nicht funktionieren!
Ich hoffe es kann mir jemand helfen, ich bin langsam am verzweifeln.Viele Grüße
Edit: Ich habe mir GMP und ähnliche Bibliotheken schon angesehen, allerdings ist es die Aufgabe, es selbst zu implementieren. Die meisten Funktionen davon brauche ich auch nicht.
-
-
Ehrlich gesagt sehe ich nicht, was du mir mit dem Link sagen möchtest bzw wie ich damit eine effiziente Berechnung des Quotienten und des Restes implementieren könnte?
-
Sorry, mir war so, als könnte man damit auch den Divisionsrest berechnen.
-
Ich weiß nicht ob die Idee sinnvoll ist aber wenn man sich die Zahlen Binär ansieht.
123123756861160068415 1101010110010101111011101001000011100010001000000101001010100111111 / 19 10011 Zählt man die Anzahl der Binärstellen die 19 kleiner ist. 1101010110010101111011101001000011100010001000000101001010100111111 0000000000000000000000000000000000000000000000000000000000000010011 = 62 stellen Dann schiftet man die 19 62 stellen nach links (was einem 19*2^62 gleichkommt) = 87622034350120370176 Testen ob resultierende zahl größer ist Nein -> subtraktion Ja -> 19 nur um 61 stellen shiften in unserem fall -> nein 123123756861160068415 - 87622034350120370176 = 35501722511039698239 -> 11110110010101111011101001000011100010001000000101001010100111111 00000000000000000000000000000000000000000000000000000000000010011 60 stellen 19 um 60 stellen shiften = 21905508587530092544 > 35501722511039698239 ? -> nein 35501722511039698239 - 21905508587530092544 = 13596213923509605695 -> 1011110010101111011101001000011100010001000000101001010100111111 0000000000000000000000000000000000000000000000000000000000010011 59 Stellen 19 um 59 stellen shiften = 10952754293765046272 > 13596213923509605695 ? -> nein 13596213923509605695 - 10952754293765046272 = 2643459629744559423 -> 10010010101111011101001000011100010001000000101001010100111111 00000000000000000000000000000000000000000000000000000000010011 57 stellen ... Quotient = 2^62 + 2^60 + 2^59 + 2^57 + ...Bei dieser Methode hat man im schlimmsten Fall:
0xFF = 255 = 11111111 / 0x01 = 1 = 1Was 8 Schleifendurchgänge wären. Ist also im schlimmsten Fall immer noch um das 32 fache schneller als subtrahieren
(was 256 Schleifendurchgänge wären)Eine bessere Lösung fällt mir jetzt nicht ein (gibts aber sicher)
Keros
-
Für die Binäroperationen müsste ich alle Zahlen (die ja gerne mal 100 Dezimalstellen haben können) erst transformieren.
Ich habe versucht, den Algorithmus von Seite 60 aus dem Buch "A Computational Introduction to Number Theory and Algebra" von http://shoup.net/ntb/ zu implementieren, allerdings funktioniert es überhaupt nicht, wäre vielleicht jemand so nett, und könnte mal drüber sehen?
Hier meine Implementation:
// division with remainder // cf. Shoup: "A computational introduction to number theory and algebra" XInt div1(const XInt& a1, const XInt& b1, XInt& r) { XInt q, a(a1), b(b1); int carry = 0, tmp = 0; int rdC, qdC, d, base = 10; if(isGreater(b,a)) { q = XInt::xIntZero; r = a; return q; } if(q.digitCount < a.digitCount+2) q.setLength(a.digitCount+2); if(r.digitCount < a.digitCount+2) r.setLength(a.digitCount+2); // normalize: b_(n-1) >= base/2 d = 1; while(b.digits[b.digitCount-1]*d < base/2) { d++; } b *= d; a *= d; for(int i=0; i<a.digitCount; i++) r.digits[i] = a.digits[i]; r.digits[a.digitCount] = 0; for(int i=a.digitCount-b.digitCount; i>=0; i--) { q.digits[i] = (int)((r.digits[i+b.digitCount]*base + r.digits[i+b.digitCount-1]) / b.digits[b.digitCount-1]); if(q.digits[i] >= base); q.digits[i] = base-1; carry = 0; for(int j=0; j<b.digitCount; j++) { tmp = r.digits[i+j] - (q.digits[i]*b.digits[j]) + carry; carry = tmp/base; r.digits[i+j] = tmp%base; } r.digits[i+b.digitCount] += carry; while (r.digits[i+b.digitCount] < 0) { carry = 0; for(int j=0; j<b.digitCount; j++) { tmp = r.digits[i+j] + b.digits[j] + carry; carry = tmp/base; r.digits[i+j] = tmp%base; } r.digits[i+b.digitCount] += carry; q.digits[i] -= 1; } } //to do: unnormalize remainder //calculate digitCount rdC = r.digitCount; qdC = q.digitCount; r.digitCount = 1; //b.digitCount; q.digitCount = 1; //a.digitCount-b.digitCount; for(int i=rdC-1; i>=0; i--) if(r.digits[i] != 0) { r.digitCount = i+1; } for(int i=qdC-1; i>=0; i--) if(q.digits[i] != 0) { q.digitCount = i+1; } r.digitCount = b.digitCount; return q; }Vielen Dank schonmal und schöne Grüße!
-
Viel zu viel Code mit viel zu viel nichtssagendem Zeug. Ergo: Niemand wird es sich ansehen.
Mein Tipp: Gehe den Algorithmus mit einfachen Zahlen auf dem Papier durch.
-
Athene schrieb:
...
Zwar schön das du dir so Mühe gegeben hast, aber keine Sau, wie The-Kenny schon meinte, wird sich das anschauen. Ich hab nur drüber gescrollt und hab fast das, entschuldigung für meine Ausdruckweise, gekotzt, weil das einfach zu kryptisch aussieht und man erstmal Minuten lang brauch, ein paar Zeilen zu verstehen.