Assembler inline Code

Barsch

das isne gute frage...jedenfalls hatten wirnen pseudo code den wir umsetzen mussten, und da war die zweite schleife praktisch dabei...deshalb

Barsch

Hab jetzt nochmal nen Kumpel gefragt.

Der meinte wir müssen das einfach implementieren für ganz große Zahlen, auch wenn wirs praktisch net ausgeben.

So wegen den fehlenden Registern:

Meine Frage an prof.:

Kann ich Ergebnisse, auf Grund der Registerknappheit, erst lokal speichern und anschließend kopieren?

Antwort:

Das ist möglich. Eigentlich bleibt ohnehin keine Alternative dazu.

Implementieren läßt sich der Ansatz, indem man entweder schon Variablen (ein
Array) in C/C++ anlegt und dieses benützt. Alternativ kann man das auch in
Assembler machen, in dem man am Stack durch Erniedrigen des Stackpointer
Platz schafft.

Hoffe das hilft.

LG

camper

Bevor das in Assembler umgesetzt wird, sind ein paar Codeveränderungen angebracht, um das Ganze etwas übersichtlicher zu halten. Sinnvoll ist allemal, den eigentlichen Algorithmus vom Rest zu trennen, also hier eine eigene Funktion, die nichts mehr mit der Klasse selbst zu tun hat. Das ist übrigens dann auch mal ein schönes Beispiel dafür, dass die Implementation von op+ durch op+= nicht immer sinnvoll ist (als Beschreibung der Funktion kann es nat. trotzdem gelten). u32, u64 verwende ich der Schreibfaulheit wegen. Teste doch mal bitte, ob hier noch alles richtig ist:

struct BigInt
{
    u32 value[ BIG_INTEGER_MAX_WORDS ];
    BigInt& operator*=(const BigInt& multiplier);
};

inline void mul32_64(u32 x, u32 y, u32& low, u32& high)
{
    u64 p = static_cast< u64 >( x ) * y;
    low = static_cast <u32 >( p );
    high = static_cast< u32 >( p >> 32 );
}

template<ptrdiff_t N>
void big_mul(const u32 (&x)[N], const u32 (&y)[N], u32 (& /* restrict */ r)[N])
{
    u32 t = 0;
    u32 u = 0;
    u32 v = 0;

    for ( ptrdiff_t i = -N; i != 0; ++i )
    {
        for ( const u32* v1 = x,
                       * v2 = y + N + 1 + i; v2-- != y; ++v1 )
        {
            u32 p_low, p_high;
            mul32_64( *v1, *v2, p_low, p_high );
            v += p_low;
            bool carry2 = v < p_low && ++p_high == 0;
            if ( carry2 || ( u += p_high ) < p_high )
                ++t;
        }
        r[ N + i ] = v;
        v = u;
        u = t;
        t = 0;
    }
}

BigInt& BigInt::operator*=(const BigInt& multiplier)
{
    u32 p_right[ BIG_INTEGER_MAX_WORDS ];
    big_mul( value, multiplier.value, p_right );
    std::copy( p_right, p_right + BIG_INTEGER_MAX_WORDS, value );
    return *this;
}

BigInt operator*(const BigInt& lhs, const BigInt& rhs)
{
    BigInt result;
    big_mul( lhs.value, rhs.value, result.value );
    return result;
}

Gibt es einen besonderen Grund, warum kein Loop-unrolling stattfinden soll? Das lässt sich schließlich durch die Verwendung von Macros durchaus flexibel gestalten - ohne gleich eine Codeexplosion im Falle sehr großer N zu erzeugen.

Barsch

Jetzt hab ich nur mehr das Problem, dass ich mich in dem C Code garnimma auskenn
So gut kann ich c++ nochnet das ich das da alles kapier.

edith: errors kommen auch viele

camper

#include <cstddef>
#include <algorithm>
using namespace std;
typedef unsigned long u32;
typedef unsigned long long u64;
const ptrdiff_t BIG_INTEGER_MAX_WORDS = 8;

gehört noch vorne dran. Die Klasse BigInt hab ich hier nur als Ersatz benutzt. Diesen Teil müsstest du nat. entsprechend an die Klasse, so wie du sie hast, anpassen.

Barsch

Jo, das Problem ist aber:

Wir dürfen die Klasse nicht verändern, auf keinen Fall

camper

Barsch schrieb:

Jo, das Problem ist aber:

Wir dürfen die Klasse nicht verändern, auf keinen Fall

Hab ich das getan? Irgendwie muss ich mal so etwas einführen, und du hast mir keine Definition gegeben.

Barsch

Also falls irgendwie möglich:

Einfach den Code, so wie ich ihn hatte in Assembler umschreiben (inline)...muss doch machbar sein oder?

Kann dir auch die files shcicken, falls du mir icq, mail, msn oder so sagst.

camper

Barsch schrieb:

Also falls irgendwie möglich:

Einfach den Code, so wie ich ihn hatte in Assembler umschreiben (inline)...muss doch machbar sein oder?

Kann dir auch die files shcicken, falls du mir icq, mail, msn oder so sagst.

Machbar ist das schon, nur nicht sinnvoll und auch nicht spannend. Heute Compiler sind ziemlich gut in dem, was sie tun. Es erfordert schon ein bisschen Arbeit, wenn man etwas davon haben will. Man schreibt nicht einfach mal ein paar Zeilen inline code und plötzlich ist alles viel schneller (nat. nur, wenn der ursprüngliche Code etwas taugt). Andernfalls könntest du genauso gut den Code, den der Compiler generiert, hernehmen. Der ist aller Wahrscheinlichkeit nach, bereits ziemlich optimal.

Barsch

Naja so blöd es klingt...ich möchte nix davon haben
Ich brauchs einfach nur ^^