Implementierung einer Datenstruktur für beliebig große Zahlen in C

CypherL0rd · Okt 10, 2017

ich habe eine frage zwecks der bignum programmieraufgabe (siehe [leicht bis schwer] BigNum selbstgemacht ) die ich nun angefangen habe zu lösen.
ich hoffe das mir wer ernsthaft dabei hilft.
ich poste mal meinen code, muss aber dazu sagen dass das erst der anfang der lösung ist, eigentlich nur ein erster test für die addition, da wird sich noch einiges ändern also keine angst.
nur dass das mal gesagt wurde, bevor mein code wieder in der luft zerrissen wird...

also die funktion convert() funktioniert definitiv, habe ich schon getestet, aber bei der stelle "printf("%s + %s = %s\n", zahl1.content, zahl2.content, zahl3.content);" und dem damit einhergehenden funktionsaufruf von addition() stimmt etwas nicht.
denn wenn ich diese zeile im code lasse, kommt ein falsches ergebnis raus und ich weiss nicht warum.
deswegen hoffe ich das jemand erkennt was der fehler ist und mir helfen tut

Code:

#include <stdio.h>
#include <stdlib.h>

struct number {
    char *content;
    int length;
};

char *convert(char numstring[], int length) {
    char *num;
    num = calloc(length, sizeof(char));
    for(int i=0; i<length; i++) {
        num[i] = numstring[i];
    }        
    return num;
}

char *addition(char *num1, char *num2, int length) {        // voraussetzung: num1 geq num2
    char *newnum;
    newnum = calloc(length + 1, sizeof(char));
    int c = 0, tmp;                                            // c = übertrag
    for(int i=length-1; i>0; i--) {
        if(tmp = ((int) num1[i] + (int) num2[i] + c) > 9) {
            newnum[i] = tmp - 10;
            c = 1;
        } else {
            newnum[i] = tmp;
            c = 0;
        }
    }
    if (c > 0) 
        newnum[0] = 1;
    else {
        char *newnewnum;
        newnewnum = calloc(length, sizeof(char));
        for (int i=0; i<length; i++) {
            newnewnum[i] = newnum[i+1];
        }
        free(newnum);
        return newnewnum;
    }
    return newnum;
}


int main() {
    struct number zahl1;
    zahl1.content = convert("123456789", 9);
    
    struct number zahl2;
    zahl2.content = convert("987654321", 9);
    
    struct number zahl3;
    zahl3.content = addition(zahl1.content, zahl2.content, 9);
    
    printf("%s + %s = %s\n", zahl1.content, zahl2.content, zahl3.content); 
        
    return 0;
}

also das ist nur die erste struktur, das mit 4^4096 usw und multiplikationen mache ich dann alles noch in extra funktionen, aber eins nach dem andren.

CDW · Okt 10, 2017

CypherL0rd hat gesagt.:
also die funktion convert() funktioniert definitiv, habe ich schon getestet, aber bei der stelle "printf("%s + %s = %s\n", zahl1.content, zahl2.content, zahl3.content);" und dem damit einhergehenden funktionsaufruf von addition() stimmt etwas nicht.
denn wenn ich diese zeile im code lasse, kommt ein falsches ergebnis raus und ich weiss nicht warum.

Du versuchst Zeichen zu addieren. Also '9' + '2'. Heraus kommt natürlich ein Zeichen.

Ich würde vorschlagen, convert zumindest so zu modifizieren:

Code:

char *convert_from_str(char numstring[], int length) {
    char *num;
    num = calloc(length, sizeof(char));
    for(int i=0; i<length; i++) {
        num[i] = numstring[i] - '0';
    }        
    return num;
}

Es fehlt hier noch eine (simple) Prüfung der Eingabe, z.B dass es sich um Zeichen '0' bis '9' handelt.

Natürlich braucht man auch eine Rückübersetzung:

Code:

/* inplace */
char* convert_to_str(char numstring[static 1], size_t length) {
    for (size_t i = 0; i < length; ++i) {
        numstring[i] += '0';
    }
    return numstring;
}

Bei der Addition sollte man Compilerwarnungen nicht ignorieren:

