Quersummenberechnung

Hallo Gemeinde,

suche einen Algo zur Quersummenberechnung.

Problem:
Die Zahl ist kein einfacher Datentyp (BYTE, int, short, ...) sondern
ein beliebig langer integer (siehe java BigInteger), der in zweier
komplement Darstellung (big-endian) in einem BYTE array (unsigned char) vorliegt.

Meine Lösung wandelt das byte array in einen string um und berechnet
daraus die Quersumme zur basis 10. Bei einer Zahl mit 10000 Ziffern
dauert das bei mir ewig lange.

Frage:
gibt es einen Algo, der direkt aus der zweier komplement Darstellung
die Quersumme zur Basis 10 berechnen kann, damit das ein bisschen schneller geht?

Thx
Guest

SeppJ

Wie wäre es, normal zu rechnen, unabhängig von der Darstellung? Den BigInt hast du dir ja sicherlich nicht selbst geschrieben, sondern der kommt doch sicherlich mit ein paar brauchbar flotten Rechenfunktionen die man benutzen kann. Solltest du mal ausprobieren, ob das dann schneller oder langsamer wird. Einen Versuch ist das sicherlich wert, sind schließlich nur ein paar Zeilen Rechnung.
Vermutlich wird die Funktion die den String erstellt jedoch intern ähnlich arbeiten, jedoch sparst du dir dadurch eventuell noch ein paar Rechenschritte die für die Stringerzeugung nicht nötig sind.

Für direkte Berechnung anhand des Zweierkomplements fällt mir nichts ein, denn es gibt keine Zweierpotenz die einer Zehnerpotenz entspricht, so dass irgendwelche Aufteilungstricks nicht funktionieren können.

MaBa

Hallo Signum,

aus dem Zweierkomplement wirst du keine Quersumme (zur Basis 10) berechnen können. Der "Umweg" über den Basiswechsel wird sich nicht umgehen lassen.

Zeig mal deinen Code, vielleicht kann man das ein oder andere optimieren. Threads wären evtl. auch einen Versuch wert. Bei der Quersumme ist das ja leicht machbar.

Viele Grüße,
MaBa

...hmm, schade

Der Code ist in einer Klasse verpackt, die etwa 9000 LOC umfasst, kann das hier
leider nicht alles posten. Auuserdem benutze ich selbstgestrickte Helferklassen
die auch nochmal so eben 500 kB umfassen.

Dank euch trotzdem!

@Sepp:

...doch, alles selber geschrieben!
Lies mal Donald E. Knuth!

Bashar

Was meinst du eigentlich mit "ewig lange"?

...die Quersummenberechnung eines (Big-)Integers mit 32000 mal der 9
(= "999999999....") dauert ca. 2 min.

Bashar

Ich habs grad mal in Python probiert, es dauert weniger als 10 Sekunden mit dem naiven Algorithmus.

N = 10**32000 - 1
sum = 0
while N != 0:
  sum = sum + N % 10
  N = N / 10

Also hast du wohl noch Potential bei der Division.

...sorry, da hast Du was nicht richtig verstanden.
Die interne Darstellung liegt im Zweierkomplement vor:
"unsigned char magnitude[]"

Deine Berechnung geht von der Dezimaldarstellung aus.
Genau das ist ja mein Dilemma.

C Ya

rage_quit

so ein grind... am längsten dauert die umwandlung in eine zeichenkette welche aber in deinen 10ksloc schon dabei sein sollte und bei sowas wie "2132135484" braucht man keine division, modulus oder sonstiges. werds jetzt nicht benchmarken aber das sollte schon schneller gehen als euere 10sek...

ist doch klar schlangen sind eben nicht die schnellsten tiere...

(am besten schnell lesen sonst wirds wieder gelöscht)

Bashar

Signum schrieb:

...sorry, da hast Du was nicht richtig verstanden.
Die interne Darstellung liegt im Zweierkomplement vor:
"unsigned char magnitude[]"

Deine Berechnung geht von der Dezimaldarstellung aus.
Genau das ist ja mein Dilemma.

