Grosse Zahlen in Binaerdarstellung

Christoph

kanoni schrieb:

Mein jetziger Ansatz ist folgender:
char l = (char*) malloc (2048);
	*l = (1 << 16);
	printf("%d\n",*l);
	free(l);
Habe ich damit generell eienen falschen Ansatz ? Wenn dem so ist, könnte mir jemand bitte ein Stichwort oder einen Link nennen unter dem ich nachsehen und so auf die Lösung kommen kann ?

Zuerst einmal: malloc() nicht casten.

Zu deinem Problem: Die Variable l zeigt auf das erste von 2048 Bytes. Weil *l dasselbe wie l[0] ist, kannst du damit nur auf das allererste Byte zugreifen, aber das ist nur die "Einerstelle", kann also im 256er-System maximal eine Ziffer mit dem maximalen Wert 255 speichern.

Die Zahl 1<<16, also 65536, hat aber im 256er-System mehr als eine Ziffer; in dem System ist diese Zahl 1|0|0.

Nur kurz zur Notation: Ich schreib Zahlen zur Basis 256 als Folge von Ziffern getrennt mit | auf. Die einzelnen Ziffern sind in diesem Posting im Dezimalsystem dargestellt, da ich sonst 256 verschiedene Zeichen bräuchte. Die Zahl 256 entspricht also 1|0 und die Zahl 513 ist 2|1.

Um jetzt 65536 manuell zuzuweisen, müsstest du also schreiben:

v[2] = 1;
v[1] = 0;
v[0] = 0;
/* Länge "3" speichern nicht vergessen */

(Ich habe mir erlaubt, die Variable v statt l zu nennen.)

kanoni

Danke für deine schnelle Antwort.

Ich verstehe das ich nur auf den Anfang des Speichers zeige jedoch verstehe ich noch nicht, wie ich den Inhalt des *l ausgeben kann bzw. verarbeiten kann. Müsste ich also durch l_0...i laufen und den jeweiligen Inhalt l[i] aneinanderhängen ?

Christoph schrieb:

Zu deinem Problem: Die Variable l zeigt auf das erste von 2048 Bytes. Weil *l dasselbe wie l[0] ist, kannst du damit nur auf das allererste Byte zugreifen, aber das ist nur die "Einerstelle", kann also im 256er-System maximal eine Ziffer mit dem maximalen Wert 255 speichern.

kanoni

Christoph

kanoni schrieb:

Ich verstehe das ich nur auf den Anfang des Speichers zeige jedoch verstehe ich noch nicht, wie ich den Inhalt des *l ausgeben kann bzw. verarbeiten kann. Müsste ich also durch l_0...i laufen und den jeweiligen Inhalt l[i] aneinanderhängen ?

Ja, zum Ausgeben brauchst eine Schleife von l[0] bis l[n]. Wenn du die Zahl im Dezimalsystem ausgeben möchtest, wird es leider ein bisschen komplizierter, dafür müsstest du ein bisschen rechnen.

Die Zahl im Hexadezimal-System oder im 256er-System oder im Binär-System ausgeben geht aber direkt, weil sie so gespeichert ist.

kanoni

Danke

Allerdings ist das glaubig etwas zu aufwenig bzw. zu langsam um dann sehr große Zahlen mittels Bitoperationen zu verrechnen.

Gibt es noch eine weitere Möglichkeit ?

Christoph

kanoni schrieb:

Allerdings ist das glaubig etwas zu aufwenig bzw. zu langsam um dann sehr große Zahlen mittels Bitoperationen zu verrechnen.

Für was brauchst du Bitoperationen?

Sind +, *, -, /, % für dich Bitoperationen?

edit: OK, ein paar Bitoperationen wie &, | machen manche Rechnungen einfacher.

Aber zu langsam ist das nicht, wenn es gut implementiert ist. Du musst dir überlegen, dass eine Zahl der Länge n Bytes eben auch so viele Bytes im Speicher belegt, und bei Rechnungen mit dieser Zahl alle n Bytes angeschaut werden müssen. Du wirst also so oder so eine Schleife über alle n Bytes brauchen, sobald du eine Rechenoperation auf diese Zahl anwendest.

