Grosse Zahlen in Binaerdarstellung

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

kanoni

So..
ich habe mich nun damit weiter beschäftigen können und bin gleich wieder auf ein Problem gestoßen.
Ich kann zwar die einzelnen gespeicherten Zahlen mit l+i (i-te position im malloc speicher als char) auslesen, doch wenn ich versuche damit zu rechnen, bekomme ich den Fehler "23 xxx\main.c invalid operands to binary + ".

Könnte mir das bitte jemand nochmal erklären ? Danke

kanoni schrieb:

Ich kann zwar die einzelnen gespeicherten Zahlen mit l+i (i-te position im malloc speicher als char) auslesen, doch wenn ich versuche damit zu rechnen, bekomme ich den Fehler "23 xxx\main.c invalid operands to binary + ".

da fehlt bestimmt irgendwo ein '*'. du versuchst wohl pointer zu addieren statt des inhalts.

kanoni

Hi,

ok mit * bekomme ich zwar keine Fehlermeldung vom Compiler mehr, aber dafür stürzt das Programm ab

printf("%d,%d,%d\n",*x+*x,(*x+3)+(*x+3),(*x+10)+(*x+10));

habe ich ausprobiert, wobei x von 0..99 gefüllt ist.

kanoni

nun ok .. peinlicher Post zuvor.

Habe es hinbekommen ^^