# C: sehr große Zahlen einlesen



## HentaiD (6. Juli 2010)

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 (6. Juli 2010)

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 (6. Juli 2010)

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 (6. Juli 2010)

HentaiD hat gesagt.:


> 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.
> 
> 
> ...


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 (6. Juli 2010)

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 (6. Juli 2010)

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 (8. August 2010)

sheel hat gesagt.:


> 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
> ...


 
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 (8. August 2010)

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


----------



## eto (8. August 2010)

sheel hat gesagt.:


> 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 (8. August 2010)

Hi.





eto hat gesagt.:


> 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ß


----------



## eto (8. August 2010)

deepthroat hat gesagt.:


> 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:
> 
> ...


 
Danke, gute Idee.
Das geht allerding für ein 10er System.
Ich muss die Zahl aus der Textdatei jedoch im Zahlensystem zur Basis 2^32 abspeichern.
Mir fällt da keine Idee ein, wie sieht es bei euch aus?


----------



## Matthias Reitinger (8. August 2010)

eto hat gesagt.:


> Danke, gute Idee.
> Das geht allerding für ein 10er System.


Du willst ja auch Zahlen im Zehnersystem einlesen, insofern ist das schon ok so.



eto hat gesagt.:


> Ich muss die Zahl aus der Textdatei jedoch im Zahlensystem zur Basis 2^32 abspeichern.
> Mir fällt da keine Idee ein, wie sieht es bei euch aus?


deepthroat hat dir doch schon eine Idee geliefert: implementiere erst mal Funktionen, die es erlauben, einen uint32 auf einen BigInt zu addieren bzw. zu multiplizieren. Bei der Umwandlung vom Zehnersystem in BigInt greifst du dann auf diese Funktionen zurück, in der Art wie deepthroat es erklärt hat.

Grüße,
Matthias


----------



## eto (13. August 2010)

Danke nochmals,
hat soweit alles geklappt, ich kann nun aus einer beliebigen Dezimalzahl in einer Text-Datei,
eine BigInt-Zahl zur Basis 2^32 erstellen.
Ich kann auch 2 BigInt addieren.

Wenn ich nun eine BigInt-Zahl als Dezimalzahl darstellen will, gibt es da eine gute Möglichkeit?

Beispiel: ich lese aus einer Textdatei die 
Dez-Zahl: 1234567891023298
(Binär: 0000 0000 0000 0100 0110 0010 1101 0101 0011 1100 1001 1000 0111 0101 1100 0010)
(Hex: 0x462D5 3C9875C2)
In meinem BigInt a, mit a.n=2, ist sie nun folgendermaßen im Little-Endian-Format abgespeichert:
a.words[0]=3C9875C2;
a.words[1]=462D5;
Im Prinzip ist die dezimaldarstellung ja: 0x462d5 * 2^32 + 0x3C9875C2
Gibt es da eine einfache Methode die mir nicht direkt einfällt?
Gruß,
eto


----------



## HentaiD (14. August 2010)

Also ich implementiere gerade das Einlesen von Dezimalzahlen. Das mache ich folgendermaßen (vll. nicht elegant, aber egal hauptsache das funktioniert irgendwie)  :

char[Anzahl Digits in der Datei] <- Da kommt eine Kopie der großen Zahl rein.
Lässt sich da problemlos ohne malloc reinspeichern. 

Die Zahl wird dann einfach durch 2 geteilt (mit dem Schulalgorithmus). Fall die letzte Ziffer sich nicht gerade teilen lässt -> 1 schonmal ins BigInt (ansonsten halt 0) und dann pro Durchlauf shiften, bzw. in ein anderes Wort schreiben.

Folglicherweise würde ich umgekehrt die Binärdaten auch so wieder auslesen... denke ich. Mal sehen, ob das auch so klappt. =)


LG, D


----------