kanoni

Die Bitoperatoren machen die Rechnungen nicht nur einfacher, sondern zum Teil auch weit aus schneller !

Du musst dir überlegen, dass eine Zahl der Länge n Bytes eben auch so viele Bytes im Speicher belegt,

Das ist klar und das ist nicht das was ich als "zu langsam" bezeichne...
Was mein Problem momentan ist, das ich es einfach nicht auf die Reihe bekomme die Zahl (Potenz von 2) in den reservierten Speicher zu stopfen und z.B. dann einen Verschiebeoperator (<< oder >>) drauf anzuwenden und das Ergebnis auszugeben...

Christoph

kanoni schrieb:

Die Bitoperatoren machen die Rechnungen nicht nur einfacher, sondern zum Teil auch weit aus schneller !

Die Grundrechenarten sind auf aktuellen CPUs oft genauso schnell wie Bitoperationen. Man muss normalerweise keine Bit-Tricksereien bemühen, wenn man es mit den Grundrechenarten ausdrücken kann.

kanoni schrieb:

Was mein Problem momentan ist, das ich es einfach nicht auf die Reihe bekomme die Zahl (Potenz von 2) in den reservierten Speicher zu stopfen und z.B. dann einen Verschiebeoperator (<< oder >>) drauf anzuwenden und das Ergebnis auszugeben...

Der Verschiebungsoperator ist keine Grundrechenart, den würde ich deswegen erstmal gar nicht implementieren. Die Addition ist IMHO wichtiger. Wenn du zwei große Zahlen jeweils als char-Array vorliegen hast, kannst du die genauso addieren, wie du lange Zahlen in der Grundschule addiert hast: Ziffer für Ziffer addieren und in jedem Schritt den Übertrag beachten.

kanoni

Ich benötige den Verschiebeoperator jedoch, da ich nicht eine "normale" lib schreiben möchte die mit großen Zahlen umgehen kann sondern ein Programm das auf Primzahlen prüft (ich bin momentan im Primzahl-Wahn ).
Die Algorythmen zum prüfen (LLR) sind ansich sehr simpel, nur muss ich das eben mit sehr großen Zahlen (>>30000 stellen) am besten sehr schnell machen (daher die Bit-tricks).

kanoni schrieb:

(ich bin momentan im Primzahl-Wahn ).

dann gefällt dir vielleicht das: http://www.alpertron.com.ar/ECM.HTM
den source code kannste auch von der seite runterladen (der ist aber ziemlich gruselig).

kanoni

Danke für den Link

Ich habe mir den quellcode nicht angesehen, aber Java verfügt über eine eigenen BigInteger Datentyp. So kann ich das leider nicht auf mein Problem übertragen

kanoni

Ok ein letzter Post dann danoch dazu.

Wüsste denn jemand deine andere Möglichkeit mit großen Zahlen Binär in der Art umzugehen ? Ein Link oder ein paar Stichwörter würden schon reichen.

Danke

kanoni schrieb:

Wüsste denn jemand deine andere Möglichkeit mit großen Zahlen Binär in der Art umzugehen ? Ein Link oder ein paar Stichwörter würden schon reichen.

guck doch mal, wie andere das machen: http://c.snippets.org/code/bignum1.c
ansonsten google 'bignumber filetype:c' oder 'biginteger filetype:c' und ähnliches.

kanoni

Sooooo Danke dir, sowas habe ich gesucht. Da kann ich nun die Ideen die andere dazu hatten mal sehen und versuchen zu verstehen.

Mein Fehler bei der Such nach Codeschnippseln etc. war das ich mich immer auf "BigInteger" versteift habe und so nicht das richtige gefunden habe

kanoni schrieb:

Mein Fehler bei der Such nach Codeschnippseln etc. war das ich mich immer auf "BigInteger" versteift habe und so nicht das richtige gefunden habe

kleiner tip noch: wenn google, dann nimm google.com/ncr, wenn's um computerthemen geht, oder http://www.google.com/codesearch für source codes. http://www.google.de/ findet im prinzip auch viel, aber irgendwie scheinen mir die interessanten sachen immer ziemlich weit hinten zu sein.

