eigene Big Integers

[Sone]

Doch warum wäre es verschwenderisch, jede Ziffer als char in einem vector abzuspeichern?

Sagen wir, du speicherst mehrere 512-Bit Zahlen, also im Größenbereich von $2^{512} \approx 10^{154}$. Dann braucht deine Lösung 154 Byte pro Zahl, mit Nibbles 77, während die Lösung mit Bits 64 braucht.

[freakC++]

Das bedeutet, dass Du die Zahl, die du anfänglich beispielsweise als String bekommst, binär zerlegst. Die Idee finde ich gar nicht mal so schlecht. Doch frage ich mich, wie ich sie am besten abspeichere. Eigentlich bietet sich vector immer noch an, doch mit welchem Typ?

Danke!

[Nathan]

char.
Weil char ist IMMER ein Byte groß.

[camper]

Wenn Performance eine Rolle spielt, muss die Anzahl der Teil-Operationen pro Rechenvorgang minimiert werden. Das geschieht durch Auswahl von Algorithmen mit optimaler Komplexität und Minimierung der Anzahl der Operanden. Normalerweise sollten Zahlen daher mit einer Basis gespeichert werden, die dem größten Typ entspricht, den der Computer nativ verarbeiten kann (also typischerweise 2^32 oder 2^64). Ganz nebenbei ist das auch optimal in Hinblick auf den Speicherverbrauch.

[Sone]

Nathan schrieb:

char.
Weil char ist IMMER ein Byte groß.

Naja, ich würde da zu uint8_t tendieren. Ist praktisch immer unsigned char, nur ist halt ein Byte nicht zwangsläufig 8 Bit groß. Und es wäre schön, da eine Sicherheit zu haben.

[Nexus]

Sone schrieb:

nur ist halt ein Byte nicht zwangsläufig 8 Bit groß. Und es wäre schön, da eine Sicherheit zu haben.

Ja, die Sicherheit kann Leben retten

[Nathan]

Es ist garantiert, dass CHAR_BIT mindestens 8 ist.
Also geht man von 8 aus.

[Sone]

Nexus schrieb:

Sone schrieb:

nur ist halt ein Byte nicht zwangsläufig 8 Bit groß. Und es wäre schön, da eine Sicherheit zu haben.

Ja, die Sicherheit kann Leben retten

Naja, aber wenn das Ding eben auch 10 Bit groß sein kann, können einige Definitionen für Dinge wie bspw. zyklische Shifts nicht mehr richtig sein.

unsigned char cyclicLeftShift(unsigned char val, std::size_t bits)
{
    return (val << bits) | (val >> (8-bits));
}

Und man baut seinen Code zu mit Dingen wie CHAR_BIT . Finde ich persönlich nicht schön. Wenn man verlangt, dass es einen Typ mit Bitlänge 8 auf der Maschine gibt, muss man sich nie wieder über sowas Gedanken machen und legt es beiseite.

[Nathan]

static_assert(CHAR_BIT == 8, "your OS is broken");

Festgelegt.

[Swordfish]

...

[spielzeug]

camper schrieb:

Wenn Performance eine Rolle spielt, muss die Anzahl der Teil-Operationen pro Rechenvorgang minimiert werden.

Es gibt noch einen anderen Faktor: Ein- und Ausgabe (bzw. Umrechnung Bigint-Daten - Dezimalstring). Für Spielzeugprogramme ist es oft keine schlechte Idee, auf Zehnerpotenzen aufzubauen.

[freakC++]

Swordfish schrieb:

@freakC++: Welche der zu implementierenden Algos brauchen denn mehr als 32 Bit?

Von welchen Algorithmen sprichst Du?

spielzeug schrieb:

Es gibt noch einen anderen Faktor: Ein- und Ausgabe (bzw. Umrechnung Bigint-Daten - Dezimalstring).

Da dachte ich einfach an eine toString - Funktion, die meinen vector durchgeht und einen schönen String draus baut.

Ok, der Konsens rät mir wohl zu einer binären Darstellung. Dies sagt mir nach ein bisschen Überlegen doch auch mehr zu, da ich so später einfach Operationen wie das Addieren etc. implementieren kann. Ich könnte mir einfach einen RippleCarry Addierer bauen.

Leider hakt es noch bei einem Punkt ein bissl :

1.) Ich kriege den String: "13423...349". Ich dachte ja daran, die Ziffern einzeln abzuspeichern. Verstehe ich euch richtig, dass ihr jetzt jede Ziffer binär umwandeln würdet und dann in einem vector<uint8_t> speichert?

3.) Ich habe bisher noch nicht mit uint8_t gearbeitet. Verstehe ich es richtig, dass es wie ein char ist. nur hier garantiert ist, dass tatsächlich immer acht Bits, also ein Byte allokiert wurde?

Vielen Dank
lg, freakC++

[Swordfish]

...

[freakC++]

Hallo zusammen,

ich bin gerade recht viel beschäfitgt, sodass ich einige Tage beim Projekt ruhen musste. Trotzdem bin ich weiterhin interessiert, meine BigInteger Klasse zu realisieren. Ich muss ehrlichg gestehen, dass ich noch nicht ganz schlau aus euren Antworten geworden bin.

Swordfish schrieb:

Von welchen Algorithmen sprichst Du?

Entschuldigt, mein Fehler. Ich rede von RSA zum Beispiel. Also es geht um Algorithmen, die weit mehr als nur mit 32 Bit arbeiten. Ich befinde ich mich in einer Größenordnung von 2048 Bit.

Ich suche also einen Datentyp, der genau acht Bit groß ist. Anscheinend darf ich mich da bei char nicht drauf verlassen.

