Grosse Zahlen in Binaerdarstellung

XFame

Hi, ich moechte eine kleine schlanke Bibliothek zum Rechnen mit grossen Zahlen erstellen. Erstmal sollen nur die vier Grundrechenarten implementiert werden.
Ich dachte daran, meine Zahlen in einem Char-Array unterzubringen und binaer zu behandeln. Sprich, mit 2 Byte koennte ich also schon 2^16 = 65536 Zahlen darstellen. Vom Vorzeichen soll erstmal abgesehen werden.
Sollen nun zwei Zahlen addiert werden, dachte ich mir das ganze so:
Ich uebergebe einer Funktion

add(char* a, int length_a, char* b, int length_b)

die Adressen zweier zu addierender Variablen und deren Laenge in Bytes. Diese Funktion soll einfach beim ersten Bit anfangen und bitweise addieren (beide Bits mit einem XOR verknuepfen) und sich einen eventuellen Uebertrag fuer die naechste Operation merken (beide Bits mit einem AND verknuepfen).
Mir stellen sich nun ein paar Fragen:

1. Die Bibliothek soll natuerlich moeglichst effizient gestaltet werden, ist das ueberhaupt ein guter Ansatz die Zahlen so darzustellen und z.B. so mit der Addition zu verfahren?

2. Im Hinblick auf weitere Implementierungen wie Multiplikation/Division, Vorzeichen und nichtganze Zahlen, was wuerdet ihr da fuer eine Darstellung der Zahlen waehlen? Also mal abgesehen von der Binaerdarstellung der Zahl selbst, wo und wie sollen Informationen wie Vorzeichen, Stelle des Kommas und Laenge der Zahl untergebracht werden? Ich dachte da an sowas in der Art:

struct number {
char* adress;  /* Adresse im Speicher */
unsigned int length; /* Laenge der Zahl in Bytes */
unsigned int point[length][8]; /* Gibt das Byte und das Bit an, vor dem das Komma steht */
};

Das Vorzeichen sollte einfach immer das letzte Bit sein, aber das ist jetzt erstmal nicht so wichtig.

3. Sollte das soweit in Ordnung sein, wie kann ich denn einzelne Bits in meinem char ansprechen?

LG Christian

Christoph

XFame schrieb:

Ich dachte daran, meine Zahlen in einem Char-Array unterzubringen und binaer zu behandeln. Sprich, mit 2 Byte koennte ich also schon 2^16 = 65536 Zahlen darstellen. Vom Vorzeichen soll erstmal abgesehen werden.
Sollen nun zwei Zahlen addiert werden, dachte ich mir das ganze so:
Ich uebergebe einer Funktion
add(char* a, int length_a, char* b, int length_b)
die Adressen zweier zu addierender Variablen und deren Laenge in Bytes. Diese Funktion soll einfach beim ersten Bit anfangen und bitweise addieren (beide Bits mit einem XOR verknuepfen) und sich einen eventuellen Uebertrag fuer die naechste Operation merken (beide Bits mit einem AND verknuepfen).
Mir stellen sich nun ein paar Fragen:

1. Die Bibliothek soll natuerlich moeglichst effizient gestaltet werden, ist das ueberhaupt ein guter Ansatz die Zahlen so darzustellen und z.B. so mit der Addition zu verfahren?

Das klingt danach, als wolltest du die Zahlen im 2er-System speichern. Da du sowieso nur ganze Bytes allozieren kannst, würde ich eher das 256er-System nehmen. Eine "Ziffer" deiner Zahl würde dann immer genau ein Byte belegen und du musst dir weniger Gedanken um die einzelnen Bits machen.

XFame schrieb:

2. Im Hinblick auf weitere Implementierungen wie Multiplikation/Division, Vorzeichen und nichtganze Zahlen, was wuerdet ihr da fuer eine Darstellung der Zahlen waehlen? Also mal abgesehen von der Binaerdarstellung der Zahl selbst, wo und wie sollen Informationen wie Vorzeichen, Stelle des Kommas und Laenge der Zahl untergebracht werden? Ich dachte da an sowas in der Art:
struct number {
char* adress;  /* Adresse im Speicher */
unsigned int length; /* Laenge der Zahl in Bytes */
unsigned int point[length][8]; /* Gibt das Byte und das Bit an, vor dem das Komma steht */
};

Du könntest auch überlegen die Kommastelle ganz wegzulassen und stattdessen mit (gekürzten) Brüchen zu arbeiten. Wenn number eine struct für ganze Zahlen ist, wäre eine Kommazahl dann:

struct fractional {
  number numerator;
  number denominator;
};

XFame schrieb:

3. Sollte das soweit in Ordnung sein, wie kann ich denn einzelne Bits in meinem char ansprechen?

Einzelne Bits der Reihe nach ansprechen ist eine ziemlich teure Operation auf normalen CPUs. Wie gesagt, ich würde lieber auf ganzen Bytes arbeiten.

kanoni

Hallo,

ich habe ähnliches vor wie der Threadstater, aber leider dabei ein kleines Problem. Ich bekomme eine beliebige (sehr) große Zahl nicht in Binärform in eine Variable vom Typ char.
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 ?

Hab dank im voraus.

kanoni

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