C: sehr große Zahlen einlesen

[HentaiD]

Hallo C-Freunde,
ich muss, wie der Titel schon sagt, sehr große Zahlen in C aus einer Datei einlesen und diese soll in folgendem struct gespeichert werden:

 typedef unsigned int uint32;
      typedef struct{
         uint32 n;
         uint32* words;
      }
      BigInt;

Das ganze soll im Little Endian Format mit Hilfe dieser Struktur im Zahlensystem 2^32 passieren. Jedes 32Bit Wort stellt also eine Ziffer bzw. Stelle da.
So heißt es in der Aufgabe. Irgendwie verstehe ich nicht ganz, wie ich da jetzt bitweise (oder jede Ziffer einzeln) einlesen soll. Bei Ziffern von 0-9 reichen
doch 4 Bit, oder stehe ich hier gerade nur total auf'm Schlauch?

Mein bisheriger Code zum testen von kleinen Zahlen ist bisher noch sehr simpel:
Er soll erst einmal nur einlesen und die Zahl ausspucken. Dabei ist es wichtig, dass es nur eine Zeile gibt.

   FILE* Datensatz = fopen (argv[1], "r");                                      // öffnen(lesen, "r") der Datei (Parametereingabe)
   if ( Datensatz == NULL )                                                     // Wenn Datei nicht vorhanden ist:
      printf("Ungueltiges Eingabeformat.\n");                                   // Ausgabe, Abbruch
   else{                                                                        // Andernfalls: Einlesevorgang beginnen
      for(i=0; !feof (Datensatz); i++){                                         // Zahl einlesen
         if (i==0){                                                    
            fscanf(Datensatz, "%d", &Zahl1);
         }
         else{
            printf("Ungueltiges Eingabeformat.\n");                             // Ausgabe, Abbruch    
            break;         
         }
      }
   }                                                                            // Ende einlesen  
   printf("%d", Zahl1);
   fclose(Datensatz);                                                           // Datei schließen

Unter Windows mit dem angeblich uralten Compiler (Bloodshed Dev C++) funktioniert das wunderbar.
Unter Mac (Xcode mit akutellem GCC) terminiert die Schleife nicht und spuckt "0" aus, bzw. eben den Wert,
mit dem Zahl1 initialisiert wurde. Da das ganze aber unter Linux laufen soll (Mac ist ja Unix, dürfte also ok sein)
frage ich mich jetzt wirklich warum der gleiche Code so schön unter Win funktioniert, aber nicht unter Mac.
Kann mir da vielleicht wer aushelfen?

Vielen Dank im Vorraus. =)


Greetz, D

 

[sheel]

Also, ich versteh die Aufgabenstellung schon anders
Kann es sein, dass nicht Jede Dezimalziffer abgespeichert werden soll, sondern als binäre ints, die hintereinandergehängt die Zahl ergeben?

zB Dezimal 8 Milliarden ergibt binär
1 11011100 11010110 01010000 00000000
Dafür braucht man also mindestens 33 bit; ein uint32 hat eben nur 32
Dass dann eben zwei int gespeichert werden (n in der struct für die Anzahl der ints),
eins mit 11011100 11010110 01010000 00000000 (dezimal 3 705 032 704)
und eins mit 00000000 00000000 00000000 00000001 (dezimal eben 1)

 

[HentaiD]

Hi,
danke schonmal für die schnelle Antwort. Jetzt habe ich einen ganz anderen Blick auf die Aufgabenstellung (folgende).

Zur Durchführung der Rechenoperationen mit großen Zahlen legen Sie diese im Speicher im Little-
Endian-Format ab und betrachten sie im Zahlensystem zur Basis 2^32. Jedes 32-Bit-Wort stellt hier
also eine einzelne Ziffer / Stelle dar. Implementieren Sie den Big-Integer-Datentyp unter Verwendung
der folgenden Struktur:

Wobei mit Struktur eben der struct oben gemeint ist.
Jetzt verstehe ich aber immer noch nicht, warum jede Ziffer als 32Bit Wort eingelesen werden soll. Ist das nicht eine
tierische Speicherverschwendung? Vorstellen könnte ich mir
1. bitweises einlesen, wobei da natürlich auch Speicher verloren geht, weil ich mit 3 Bit eben nur von 0 bis 7 zählen kann
und dann eben 4 brauche.
2. Oder ich hänge eben 32 Bit Zahlen aneinander, wobei das dann wohl auch gemeint ist.

