3. eigene Big Integers

eigene Big Integers

  • S

    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.

    0
  • O

    implizitexplizit schrieb:

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

    Kleiner kanns aber auch nicht werden.

    0
  • ?

    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.

    0
  • S

    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.

    0
  • C
    Mod

    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.

    0
  • F

    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

    0
  • C

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

    0
  • C
    Mod

    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';
}
    0
  • V

    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.

    0
  • B

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

    0
Anmelden zum Antworten