1.) Wo hat char bitte keine 8 Bit?

Von std::uint_least32_t habe ich noch nie was gehört und finde dazu auch keine guten Referenzen.

2.) Was ist der Vorteil dieses Datentyps? Ich sehe nur die Beschreibung "width of at least 8, 16, 32 and 64 bits respectively. Das will ich doch gerade nicht!

Ich habe mir noch ein paar weitere Gedanken gemacht. Mir bleibt ja nichts anderes über, als die Zahl als BCD abzuspeichern. Andernfalls müsste ich die Zahl irgendwie binär zerlegen, wozu ich sie aber zunächst in eine Variabel packen müsste. Das geht ja gerade (noch) nicht.

3.) Ich hatte die primitive Idee, einfach mit bool zu arbeiten. Ist es nicht am effizientesten, wenn ich jedes Bit als true/false hinterlege. Damit habe ich auch die Speicherfrage gelöst, denn eine n Bit Zahl wird genau n Bit im Speicher beanspruchen.

Vielen Dank für eure Hilfe
freakC++

[volkard]

freakC++ schrieb:

Hallo zusammen,

ich bin gerade recht viel beschäfitgt, sodass ich einige Tage beim Projekt ruhen musste. Trotzdem bin ich weiterhin interessiert, meine BigInteger Klasse zu realisieren. Ich muss ehrlichg gestehen, dass ich noch nicht ganz schlau aus euren Antworten geworden bin.

Swordfish schrieb:

Von welchen Algorithmen sprichst Du?

Entschuldigt, mein Fehler. Ich rede von RSA zum Beispiel. Also es geht um Algorithmen, die weit mehr als nur mit 32 Bit arbeiten. Ich befinde ich mich in einer Größenordnung von 2048 Bit.

Ich suche also einen Datentyp, der genau acht Bit groß ist. Anscheinend darf ich mich da bei char nicht drauf verlassen.

1.) Wo hat char bitte keine 8 Bit?

Von std::uint_least32_t habe ich noch nie was gehört und finde dazu auch keine guten Referenzen.

2.) Was ist der Vorteil dieses Datentyps? Ich sehe nur die Beschreibung "width of at least 8, 16, 32 and 64 bits respectively. Das will ich doch gerade nicht!

Ich habe mir noch ein paar weitere Gedanken gemacht. Mir bleibt ja nichts anderes über, als die Zahl als BCD abzuspeichern. Andernfalls müsste ich die Zahl irgendwie binär zerlegen, wozu ich sie aber zunächst in eine Variabel packen müsste. Das geht ja gerade (noch) nicht.

3.) Ich hatte die primitive Idee, einfach mit bool zu arbeiten. Ist es nicht am effizientesten, wenn ich jedes Bit als true/false hinterlege. Damit habe ich auch die Speicherfrage gelöst, denn eine n Bit Zahl wird genau n Bit im Speicher beanspruchen.

Vielen Dank für eure Hilfe
freakC++

lol

[cooky451]

Du willst einfach die fixed-size Datentypen uint8_t/uint16_t/uint32_t etc. benutzen. (Die will man in den allermeisten Fällen eh.) Big-Integer sind in derzeitigem C++ aber einfach nicht ordentlich zu implementieren, weil die Überlaufberechnung (die die CPU eigentlich gratis mit macht) einfach zu umständlich ist. Das macht nur mit Assembler Spaß.

[otze]

freakC++ schrieb:

3.) Ich hatte die primitive Idee, einfach mit bool zu arbeiten. Ist es nicht am effizientesten, wenn ich jedes Bit als true/false hinterlege. Damit habe ich auch die Speicherfrage gelöst, denn eine n Bit Zahl wird genau n Bit im Speicher beanspruchen.

Nein. Bool ist exakt 1 Byte groß. also auf allen handelsülichen maschinen 8Bit. Warum? Weil C++ nur Bytes addressieren kann.

[implizitexplizit]

otze schrieb:

Nein. Bool ist exakt 1 Byte groß. also auf allen handelsülichen maschinen 8Bit. Warum? Weil C++ nur Bytes addressieren kann.

§ 5.3.3 / 1 schrieb:

sizeof(char), sizeof(signed char) and sizeof(unsigned char) are 1. The result of sizeof applied to any other fundamental type (3.9.1) is implementation-defined. [ Note: in particular, sizeof(bool), sizeof(char16_t), sizeof(char32_t), and
sizeof(wchar_t) are implementation-defined.74 — end note ]
[...]
74) sizeof(bool) is not required to be 1.

Wüsste nicht, wie man das noch expliziter schreiben könnte.

[SG1]

Ich hab hier http://www.amazon.de/Kryptographie-Zahlentheoretische-Computer-Arithmetik-kryptographische-Xpert-press/dp/3540420614/ref=sr_1_1?ie=UTF8&qid=1369862129&sr=8-1&keywords=kryptografie+in+c+und+c%2B%2B noch als Buchempfehlung zu genau dem Thema.

Zur Überlaufproblematik gerade bei der Multiplikation wird dort folgendes vorgeschlagen: Angenommen, man arbeitet mit uintN_t als Typ für die "Ziffern". Dann castet man vor der Multiplikation jeweils nach uint2N_t, und kann damit den Überlauf darstellen. Das Ergebnis kann man dann mit Bitoperation wieder in uintN_t zerlegen.

Man nimmt also nicht den größten auf der Plattform nutzbaren Typ, sondern einen, der nur halb so groß ist.

[otze]

implizitexplizit schrieb:

Wüsste nicht, wie man das noch expliziter schreiben könnte.

Kleiner kanns aber auch nicht werden.