Da ich aber auch Hex-Zahlen einlesen soll, stellt sich mir da wieder da Frage nach dem effizientesten Einleseverfahren,
da fscanf wohl nicht so dolle funktioniert und fgets sich zwar anbietet aber ich nicht wüsste wie groß der Puffer optimalerweise
sein sollte. Zumal die Hex-Zahlen, denke ich, von mir noch intern umgerechnet werden. Ist die Frage wie ich das bei sehr großen
am besten löse. Gibt es da vll. ein Einleseverfahren, was günstig für so eine Einleseoperation großer Zahlen geeignet ist und auch
unter Unix gut funktioniert?


Grüße, D

 

[deepthroat]

Mein bisheriger Code zum testen von kleinen Zahlen ist bisher noch sehr simpel:
Er soll erst einmal nur einlesen und die Zahl ausspucken. Dabei ist es wichtig, dass es nur eine Zeile gibt.

   FILE* Datensatz = fopen (argv[1], "r");                                      // öffnen(lesen, "r") der Datei (Parametereingabe)
   if ( Datensatz == NULL )                                                     // Wenn Datei nicht vorhanden ist:
      printf("Ungueltiges Eingabeformat.\n");                                   // Ausgabe, Abbruch
   else{                                                                        // Andernfalls: Einlesevorgang beginnen
      for(i=0; !feof (Datensatz); i++){                                         // Zahl einlesen
         if (i==0){                                                    
            fscanf(Datensatz, "%d", &Zahl1);
         }
         else{
            printf("Ungueltiges Eingabeformat.\n");                             // Ausgabe, Abbruch    
            break;         
         }
      }
   }                                                                            // Ende einlesen  
   printf("%d", Zahl1);
   fclose(Datensatz);                                                           // Datei schließen

Unter Windows mit dem angeblich uralten Compiler (Bloodshed Dev C++) funktioniert das wunderbar.
Unter Mac (Xcode mit akutellem GCC) terminiert die Schleife nicht und spuckt "0" aus, bzw. eben den Wert,
mit dem Zahl1 initialisiert wurde. Da das ganze aber unter Linux laufen soll (Mac ist ja Unix, dürfte also ok sein)
frage ich mich jetzt wirklich warum der gleiche Code so schön unter Win funktioniert, aber nicht unter Mac.

Es ist grundsätzlich eine schlechte Idee vor dem Einlesen auf EOF zu prüfen. Das sagt doch überhaupt nicht aus ob das Einlesen dann klappen wird. Zumal EOF evtl. erst gesetzt wird, nachdem man versucht hat Daten einzulesen.

Wenn du Zeilenweise einlesen willst, dann nimm fgets.

Wenn du nur eine Zahl einlesen willst, dann probiere doch einfach eine Zahl einzulesen und schau ob das geklappt hat.

if (fscanf(Datensatz, "%d", &Zahl1) == 1) {
  ...
}

Gruß

 

[sheel]

Ich glaub, du verstehst "Ziffer" falsch...Im Dezimalsystem hättest du ja wohl recht (mit der Speicherverschwendung und so).
Im Dezimalsystem kann eine Ziffer 10 mögliche Werte haben (0-9), im Hex eben 16 (0-9 und a-f)...und jetzt soll jede sogenannte Ziffer 2^32 verschiedene Werte haben
Praktisch eines der ints aus dem words-Array in der struct.

Es ist also wirklich so, wie im Beispiel mit den 8 Milliarden.

Und wegen den Hex-Zahlen: Die sind um einiges einfacher als Dezimalzahlen einzulesen, weil iimmer 8 hex-Ziffern in ein int reingestopft werden.

 

[HentaiD]

Hi,
danke nochmal, der Code wurde jetzt abgeändert, da ich tatsächlich nur eine Zeile mit einer Zahl auslesen soll.
Ich muss allerdings noch schauen, ob die Eingabe korrekt ist. D.h. ob da Buchstaben außerhalb einer 0x / Hex-Zahl sind,
oder weitere Zeilen, oder oder oder.

