Quersummenberechnung

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!

SeppJ

rage_quit schrieb:

SeppJ schrieb:

Darf ich als Alternative die Quersumme zur Basis 256 vorschlagen?

für was soll die gut sein?

Wozu soll die Quersumme zur Basis 10 gut sein? Doch wohl als Prüfsumme oder für Teilbarkeitsregeln. Prüfsumme geht mit Basis 256 genauso und Teilbarkeitsregeln entfällt im Gegensatz zum Dezimalsystem "nur" die Teilbarkeit durch 9. Diese kann man durch zweimaliges prüfen der Teilbarkeit durch 3 emulieren. Dafür gewinnt man Teilbarkeitsregeln für 5, 15, 17, 51, 85 und 255.

Heimelchen

Wikipedia sagt übrigens:

Allgemein gilt, dass die Quersumme qn der Darstellung einer Zahl a im Stellenwertsystem mit der Basis n den Rest modulo n − 1 unverändert lässt, also...

Wenn du deine Zahl also Modulo 9 gerechnet kriegst, könntest du daraus die Quersumme berechnen. Das lässt sich auch binär recht einfach tun.

volkard

SeppJ schrieb:

rage_quit schrieb:

SeppJ schrieb:

Darf ich als Alternative die Quersumme zur Basis 256 vorschlagen?

für was soll die gut sein?

Wozu soll die Quersumme zur Basis 10 gut sein? Doch wohl als Prüfsumme oder für Teilbarkeitsregeln. Prüfsumme geht mit Basis 256 genauso und Teilbarkeitsregeln entfällt im Gegensatz zum Dezimalsystem "nur" die Teilbarkeit durch 9. Diese kann man durch zweimaliges prüfen der Teilbarkeit durch 3 emulieren. Dafür gewinnt man Teilbarkeitsregeln für 5, 15, 17, 51, 85 und 255.

Ich wiederhole: "Dafür gewinnt man eine Teilbarkeitsregel für 5".

SeppJ schrieb:

rage_quit schrieb:

SeppJ schrieb:

Darf ich als Alternative die Quersumme zur Basis 256 vorschlagen?

für was soll die gut sein?

Wozu soll die Quersumme zur Basis 10 gut sein? Doch wohl als Prüfsumme oder für Teilbarkeitsregeln. Prüfsumme geht mit Basis 256 genauso und Teilbarkeitsregeln entfällt im Gegensatz zum Dezimalsystem "nur" die Teilbarkeit durch 9. Diese kann man durch zweimaliges prüfen der Teilbarkeit durch 3 emulieren. Dafür gewinnt man Teilbarkeitsregeln für 5, 15, 17, 51, 85 und 255.

hättest du da sowas wie eine tabelle/link? kannte bisher nur die Teilbarkeitsregeln im Dezimalsystem?