Quersummenberechnung
-
SeppJ schrieb:
Signum schrieb:
.-.-.-.-. schrieb:
also ich konnte da nur sowas finden
int digit = MPN.divmod_1(work, work, len, radix);
...nö, die funktion heisst "public String toString(int radix)".
Ich arbeite grundsätzlich mit radix 10. Möchte nur wissen, wer da behauptet
ich würde in einen String umwandeln ohne durch 10 zu teilen.
Genau das ist Bestandteil der Umwandlung, und genau das will ich mir aus performance günden ersparen.Guck dir mal an, wie toString implementiert ist. Was glaubst du denn, was das macht?
Aber da die Stringumwandlung ziemlich viel anderes auch macht, rechne doch einfach direkt! Die Funktion zum teilen ist ja offensichtlich da, denn dein toString benutzt sie ja.
...ochhh Sepp!
Und es stand geschrieben:
"...und genau das will ich mir aus performance günden ersparen"
-
Signum schrieb:
...na gut, Du darfst auch ein Python-Script verwenden, aber bitte posten, damit
ich mir was abgucken kann!
Die Kenntnis des Interfaces ist für die Lösung des Problems übrigens völlig irrelevant.
Ich habe das Gefühl, wir reden hier mächtig aneinander vorbei. Du scheinst von mir zu erwarten, dass ich dir eine Lowlevel-Lösung anbiete, die direkt mit deinen Bytes herumhantiert und damit die Quersumme berechnet. Das hab ich aber nie vorgeschlagen, im Gegenteil.
Du hast gesagt, deine Library kann schon Grundrechenarten. Wir brauchen: Vergleich mit 0, Addition, Modulo und Division. Dann sieht dein Algorithmus so aus:
// Eingabe: N Erzeuge zwei Bignums: X als Kopie von N, Q mit dem Initialwert 0 while (X ist nicht 0) { Inkrementiere Q um den Wert von X modulo 10 Teile X durch 10 } // Ausgabe: QDie natürlichsprachlichen Elemente werden Aufrufe deiner Funktionen, wie auch immer sie heißen,
my_bignum_dividevielleicht. Alles high-level. Dass das so funktionieren muss, zeigt das Python-Script, das ich auf der ersten Seite gepostet habe. Das macht nämlich im wesentlichen auch nichts anderes, hat aber noch einiges an Overhead seitens des Interpreters. Wenn deine Grundoperationen also effizient implementiert sind, solltest du auf ähnliche Laufzeiten kommen.
-
Signum schrieb:
SeppJ schrieb:
Signum schrieb:
.-.-.-.-. schrieb:
also ich konnte da nur sowas finden
int digit = MPN.divmod_1(work, work, len, radix);
...nö, die funktion heisst "public String toString(int radix)".
Ich arbeite grundsätzlich mit radix 10. Möchte nur wissen, wer da behauptet
ich würde in einen String umwandeln ohne durch 10 zu teilen.
Genau das ist Bestandteil der Umwandlung, und genau das will ich mir aus performance günden ersparen.Guck dir mal an, wie toString implementiert ist. Was glaubst du denn, was das macht?
Aber da die Stringumwandlung ziemlich viel anderes auch macht, rechne doch einfach direkt! Die Funktion zum teilen ist ja offensichtlich da, denn dein toString benutzt sie ja.
...ochhh Sepp!
Und es stand geschrieben:
"...und genau das will ich mir aus performance günden ersparen"Nachtrag:
Was hab ich denn von einer Division durch 10?
Das Ergebnis ist eine Zahl in zweier komplement Darstellung und wir stehen wieder am Anfang
-
Signum schrieb:
Nachtrag:
Was hab ich denn von einer Division durch 10?
Das Ergebnis ist eine Zahl in zweier komplement Darstellung und wir stehen wieder am AnfangIch glaube ich kann dir nicht helfen. Du bemühst dich ja noch nicht einmal.
-
faß lieber das mod und div zusammen und rechne das nur 1 mal aus. dann bist ca. doppelt so schnell...
-
Bashar schrieb:
Signum schrieb:
...na gut, Du darfst auch ein Python-Script verwenden, aber bitte posten, damit
ich mir was abgucken kann!Die Kenntnis des Interfaces ist für die Lösung des Problems übrigens völlig irrelevant.
Ich habe das Gefühl, wir reden hier mächtig aneinander vorbei. Du scheinst von mir zu erwarten, dass ich dir eine Lowlevel-Lösung anbiete, die direkt mit deinen Bytes herumhantiert und damit die Quersumme berechnet. Das hab ich aber nie vorgeschlagen, im Gegenteil.
Du hast gesagt, deine Library kann schon Grundrechenarten. Wir brauchen: Vergleich mit 0, Addition, Modulo und Division. Dann sieht dein Algorithmus so aus:
// Eingabe: N Erzeuge zwei Bignums: X als Kopie von N, Q mit dem Initialwert 0 while (X ist nicht 0) { Inkrementiere Q um den Wert von X modulo 10 Teile X durch 10 } // Ausgabe: QDie natürlichsprachlichen Elemente werden Aufrufe deiner Funktionen, wie auch immer sie heißen,
my_bignum_dividevielleicht. Alles high-level. Dass das so funktionieren muss, zeigt das Python-Script, das ich auf der ersten Seite gepostet habe. Das macht nämlich im wesentlichen auch nichts anderes, hat aber noch einiges an Overhead seitens des Interpreters. Wenn deine Grundoperationen also effizient implementiert sind, solltest du auf ähnliche Laufzeiten kommen....genau das wollte ich vermeiden. ich formuliere deinen pseudocode mal um:
Nehme eine beliebig grosse Zahl in zweierkomplement Darstellung in der Form unsigned char magnitude[] Errechne die Quersumme zur Basis 10 ohne div und mod der gesamten magnitude sondern nur mit einer kleinen (mit der kleinsten) Anzahl von elementen aus magnitude. } // Ausgabe:Dies können beliebige shift operationen oder additionen, subtraktionen oder multiplikationen sein, weil diese einfach und schnell sind.
-
Das geht nicht elementar, zumindest nicht mit Basis 10, sondern nur mit Zweierpotenzen als Basis. Der allgemeine Fall (das heißt mit Übertrag und so) ist aber auch nicht langsam, man muss es nur nicht so umständlich machen wie du es vermutlich tust.
Aber wenn es dich so freut, dann guck dir doch mal die Implementierung von divmod_1 an, die dein to_string benutzt. Das arbeitet intern natürlich auch mit Grundrechenarten. Die Sache ist bloß, dass du für die Quersumme nicht drum rum kommen wirst, durch deine Basis zu teilen. Egal ob du selbst den Code für das Teilen schreibst oder den aus der BigInt Bibliothek nimmst.
P.S.: Da ist er:
/** Divide divident[0:len-1] by (unsigned int)divisor. * Write result into quotient[0:len-1. * Return the one-word (unsigned) remainder. * OK for quotient==dividend. */ public static int divmod_1 (int[] quotient, int[] dividend, int len, int divisor) { int i = len - 1; long r = dividend[i]; if ((r & 0xffffffffL) >= ((long)divisor & 0xffffffffL)) r = 0; else { quotient[i--] = 0; r <<= 32; } for (; i >= 0; i--) { int n0 = dividend[i]; r = (r & ~0xffffffffL) | (n0 & 0xffffffffL); r = udiv_qrnnd (r, divisor); quotient[i] = (int) r; } return (int)(r >> 32); }
-
Dann viel Spaß beim Knobeln. Ich dachte, dir käme es darauf an, dass es schneller läuft. Nicht, dass es auf eine bestimmte Art schneller läuft.
-
@SeppJ(ava)
gib doch gleich noch den udiv_qrnnd code mit dann kann man damit auch was anfangen/* Divide (unsigned long) N by (unsigned int) D. 166 * Returns (remainder << 32)+(unsigned int)(quotient). 167 * Assumes (unsigned int)(N>>32) < (unsigned int)D. 168 * Code transcribed from gmp-2.0's mpn_udiv_w_sdiv function. 169 */ 170 public static long udiv_qrnnd (long N, int D) 171 { 172 long q, r; 173 long a1 = N >>> 32; 174 long a0 = N & 0xffffffffL; 175 if (D >= 0) 176 { 177 if (a1 < ((D - a1 - (a0 >>> 31)) & 0xffffffffL)) 178 { 179 /* dividend, divisor, and quotient are nonnegative */ 180 q = N / D; 181 r = N % D; 182 } 183 else 184 { 185 /* Compute c1*2^32 + c0 = a1*2^32 + a0 - 2^31*d */ 186 long c = N - ((long) D << 31); 187 /* Divide (c1*2^32 + c0) by d */ 188 q = c / D; 189 r = c % D; 190 /* Add 2^31 to quotient */ 191 q += 1 << 31; 192 } 193 } 194 else 195 { 196 long b1 = D >>> 1; /* d/2, between 2^30 and 2^31 - 1 */ 197 //long c1 = (a1 >> 1); /* A/2 */ 198 //int c0 = (a1 << 31) + (a0 >> 1); 199 long c = N >>> 1; 200 if (a1 < b1 || (a1 >> 1) < b1) 201 { 202 if (a1 < b1) 203 { 204 q = c / b1; 205 r = c % b1; 206 } 207 else /* c1 < b1, so 2^31 <= (A/2)/b1 < 2^32 */ 208 { 209 c = ~(c - (b1 << 32)); 210 q = c / b1; /* (A/2) / (d/2) */ 211 r = c % b1; 212 q = (~q) & 0xffffffffL; /* (A/2)/b1 */ 213 r = (b1 - 1) - r; /* r < b1 => new r >= 0 */ 214 } 215 r = 2 * r + (a0 & 1); 216 if ((D & 1) != 0) 217 { 218 if (r >= q) { 219 r = r - q; 220 } else if (q - r <= ((long) D & 0xffffffffL)) { 221 r = r - q + D; 222 q -= 1; 223 } else { 224 r = r - q + D + D; 225 q -= 2; 226 } 227 } 228 } 229 else /* Implies c1 = b1 */ 230 { /* Hence a1 = d - 1 = 2*b1 - 1 */ 231 if (a0 >= ((long)(-D) & 0xffffffffL)) 232 { 233 q = -1; 234 r = a0 + D; 235 } 236 else 237 { 238 q = -2; 239 r = a0 + D + D; 240 } 241 } 242 } 243 244 return (r << 32) | (q & 0xFFFFFFFFl); 245 }
-
java_a_a_ schrieb:
@SeppJ(ava)
gib doch gleich noch den udiv_qrnnd code mit dann kann man damit auch was anfangen/* Divide (unsigned long) N by (unsigned int) D. 166 * Returns (remainder << 32)+(unsigned int)(quotient). 167 * Assumes (unsigned int)(N>>32) < (unsigned int)D. 168 * Code transcribed from gmp-2.0's mpn_udiv_w_sdiv function. 169 */ 170 public static long udiv_qrnnd (long N, int D) 171 { 172 long q, r; 173 long a1 = N >>> 32; 174 long a0 = N & 0xffffffffL; 175 if (D >= 0) 176 { 177 if (a1 < ((D - a1 - (a0 >>> 31)) & 0xffffffffL)) 178 { 179 /* dividend, divisor, and quotient are nonnegative */ 180 q = N / D; 181 r = N % D; 182 } 183 else 184 { 185 /* Compute c1*2^32 + c0 = a1*2^32 + a0 - 2^31*d */ 186 long c = N - ((long) D << 31); 187 /* Divide (c1*2^32 + c0) by d */ 188 q = c / D; 189 r = c % D; 190 /* Add 2^31 to quotient */ 191 q += 1 << 31; 192 } 193 } 194 else 195 { 196 long b1 = D >>> 1; /* d/2, between 2^30 and 2^31 - 1 */ 197 //long c1 = (a1 >> 1); /* A/2 */ 198 //int c0 = (a1 << 31) + (a0 >> 1); 199 long c = N >>> 1; 200 if (a1 < b1 || (a1 >> 1) < b1) 201 { 202 if (a1 < b1) 203 { 204 q = c / b1; 205 r = c % b1; 206 } 207 else /* c1 < b1, so 2^31 <= (A/2)/b1 < 2^32 */ 208 { 209 c = ~(c - (b1 << 32)); 210 q = c / b1; /* (A/2) / (d/2) */ 211 r = c % b1; 212 q = (~q) & 0xffffffffL; /* (A/2)/b1 */ 213 r = (b1 - 1) - r; /* r < b1 => new r >= 0 */ 214 } 215 r = 2 * r + (a0 & 1); 216 if ((D & 1) != 0) 217 { 218 if (r >= q) { 219 r = r - q; 220 } else if (q - r <= ((long) D & 0xffffffffL)) { 221 r = r - q + D; 222 q -= 1; 223 } else { 224 r = r - q + D + D; 225 q -= 2; 226 } 227 } 228 } 229 else /* Implies c1 = b1 */ 230 { /* Hence a1 = d - 1 = 2*b1 - 1 */ 231 if (a0 >= ((long)(-D) & 0xffffffffL)) 232 { 233 q = -1; 234 r = a0 + D; 235 } 236 else 237 { 238 q = -2; 239 r = a0 + D + D; 240 } 241 } 242 } 243 244 return (r << 32) | (q & 0xFFFFFFFFl); 245 }...danke für die Mühe, Du hast es aber schon gesagt, dass es elementar wohl nicht gehen wird.
Übrigens ist der Divisor im gepostetem Code ein einfacher datentyp (int). Das entspricht etwa der funktion "divideOneWord()" der Java Klasse MutableBigInteger.
Den Code habe ich schon selbst implementiert. Kann aber keine ints benutzen
sondern nur 'unsigned char'.C Ya