XFame

Ich habe mal den Rat von Christoph befolgt und verwende nun das 256er System. Meine (ganzen) Zahlen werden nun so dargestellt:

typedef struct {
       unsigned char* adress;   /*Adresse der Zahl im Speicher*/
       unsigned int length;     /*Laenge der Zahl*/
       char sign;               /*Vorzeichen, entweder =1 oder =-1*/
} number;

Nun stellen sich mir aber noch ein paar Fragen bzgl. der Datentypen in C:
Nehmen wir folgendes Beispiel:

int main()
{
unsigned char a=10,b=20;
if (a-b>255) printf("a-b>255");
if (a-b<0) printf("a-b<0");
return 0;
}

Das Programm gibt bei mir nur ersteres aus:

a-b>255

Wie wird der Ausdruck "a-b" denn intern behandelt? Wie kann er groesser als 255 sein oder wie funktionieren Vergleiche in C? Weise ich einer dritten unsigned char Variable den Wert a-b zu, so ist ihr Wert ja kaum groesser als 255.
Gibt es da vllt. auch ein hilfreiches Tutorial im Netz?
LG

/Edit: Noch eine Frage: Was ist schneller

a?b:c

oder

if (a) b;
else c;

soviel ich weiß, wird bei berechnungen mit unterschiedlichen datentypen stets in den größten konvertiert.
also z.b.

char a = 1;
int b = 2;
double c = 3;
if ( a + b + c > 1 )

der größte datetyp im klammerausdruck, der mit den meisten byte, ist vom typ double. also wird alles nach double konveriert.

XFame schrieb:

if (a-b>255) printf("a-b>255");
if (a-b<0) printf("a-b<0");

hier ist in beiden fällen der größte datentyp int, wegen der 255 und wegen der eins. darum kann a-b negativ werden und kleiner 0 sein aber nicht größer als 255 werden.

XFame schrieb:

Noch eine Frage: Was ist schneller
a?b:c
oder
if (a) b;
else c;

kommt drauf an, was der compiler daraus macht. man müsste sich den maschinencode angucken, den der compiler produziert. ich glaube ich habe mal irgendwo gelesen, das es das gleiche in grün ist, bloß mit ner anderen schreibweise. sollte also gleich schnell sein.

XFame

mathematikpraktikant schrieb:

XFame schrieb:

if (a-b>255) printf("a-b>255");
if (a-b<0) printf("a-b<0");

hier ist in beiden fällen der größte datentyp int, wegen der 255 und wegen der eins. darum kann a-b negativ werden und kleiner 0 sein aber nicht größer als 255 werden.

Wieso ist der groesste Datentyp int? Sie sind doch beide unsigned char. Ausserdem wird ja eben "a-b>255" ausgegeben und nicht letzteres, also wird es eben nicht als negativ angesehen, sondern eher als >255.
LG

Wegen der eins und wegen der 255 wird alles nach int konvertiert. So macht es jedenfalls mein Compiler, bei mir wird letzteres ausgegeben.

Hier kannst du ein oder zwei Sätze zur Konvertierung unter dem Stichwort Konstanten nachlesen. Steht bestimmt auch im Standard, den habe ich aber z.Zt. nicht verfügbar.
http://www.mindrup.de/atos/news/c-kurs-02.html

XFame schrieb:

Das Programm gibt bei mir nur ersteres aus:
a-b>255

wenn du willst, dass das ergebnis auch ein 'unsigned char' ist, dann mach's so:

int main()
{
  unsigned char a=10, b=20;
  unsigned char c = a-b;
  if (c>255) 
    printf("a-b>255");
  if (c<0) 
    printf("a-b<0");
  return 0;
}

dein code spuckt bei mir übrigens 'a-b<0' aus, also anders als bei dir. kann sein, dass under/overflows von chars undefined sind.
zum konvertieren: chars werden vor der operation zu 'int' erweitert, dann wird mit den ints gerechnet und dann das ergebnis beschnitten (so dass es wieder in einen 'char' passt, wenn es einer 'char' variablen zugewiesen wird).