FILE* Datensatz = fopen (argv[1], "r");                                      // öffnen(lesen, "r") der Datei (Parametereingabe)
   if ( Datensatz == NULL )                                                     // Wenn Datei nicht vorhanden ist:
      printf("Ungueltiges Eingabeformat.\n");                                   // Ausgabe, Abbruch
   else{                                                                        // Andernfalls: Einlesevorgang beginnen
      for(i=0; !feof (Datensatz); i++){                                         // Zahl einlesen
         if ((fscanf(Datensatz, "%d", &Zahl1))==1){                                                    
            printf("%d", Zahl1);
         }
         else{
            printf("Ungueltiges Eingabeformat.\n");                             // Ausgabe, Abbruch    
            break;         
         }
      }
   }                                                                            // Ende einlesen  
   fclose(Datensatz);                                                           // Datei schließen

Funktioniert für Windows mit und ohne Schleife wunderbar (die Schleife soll wie gesagt prüfen, ob da noch mehr Zeilen sind
und wenn dem so ist -> abbrechen und das Programm stoppen).
Unter Mac funktioniert das mal wieder gar nicht. Er lädt die Datei offenbar und geht dann in den else-Teil. Das verstehe ich einfach nicht.
Der Code ist doch ok, oder nicht? Er bestätigt, dass die Datei da ist, liest aber nichts aus, also fscanf == 0.

Habe das ganze jetzt mit großen Zahlen probiert. Erstaunlicherweise stürzt das Programm nicht ab, sondern gibt mir irgend eine große Zahl aus.

Kann ich fscanf oder fgets irgendwie sagen, dass er nur 32 Bit einlesen soll (also so nach und nach), damit ich die in die struct speichern kann?
Und vorher irgendwie checken wie lang die Zahl tatsächlich ist, damit ich weiß, wie oft ich das machen muss?


Liebe Grüße, D

 

[eto]

Also, ich versteh die Aufgabenstellung schon anders
Kann es sein, dass nicht Jede Dezimalziffer abgespeichert werden soll, sondern als binäre ints, die hintereinandergehängt die Zahl ergeben?

zB Dezimal 8 Milliarden ergibt binär
1 11011100 11010110 01010000 00000000
Dafür braucht man also mindestens 33 bit; ein uint32 hat eben nur 32
Dass dann eben zwei int gespeichert werden (n in der struct für die Anzahl der ints),
eins mit 11011100 11010110 01010000 00000000 (dezimal 3 705 032 704)
und eins mit 00000000 00000000 00000000 00000001 (dezimal eben 1)

Hi das klingt sehr einleuchtend.
Wenn ich jetzt z.B die Zahl 8 Milliarden in einer Datei a.txt habe.
Wie kann ich diese in der Speicher einlesen, so dass wirklich die Zahl eingelesen wird und nicht jede Ziffer der Zahl 8 Milliarden?
Ich habe es probiert mit fread, aber das funktioniert nicht.

 

[sheel]

Wie steht die die Zahl in der Datei?
Acht Null Null...?

 

[eto]

Wie steht die die Zahl in der Datei?
Acht Null Null...?

Genau, da steht jetzt zum Beispiel 80000..
ich kann die Zahlen nun z.B mit
a.n = fread(a.words,sizeof(uint32),size,f);
einlesen. (a ist dabei ein BigInt)
Ausgeben kann ich meine Zahl nun aber nur als String,
printf("Eingelesen: %d, und zwar: %s\n",a.n,a.words);
ich möchte aber doch irgendwie Bitoperationen machen, also die Zahl wirklich als Zahl im Speicher benutzen können.
Wie kann ich nun solch eine grosse zahl 8000.. wirklich als Zahl in den Speicher laden und darauf zugreifen
um es dann zB irgendwie zur Basis 2^32 umrechnen zu können.

 

[deepthroat]

Hi.

Wie kann ich nun solch eine grosse zahl 8000.. wirklich als Zahl in den Speicher laden und darauf zugreifen
um es dann zB irgendwie zur Basis 2^32 umrechnen zu können.

Da es keinen eingebauten Datentyp für solch große Zahlen gibt, mußt du den Text schon selbst als Zahl interpretieren. fread funktioniert natürlich überhaupt nicht.

Du solltest inzwischen die einfachsten Grundrechenoperationen (zumindest die Addition von BigInts mit int und Multiplikation von BigInts mit int) implementiert haben.

Dann könntest du z.B. eine Zeile aus der Datei einlesen und jede Ziffer einzeln interpretieren und entsprechend zu einem mit 0 initialisierten BigInt Variablen addieren.

PseudoCode:

BigInt b = 0;

while (d = readDigit(datei)) {
  b *= 10;
  b += d;
}

Gruß