Meine Berechnung geht nicht von einer bestimmten Darstellung aus. Ich weiß natürlich nicht, wie Python das intern macht, aber die Quersumme zur Basis 13 wird genauso schnell berechnet, damit kann ich eine Dezimaldarstellung ausschließen.

@rage_quit:
Yep, der algo ist dabei und ja, das dauert am längsten.
Genau diesen Schritt will ich mir ja aus preformance gründen ersparen.
Ich dachte, das es mögl. sein könnte, die Quersumme ohne Umwandlung aus
der Zweierkomplement Darstellung zu errechnen.

SeppJ

Signum schrieb:

Der Code ist in einer Klasse verpackt, die etwa 9000 LOC umfasst, kann das hier
leider nicht alles posten. Auuserdem benutze ich selbstgestrickte Helferklassen
die auch nochmal so eben 500 kB umfassen.

Hmm, ich schätze man könnte hier ansetzen. Klingt nach reichlich Overhead und überkompliziert. Jedenfalls würde ich mir Sorgen machen, wenn mein C-Programm von einem Python-Script überholt wird. Die recht verbreitete Großzahlenbibliothek von Matt McCutchen kann auch sehr viel (und ist nicht für Performance berühmt), braucht mit dem naiven Algorithmus aber nur rund 1 Sekunde. Da kann man bei dir garantiert was rausholen, allein schon dadurch dass man den Code entschlackt.

Hast du eigentlich den naiven Algorithmus, wie schon mehrmals vorgeschlagen, bei dir schonmal ausprobiert? Vielleicht ist ja wirklich nur die Stringumwandlung so lahm (auch wenn ich es nicht glaube).

Signum schrieb:

@Sepp:

...doch, alles selber geschrieben!
Lies mal Donald E. Knuth!

Liebend gerne! Aber Herr Knuth hat viel geschrieben. Worauf beziehst du dich genau?

rage_quit

Signum schrieb:

Ich dachte, das es mögl. sein könnte, die Quersumme ohne Umwandlung aus der Zweierkomplement Darstellung zu errechnen.

ja klar, wenn das deine meist ausgeführte berechnung ist bleib doch einfach bei basis 10 statt basis 2

SeppJ

rage_quit schrieb:

Signum schrieb:

Ich dachte, das es mögl. sein könnte, die Quersumme ohne Umwandlung aus der Zweierkomplement Darstellung zu errechnen.

ja klar, wenn das deine meist ausgeführte berechnung ist bleib doch einfach bei basis 10 statt basis 2

Oder wenn ich mal raten darf: Musst du unbedingt die Quersumme zur Basis 10 haben? Klingt irgendwie ungewöhnlich. Darf ich als Alternative die Quersumme zur Basis 256 vorschlagen?

rage_quit

SeppJ schrieb:

Darf ich als Alternative die Quersumme zur Basis 256 vorschlagen?

für was soll die gut sein?

volkard

Außerdem hast Du noch nicht gesagt, wie Du die Quersumme berechnest.
Und die Zeitkomplexität von BigNumMitMStellen/BigNumMitNStellen wäre interessant, um abzuschätzen, ob man was mit divide&conquer machen sollte,
und hast Du für BigNumMitNStellen/10 eine eigene Funktion, damit kein DIV mehr vorkommt?

Heimelchen

Mal zum Verständnis:
Deine Zahl liegt in dieser Form vor?

char MyZahl[] = "100101001101011110011100...11001";

Heimelchen schrieb:

Mal zum Verständnis:
Deine Zahl liegt in dieser Form vor?
char MyZahl[] = "100101001101011110011100...11001";

o herr schenke ihm ein hirn

volkard

Heimelchen schrieb:

Mal zum Verständnis:
Deine Zahl liegt in dieser Form vor?
char MyZahl[] = "100101001101011110011100...11001";

Nein.

struct BigNum{
   char* MyZahl;
...

und
statt
char MyZahl[]="10010100 11010111 10011100 ...11001";//leerzeichen nur zur Verdeutlichung, wo Byte-Grenzen sind.
char MyZahl[]="\224\327\234...1";
oder
char MyZahl[]={148,215,156...};

Heimelchen

Wenn du mich meinst, könntest du deinen Gelatine-Sack mal um eine Erklärung bemühen. Wenn du nicht mich meinst, auch!