Code:

 warning: suggest parentheses around assignment used as truth value [-Wparentheses]
         if( tmp = ((int) num1[i] + (int) num2[i] + c) > 9) {

Ich glaube nicht wirkich, dass du in tmp das Vergleichsergebnis OP > 9 haben (also 0/1) willst, also wird

Code:

 if(tmp = ((int) num1[i] + (int) num2[i] + c) > 9)

zu

Code:

 if( (tmp = ((int) num1[i] + (int) num2[i] + c)) > 9)

Bleibt noch die main Modifizierung:

Code:

int main() {
    struct number zahl1;
    zahl1.content = convert_from_str("123456789", 9);
    zahl1.length = 9;
    
    struct number zahl2;
    zahl2.content = convert_from_str("987654321", 9);
    zahl2.length = 9;
    struct number zahl3;
    zahl3.content = addition(zahl1.content, zahl2.content, 9);
    zahl3.length = 9; /* ? unknown */
    printf("%.*s + %.*s = %.*s\n", zahl1.length, convert_to_str(zahl1.content, zahl1.length), 
                             zahl2.length, convert_to_str(zahl2.content, zahl2.length),
                             zahl3.length, convert_to_str(zahl3.content, zahl3.length)
          );
    free(zahl1.content);                                                                                               
    free(zahl2.content);                                                                                               
    free(zahl3.content)       
    return EXIT_SUCCESS;
}

Pik-9 · Okt 10, 2017

Hallo CypherL0rd,

ich sehe da mehrere systematische Probleme:

Wenn du eine Nummer als String einliest, kopierst du einfach die Chars in deine Zahlenstruktur. Dabei musst du aber bedenken, dass das Zeichen '1' nicht dem Byte 1 entspricht, sondern 49. Du rechnest also mit völlig falschen Zahlen!
Du vermischst hier die Zahlensysteme: Du hältst jeweils ein Byte für eine dezimale Ziffer vor. Das kann prinzipiell funktionieren, wenn es konsequent durchgezogen wird, obwohl es sehr ineffizient ist, da der Prozessor letzten Endes am besten (nur) im Binärsystem rechnen kann.
Aus Problem #2 resultieren auch weitere Probleme mit deiner Additionsfunktion: Du hast eine Variable für den Übertrag c angegeben, diese speichert aber nur 1 oder 0. Das ist genau richtig im binären System, aber du rechnest ja dezimal - d.h. c muss ebenfalls den Übertrag im dezimalen System beinhalten. Wie viele du "im Sinn" hast - also genau wie in der Grundschule. :wink:
Um deine Ziffer nach dem Übertrag zu erhalten musst du die höchste darstellbare Ziffer in deinem verwendeten Zahlensystem (also 9 im Dezimalsystem) abziehen und nicht 10 (dezimal). Besser noch wäre modulo 10.

Diese Probleme konnte ich auf den ersten Blick sehen, vielleicht fällt mir ja noch mehr auf - möglicherweise sogar ein Verbesserungsvorschlag.

Viele Grüße,
Pik-9

Edit: Immer läuft das auf ein Wettrennen zwischen @CDW und mir hinaus... Diesmal war er wieder schneller...

CDW · Okt 11, 2017

Pik-9 hat gesagt.:
Edit: Immer läuft das auf ein Wettrennen zwischen @CDW und mir hinaus... Diesmal war er wieder schneller...

Du hast allerdings recht, dass die Addierfunktion so nicht wirklich funktionieren kann - die Zahlen werden "rückwärts" durchlaufen, beim kopieren am Ende wird eine Stelle "verschlückt".
Aaaber:

Du hast eine Variable für den Übertrag c angegeben, diese speichert aber nur 1 oder 0.

0 oder 1 sollte schon für die Addition zweier Zahlen im dez. System stimmen:
9 + 9 = 18 => 8, übertrag 1, 9 + 9 + 1 => 19, übertrag 1.
Größer als 1 sollte es nicht werden können

(also 9 im Dezimalsystem) abziehen und nicht 10 (dezimal). Besser noch wäre modulo 10.

*hust* 6 + 6 = 12, 12 - 9 = 3, 12 mod 10 = 2

Shalec · Okt 11, 2017

Anmerkungen für "further work":

Häufig möchtest du mit dem Ergebnis einer Addition oder Multiplikation weiter rechnen. Wie möchtest du zukünftig das Ergebnis dann in einer Variable speichern? Klar geht
Code:
```
number A,B; 
A.length=10;
B.length=10; 
char Sum[A.length + "Übertrag"];
```
Aber du siehst eben, dass du nie wissen kannst, wie groß dein Übertrag exakt ist. Im Worstcase hast du als Input "9999999 = 0x0098 967F = 0b100110001001011001111111" und möchtest diese Zahl verdoppeln. Veroppeln ist normalerweise einfach ein Leftshift um 1 Bit. Also
Code:
```
0b100110001001011001111111 << 1 //=0b1001100010010110011111110 = 0x0131 2CFE = 19999998
```
Jetzt vergleichen wir: count_digits( 19 999 998 )= 8, und count_digits( 9 999 999 ) = 7. Du siehst also, dass du bei der Addition im Worstcase (nach deiner Eingabe) maximal einen Übertrag hast. Bei der Multiplikation wird aus der Länge "n" direkt "2n-1". Wobei das eben auch ein "bis zu" bedeutet. Diese Überlaufbehandlung musst du also äußerst gewissenhaft implementieren.
Dein implementiertes Carry-handling sieht aber für diesen Fall ganz brauchbar aus.
Je nach verwendeter Hardware ist es nicht performant eine 32-Bit große Zahl in in seine Dezimaldarstellung zu zerlegen und mit diesen Lettern zu rechnen. Auf meinem Mikrocontroller (ARM Cortex M4) z.B. ist die Multiplikation zweier vorzeichenloser 32-Bit Zahlen in Hardware implementiert und benötigt exakt einen Cycle. Zerlegst du also die Zahl in seine dezimale Darstellung, benötigst du bereits bei der Multiplikation (2^32-1 = 4 294 967 295) wesentlich mehr Cycles, z.B. 10^2 Multiplikationen und 9^2 Additionen (bei der Schulbuchmultiplikation) von Zahlen bis 4 Bit. Wo also eine 32-Bit Darstellung 1 Cycle verbraucht, landest du bei 181 cycles.

Möchtest du egtl. nur das BigNum-Problem implementieren und eine gewöhnliche Addition beliebig langer Zahlen erwirken oder am Ende auch modulo beliebig großer Primzahlen rechnen?

Nachtrag: An #3 siehst du z.B. wie wichtig es ist, sich mit der Architektur des Zielsystems auseinander zu setzen. Es gibt viele "eine" Lösungen, aber nur "die" Schnellste

CypherL0rd · Okt 11, 2017

danke erstma für die hilfe leutz :thumb_up:

ihr habt recht, das ist ziemlich undurchdacht und fehleranfällig, mein konzept.

so ist das halt wenn man mit python anfängt und dann über java zu c kommt: es ist als würden einem zum ersten mal die schwimmflügel abgenommen und von jetzt an muss man sich selbst drum kümmern über wasser zu bleiben

CDW hat gesagt.:
Ich würde vorschlagen, convert zumindest so zu modifizieren:

Code:

char *convert_from_str(char numstring[], int length) { char *num; num = calloc(length, sizeof(char)); for(int i=0; i<length; i++) { num[i] = numstring[i] - '0'; } return num; }

was genau ist denn der sinn dahinter '0' von einem einzelnen char abzuziehen?

CDW hat gesagt.:
Bei der Addition sollte man Compilerwarnungen nicht ignorieren:

Code:

warning: suggest parentheses around assignment used as truth value [-Wparentheses] if( tmp = ((int) num1[i] + (int) num2[i] + c) > 9) {

komischweise hat mein compiler diese warnungen nicht angezeigt und alles ohne zu murren kompiliert.

das ist eh so eine sache, mit den neuen verbesserungen im code compilet er jetzt zwar wieder den code, aber wenn ich ihn ausühren will,
springt antivir an und schiebt die erstellte exe in quarantäne.. ich benutze mingw als compiler, also gcc für windows sozusagen.

Shalec hat gesagt.:
Möchtest du egtl. nur das BigNum-Problem implementieren und eine gewöhnliche Addition beliebig langer Zahlen erwirken oder am Ende auch modulo beliebig großer Primzahlen rechnen?

ich hatte eigentlich nur vor bignum zu implementieren, aber ich checke jetzt langsam selbst nicht mehr durch meinen code salat plus compileproblemen..

CDW · Okt 12, 2017

CypherL0rd hat gesagt.:
Code:

was genau ist denn der sinn dahinter '0' von einem einzelnen char abzuziehen?

Der Sinn ist in der Darstellung der Zeichen - für Zahlen werden in den üblichen Kodierungen (ASCII, Unicode, usw) die Werte 48 bis 57 benutzt:
American Standard Code for Information Interchange – Wikipedia
List of Unicode characters - Wikipedia
Mit diesen Kodierungswerten alleine kann der Rechner noch nichts anfangen, dafür hat er Schriftarten (Fonts), die (grob und vereinfacht gesagt) eine Ansammlung von Bildern und einer Tabelle mit der Zuordnung "Wert" <-> "Bild" sind.
D.h. im Char-Array "0123" befinden sich in Wirklichkeit die Werte {48,49,50,51} und bei der Ausgabe wird (letztenendes) für jeden dieser Werte einfach ein entsprechendes Bild auf dem Monitor gezeichnet '0', '1', '2'.

C ist eher schwachtypisiert und die Zeichenliterale ('x','1','y','a','b') entsprechend im Code direkt, ohne Umwandlung, dem jeweiligen Zeichenkodierungswert (man braucht also kein ord('3') oder .getnumericValue() wie in Python/Java usw.).
Für uns ist es wichtig, dass die Werte der Zeichenkodierung für Zahlen kontinuierlich, also ohne Lücken sind, so dass wir für die Umwandlung "Char-Wert" => "echte Zahl" den "Hack" mit dem Abzug der '0' nutzen können.

'1' == 49
'2' == 50
...
'9' == 57

'1' - '0' == 49 - 48 == 1
'9' - '0' == 57 - 48 == 9

komischweise hat mein compiler diese warnungen nicht angezeigt und alles ohne zu murren kompiliert.

Code:

gcc -Wall -Wextra -std=c99 -pedantic foo.c

Shalec · Okt 12, 2017

ich empfehle die Hex-Darstellung. Denn 8 Zeichen entsprechen 32-Bit und 1 Zeichen entsprechend 4-Bit. So kannst du Änderungen im binären System (so lange es keine shifts sind) optisch nachvollziehen.

Code:

printf("%08X", (int) zahl)

gibt dir stets einen 8-stelligen Hexstring aus. Notfalls mit Nullen gefüllt.

Man kann das Problem halt generisch lösen, d.h. so dass es auf allen 32/64-Bit Plattformen läuft, ist aber die ineffizienteste Lösung, oder eben speziell auf Hardware zugeschnitten. Die zweite Variante benötigt dann aber ein tiefes Verständnis der Zielplattform. Für Hardware gibt es immer Technical Guides, Programming Manuals, ... die dir eben nicht nur das Instruction Set präsentieren, sondern oft auch Benchmarks der einzelnen Instruktionen bietet.

CypherL0rd · Okt 13, 2017

danke CDW jetz hab ichs verstanden. das mit dem ascii kannte ich natürlich schon aber das man mit minus '0' den ascii wert von den zahlen ascii werten abzieht und so einen korrekten integerwert bekommt, ist zwar logisch aber hab ich ohne erklärung nich geblickt..

shalec du willst es mir wohl immer komplizierter machen

nich alle menschen auf der welt sind mathematiker es gibt auch noch informatiker von der universität, informatikingeneure von der fachhochschule, fachinformatiker von der berufsschule und code-monkeys ohne jegliche qualifikation sowie quereinsteiger mit der falschen qualifikation.
was ich damit sagen will: eins nach dem andern, ich möchte es langsam angehn lassen und mein code muss erstmal funktionieren, bevor er optimal sein kann.

CypherL0rd · Okt 13, 2017

danke vielmals CDW, mit deiner hilfe habe ich es jetzt geschafft!
dein tipp dass eine zahl fehlt hat mir auch geholfen und dein /* unknown */ kommentar, habe das jetzt quick und dirty mit einer globalen variable gelöst.
zumindest kann man aber sagen dass mein konzept wohl doch nicht sooo blöd ist, hier der gesamte code:

Code:

#include <stdlib.h>
#include <stdio.h>

struct number {
    char *content;
    int length;
};

int lastlength;

char *convert_from_str(char numstring[], int length) {
    char *num;
    num = calloc(length, sizeof(char));
    for(int i=0; i<length; i++) {
        num[i] = numstring[i] - '0';
    }        
    return num;
}

char* convert_to_str(char numstring[static 1], size_t length) {
    for (size_t i = 0; i < length; ++i) {
        numstring[i] += '0';
    }
    return numstring;
}

char *addition(char *num1, char *num2, int length) {              // voraussetzung: num1 geq num2
    char *newnum;
    lastlength = length;
    newnum = calloc(length + 1, sizeof(char));
    int c = 0, tmp;                                              // c = übertrag
    for(int i=length-1; i>=0; i--) {
        if( (tmp = ((int) num1[i] + (int) num2[i] + c)) > 9) {
            newnum[i+1] = tmp - 10;
            c = 1;
        } else {
            newnum[i+1] = tmp;
            c = 0;
        }
    }
    if (c > 0) {
        newnum[0] = 1;
        lastlength++;
    } else {
        char *newnewnum;
        newnewnum = calloc(length, sizeof(char));
        for (int i=0; i<length; i++) {
            newnewnum[i] = newnum[i+1];
        }
        free(newnum);
        return newnewnum;
    }
    return newnum;
}

int main() {
    struct number zahl1;
    zahl1.content = convert_from_str("123456789", 9);
    zahl1.length = 9;
    
    struct number zahl2;
    zahl2.content = convert_from_str("987654321", 9);
    zahl2.length = 9;
    struct number zahl3;
    zahl3.content = addition(zahl1.content, zahl2.content, 9);
    zahl3.length = lastlength; 
    printf("%.*s + %.*s = %.*s\n", zahl1.length, convert_to_str(zahl1.content, zahl1.length), 
                             zahl2.length, convert_to_str(zahl2.content, zahl2.length),
                             zahl3.length, convert_to_str(zahl3.content, zahl3.length)
          );
    free(zahl1.content);                                                                                               
    free(zahl2.content);                                                                                               
    free(zahl3.content);       
    return EXIT_SUCCESS;
}

die ausgabe:

cmd hat gesagt.:
123456789 + 987654321 = 1111111110

shalec wird bestimmt wieder verbesserungen finden aber ich mache mich jetzt damit trotzdem mal an die bignum aufgabe, jetzt ist der anfang ja schon mal getan aber es wäre nett wenn ihr mir dann am ende sagt wie ich damit kryptographische sachen implementieren kann - made by CypherL0rd natürlich 8)

edit: achja übrigens hat es erst funktioniert nachdem ich antivir ausgeschaltet habe,
wenn ich diesen code, so wie er ist kompiliere und antivir echtzeitschutz aktiv lasse, wird das programm bei der ausführung in quarantäne verschoben und generell dauert die ausführung jeder selbst kompilierten datei beim ersten start immer 15 sekunden oder so.
nur mal so als anmerkung, von java und python kenne ich dieses verhalten nämlich nicht

Shalec · Okt 14, 2017

Verbesserungen gibt es immer. Mach erstmal weiter und Präsentiere die Ausgabe für

Code:

0xFFFFFFFF00000000DEADBEEFFFFFFFFF + 0xFFFFFFFFFEEBDAED00000000FFFFFFFF

Du kannst die Zahlen theoretisch (!) als integer einlesen. Jedenfalls interpretiert C die Eingabe "0xFFFFFFFF" als Integer = 2^32-1. Wie viele Bits haben die Summanden und wie viele erwartest du in der Summe maximal?

Du kannst auch den Windowsrechner nutzen, um dir die Ausgabe im "Programmierer"-Modus wandeln lassen. Übrigens ist Sagemath[1] (gibts als VB image gratis, ansteuerbar über den Browser über "localhost:8000") sehr dafür geeignet, sich Kontrollwerte ausgeben zu lassen.

Du kannst auch einen Prof fragen, ob er eine solche Vorlesung machen könnte. Dann wird die zum nächsten Semester geplant. Aber Krypto sollteste erst nach (erfolgreichem) Mathe 1&2 belegen. Die endliche Körperarithmetik ist das A und O der asymmetrischen Kryptographie und in Teilen sogar der symmetrischen Kryptographie. Der AES z.B. basiert auf der GF(2^8 ) Arithmetik. [2]

[1] SageMath - Open-Source Mathematical Software System

[2] Cryptography Engineering, Teil 1: Zur Theorie des Advanced Encryption Standard |
heise Developer