eigene Big Integers

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

[big number bubie]

freakC++ schrieb:

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.

Ach was, das ist doch gar nicht nötig. Du kannst die Zahl in einem simplen char-Array speichern, oder eben etwas umständlicher in einem Vektor.
Damit kannst du Zahlen bauen, die viele Megabytes lang sind, ohne Probleme.

[SG1]

freakC++ schrieb:

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.

Sagt Dir das Horner-Schema was? Damit kannst Du die Zahl ziffernweise einlesen und sofort in eine Zahl zur Basis 2^N konvertieren.

[camper]

Wenn es Integer mit fester Größe sein sollen, kann man das Ganze auch elegant rekursiv aus jeweils 2 Integern halber Größe aufbauen, bis diese klein genug sind, um eingebaute Typen verwenden zu können. Das spart dann auch das Schreiben von irgendwelchen Schleifen.

[freakC++]

SG1 schrieb:

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.

Das scheint genau das richtige sein für mich. Weiß jemand, wo man es für einen normalen Preis kaufen kann (nicht für über 2000 euro auf amazon)? Ich konnte auch kein .pdf finden. Gibt es das Buch überhaupt noch?

SG1 schrieb:

Sagt Dir das Horner-Schema was? Damit kannst Du die Zahl ziffernweise einlesen und sofort in eine Zahl zur Basis 2^N konvertieren.

Nein, aber das sieht sehr brauchbar aus. Vielen Dank!

volkard schrieb:

lol

Sowas kannste dir sparen. Das braucht hier keine. Schone lieber den Traffic des Forums!

camper schrieb:

Wenn es Integer mit fester Größe sein sollen, kann man das Ganze auch elegant rekursiv aus jeweils 2 Integern halber Größe aufbauen, bis diese klein genug sind, um eingebaute Typen verwenden zu können. Das spart dann auch das Schreiben von irgendwelchen Schleifen.

Kannst Du etwas genauer werden?

Danke und Grüße

[cooky451]

Ziemlich nette Idee eigentlich, vielleicht schafft der Compiler es sogar dann adc Instruktionen zu generieren. Muss ich bei Gelegenheit mal testen.

[camper]

Ganz grob ungefähr so

#include <iostream>
#include <cstddef>
#include <tuple>
#include <utility>

using namespace std;

template <size_t bits>
struct big_uint;

pair<uint32_t, bool> add_c(uint32_t a, uint32_t b, bool carry);
big_uint<64> mul_c(uint32_t a, uint32_t b);

template <size_t bits>
struct big_uint
{
    using half_type = typename std::conditional<bits==64, uint32_t, big_uint<bits/2>>::type;

    constexpr big_uint(half_type lo = 0, half_type hi = 0) : lo(lo), hi(hi) {}

    friend pair<big_uint, bool> add_c(const big_uint& a, const big_uint& b, bool carry)
    {
        auto low = add_c( a.lo, b.lo, carry );
        auto high = add_c( a.hi, b.hi, low.second );
        return { big_uint( low.first, high.first ), high.second };
    }

    friend big_uint<bits*2> mul_c(const big_uint& a, const big_uint& b)
    {
        auto x1 = mul_c( a.lo, b.lo );
        auto x2 = mul_c( a.lo, b.hi );
        auto x3 = mul_c( a.hi, b.lo );
        auto x4 = mul_c( a.hi, b.hi );
        auto low_  = add_c( x1,          big_uint( 0,     x2.lo ), false );
        auto low   = add_c( low_.first,  big_uint( 0,     x3.lo ), false );
        auto high_ = add_c( x4,          big_uint( x2.hi, 0 ),     low_.second );
        auto high  = add_c( high_.first, big_uint( x3.hi, 0 ),     low.second );
        return { low.first, high.first };
    }

    friend big_uint operator+(const big_uint& lhs, const big_uint& rhs)
    {
        return add_c( lhs, rhs, false ).first;
    }

    friend big_uint operator*(const big_uint& lhs, const big_uint& rhs)
    {
        return mul_c( lhs, rhs ).lo;
    }

    half_type lo, hi;
};

pair<uint32_t, bool> add_c(uint32_t a, uint32_t b, bool carry)
{
    auto res = a + b + carry;
    return { res, carry ? res <= a : res < a };
}

big_uint<64> mul_c(uint32_t a, uint32_t b)
{
    uint64_t x = a;
    auto res = x * b;
    return { res % ( 1ull << 32 ), res / ( 1ull << 32 ) };
}

int main()
{
    big_uint<64> x( 10, 20 ), y( 30, 40 );
    cout << x.hi << '\t' << x.lo << '\n';
    cout << y.hi << '\t' << y.lo << '\n';
    auto a = x + y; cout << a.hi << '\t' << a.lo << '\n';
    auto b = x * y; cout << b.hi << '\t' << b.lo << '\n';
}

[volkard]

camper schrieb:

Wenn es Integer mit fester Größe sein sollen, kann man das Ganze auch elegant rekursiv aus jeweils 2 Integern halber Größe aufbauen, bis diese klein genug sind, um eingebaute Typen verwenden zu können. Das spart dann auch das Schreiben von irgendwelchen Schleifen.

Ich hatte das angesetzt, weil karatsuba damit so schön unmittelbar hingeschrieben werden kann.

[Bitte ein Bit]

Ähh Leute, geht diese Bitfricklerei nicht ein wenig am Thema vorbei?

Sollte man nicht eher mal schauen dass die ganzen Algorithmen für + - / exp implementiert werden bevor wir über diese Mikro-Optimierung reden? Nachher möchte man eine High-End Multiplikation implementieren und muss erst seine seine Kodierung entsprechend anpassen.

Und ich bin mir sicher dass eine 0815 BigNum Implementierung auch ein wenig verschwenderisch sein darf. Es sein halt denn man benutzt sehr viele Instanzen von BigNum...