BigInt Klasse - Problem bei Subtraktion



  • Ich versuche gerade eine eigene Klasse zu implementieren, die mit beliebig grossen ganzen Zahlen rechnen kann. Die Idee meiner Implementierung ist folgende:

    Ich speicheree eine BigInt Zahl in einem std::vector<uint32_t> _blocks , d.h. ich will die Zahl blockweise speichern. Zusaetzlich wird das Vorzeichen in einem sign Feld gespeichert. Es handelt sich also um eine Sign-Magnitude Darstellung (Two's Complement funktioniert soweit ich es sehe nicht gut fuer BigInt?).

    Die Idee ist nun schriftliche Subtraktion zu implementieren. Statt Basis 10 mache ich das in der Basis 0x100000000 = 2 ^ 32. Allerdings funktioniert die Subtraktion nicht:

    bigint_t bigint_t::operator-(const bigint_t &rhs) const
    {
            assert( is_positive() && rhs.is_positive() );
            if ( *this < rhs )
                return -(rhs - *this);
    
            bigint_t res;
            uint32_t carry = 0;
            for ( size_t i = 0; i < block_count(); ++i )
            {
                uint64_t a = _blocks[i];
                uint64_t b = (i < rhs.block_count() ? rhs._blocks[i] : 0) + carry;
    
                uint64_t r;
                if ( a < b )
                {
                    r = (0x100000000UL + (b - a)) % 0x100000000UL;
                    carry = 1;
                }
                else
                {
                    r = a - b;
                    carry = 0;
                }
    
                res._blocks.push_back(r);
            }
    
            return res;
    }
    

    Sieht jemand meinen Fehler bzw. kann mir jemand sagen wie man das richtig macht?

    PS: Kennt jemand irgendwelche Literatur zum Thema? Ich habe gegoogelt aber habe nicht wirklich etwas dazu gefunden (meistens Implementierungen, die nicht immer funktionieren, oder dann irgendwelche Libraries deren Code sehr schwierig zu verstehen ist).



  • icarus2 schrieb:

    Allerdings funktioniert die Subtraktion nicht:

    Sehr präzise Beschreibung.



  • icarus2 schrieb:

    PS: Kennt jemand irgendwelche Literatur zum Thema?

    Kapitel 8 in Ammeraal, L.: STL for C++ programmers, John Wiley & Sons, 1996

    dort ausführlich kommentierte class large.



  • manni66 schrieb:

    icarus2 schrieb:

    Allerdings funktioniert die Subtraktion nicht:

    Sehr präzise Beschreibung.

    Was soll schon nicht funktionieren? Es kommt natuerlich das falsche Resultat raus.

    Falls du ein Beispiel willst:
    a = 0x0000234afdafadfadafdafd390623623
    b = 0x0000fff4562340562035623045623056

    Mein Programm spuckt
    a - b = -0x0000dca9a78c6da5bac84da44b0005cd
    aus, es sollte aber
    -0xdca95873925b4537b25cb4fffa33
    sein.



  • versionsnummer schrieb:

    icarus2 schrieb:

    PS: Kennt jemand irgendwelche Literatur zum Thema?

    Kapitel 8 in Ammeraal, L.: STL for C++ programmers, John Wiley & Sons, 1996

    dort ausführlich kommentierte class large.

    Danke. Scheint allerdings keine PDF Version davon zu geben was etwas schade ist.



  • Ernsthaft?
    Falls ich ein Beispiel will?
    Ein Codeschnipsel und EIN Testfall?

    Es wird dich vielleicht überraschen, aber mir ist es völlig egal, ob dein BigInt funktioniert.


  • Mod

    uint64_t b = (i < rhs.block_count() ? rhs._blocks[i] : 0) + carry;
    

    bei b==0&& carry==1 ist das Unglück schon passiert, bevor in der größeren Variablen gespeicht wird. (Die Erweiterung auf 64bit ist im Übrigen völlig unnötig).

    r = (0x100000000UL + (b - a)) % 0x100000000UL;
    

    Und das ist einfach nur Blödsinn. Warum b-a, wenn du a-b rechnen willst? Einen Negation erfolgt ja nicht. und 0x... zu addieren nur um es dann per Modulo wieder loszuwerden hilft auch nicht.



  • Mir ist durchaus bewusst dass der Code Muell ist (hab den nur gepostet um zu zeigen dass ich bereits was versucht habe und es nicht klappt). Was mich eigentlich mehr interessieren wuerde ist wie man es richtig macht.

    Habe jetzt das Buch "Modern Computer Arithmetic". Beschreibt halt aber nicht wie man das ganze am besten in C++ implementiert.





  • gutes Buch schrieb:

    http://www.springer.com/de/book/9783642626463

    Danke, werde ich mir mal anschauen.



  • den gut kommentierten Quellcode von class large gibt's auf der Homepage des Autors



  • icarus2 schrieb:

    Was soll schon nicht funktionieren? Es kommt natuerlich das falsche Resultat raus.

    Falls du ein Beispiel willst:
    a = 0x0000234afdafadfadafdafd390623623
    b = 0x0000fff4562340562035623045623056

    Mein Programm spuckt
    a - b = -0x0000dca9a78c6da5bac84da44b0005cd
    aus, es sollte aber
    -0xdca95873925b4537b25cb4fffa33
    sein.

    zumindest die letzten 3 ziffern sind in deiner "falschen" lösung korrekt, ich war jetzt natürlich zu faul, den rest auch noch auszurechnen, aber dein programm arbeitet vermutlich korrekt.


Anmelden zum Antworten