Quersummenberechnung

@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?

volkard

Heimelchen schrieb:

Wenn du deine Zahl also Modulo 9 gerechnet kriegst, könntest du daraus die Quersumme berechnen. Ob das schneller geht, ist die große Frage...

Ja, es wäre viel viel schneller. Aber nicht richtig.
qs(16777216)=37 und nicht nur 1.

@bashar
Versuche folgende Quersumme zu berechnen, ohne für magnitude integrale datentypen zu verwenden:

void main(void)
{
unsigned char magnitude[5] = {0x7F, 0x88, 0x32, 0x46, 0x78};
// Dezimal: 547745842808
int size = sizeof(magnitude) / sizeof(magnitude[0]);
int Your_Crossfoot = 0;
int Correct_Crossfoot = 62; // 5+4+7+7+4+5+8+4+2+8+0+8
unsigned char digit;

    // ...so gehts nicht!
    for(int i = 0; i < size; i++)
    {
        digit = magnitude[i];
        while(digit != 0x00)
        {
            Your_Crossfoot += digit % 10;
            digit /= 10;
        }
    }

    assert(Your_Crossfoot == Correct_Crossfoot);
}

@Sepp
Ich benutze die Schoolbook Division nach Donald Knuth "The Art of Computer Programming II"

@Heimelchen
NEIN!

@volkard
Die Division kommt da oft genug vor, genau das will ich vermeiden!
BigNumMitNStellen/10:
Ja, hab eine eigene funktion. Dies ist ein Sonderfall, indem der Divisor geau so gross ist wie ein Byte des Dividenden

SeppJ

401301201 schrieb:

SeppJ schrieb:

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?

Link:
http://de.wikipedia.org/wiki/Quersumme#Quersummensatz

401301201 schrieb:

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?

Na das wäre doch mal ein Ansatz!
Wenn man das Ergebnis der Quersumme einfach ins Dezimalsystem umrechnen kann wäre mir schon geholfen!

SeppJ

volkard schrieb:

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

Ups, ja :p .

Aber immerhin ist die Regel mit der 5 von gänzlich anderer Art in den zwei Fällen. So gesehen würde man mit 256 noch viel mehr Teilbarkeitsregeln bekommen, die dann eben nicht auf der Quersumme beruhen.

Heimelchen

Signum schrieb:

@Heimelchen
NEIN!

Ok, dann lass ich's.