Assembler inline Code

Hallo,

sorry war etwas undurchsichtig. Habe den code jetzt noch ein bisschen geändert!

bigIntType = unsigned long
BIG_INTEGER_MAX_WORDS = 8

bigIntType p_right[BIG_INTEGER_MAX_WORDS];
   bigIntType p_left[BIG_INTEGER_MAX_WORDS];

   bigIntType t, u, v, carry;
   t=0;
   u=0;
   v=0;
   unsigned long long p = 0;

   int count1 = 0;
   while (count1 < BIG_INTEGER_MAX_WORDS)
   {
		carry = 0;
		int count2 = 0;
		while (count2 <= count1)
           {
                p = static_cast<unsigned long long>(value[count2]) *
                    static_cast<unsigned long long>(multiplier.value[count1 - count2]);
                v += static_cast<unsigned long>(p);
                carry = v < static_cast<unsigned long>(p);
                u += static_cast<unsigned long>(p >> 32) + carry;
                carry = u < (static_cast<unsigned long>(p >> 32) + carry);
                t += carry;
				count2++;
           }
		   p_right[count1]=v;
           v = u;
           u = t;
           t = 0;
		   count1++;

   }

Danke
Barsch

camper

Ich nehme an, hier soll die Multiplikation zweier "BigUInts" implementiert werden. Der Algorithmus hat dann allerdings einen kleinen Fehler: static_cast<unsigned long>(p >> 32) + carry kann 0 sein, wenn carry 1 ist, und t wird dann nicht erhöht. Simples Beispiel wäre (2^64-1)2

Die Definition von multiplier und value fehlt, wenn sie auch nahe liegt. Auch den verwendeten Compiler und Zielplattform hast du nicht angegeben.

Hallo,

irgendwie versteh ich gerade nicht so ganz was du meinst, was da falsch sei.
Kannst die zeile vll richtig stellen? Das wäre ganz super.

value is der erste Multiplikant, multiplier der zweite

und value is dann am ende this, also das ergebnis

Compiler ist gcc (bzw. g++) und die verwendete Plattform Linux. (Intel im übrigen)

camper

wenn static_cast<unsigned long>(p >> 32) + carry überläuft, müsste dies eigentlich an t weitergereicht werden. also:

carry = u < (static_cast<unsigned long>(p >> 32) + carry) || (static_cast<unsigned long>(p >> 32) + carry) < carry;

im Assembler ist das dann zum Glück einfacher zu handhaben. Ein bisschen ungünstig ist die Registerproblematik: wir brauchen eax,edx für die Multiplikation, 3 Register für die Addition und eigentlich noch 3 Register um Operanden und Ergebnis zu adressieren. Wir haben aber nur 7 Register zur freien Verfügung. Hilfsweise könnte man das Ergebnis erst einmal lokal speichern (also relativ zu esp) und anschließen kopieren. Eine andere Möglichkeit wäre die Verwendung von SSE2 - das könnte sogar sehr elegant sein. Bei einer 64bit Plattform sind die Register kein Problem (wir haben ja 15 zur Verfügung), dann würde man aber wohl von vornherein auch mit 64bit Wörtern arbeiten. Darf das Ganze also SSE2 verwenden (Athlon64+ oder Pentium4+) oder soll es P6-kompatibel sein?

Ach stimmt, genau das habe ich vergessen.

Also ich kopier hiermal die Anforderungen rein.

Contraints(„Randbedingungen“)
–Nur Comba-Algorithmuserwünscht
–Keine 64-Bit Operationen verwenden
•MUL32 ist erwünscht
–Gesamte Multiplikation in Assembler
•Inklusive Schleifen
–Kein Loop-unrollingerwünscht
–Beschneiden des Ergebnisses auf n*32 Bit
•Richtigkeit der niederwertigen Worte sicherstellen
•Kein Überschreiten von Array-bzw. Index-Grenzen
–Wortanzahl n ist Parameter
•Derzeit auf 8 gesetzt; kann sich aber ändern

Also darf man wohl keine 64bit operationen und register verwenden.

Barsch

So mal registriert, ich poste jetzt noch den gesamten code, also auch die zweite Schleife und den Schluss.

bigIntType p_right[BIG_INTEGER_MAX_WORDS];
   bigIntType p_left[BIG_INTEGER_MAX_WORDS];

   bigIntType t, u, v, carry;
   t=0;
   u=0;
   v=0;
   unsigned long long p = 0;

   int count1 = 0;
   while (count1 < BIG_INTEGER_MAX_WORDS)
   {
		carry = 0;
		int count2 = 0;
		while (count2 <= count1)
           {
                p = static_cast<unsigned long long>(value[count2]) *
                    static_cast<unsigned long long>(multiplier.value[count1 - count2]);
                v += static_cast<unsigned long>(p);
                carry = v < static_cast<unsigned long>(p);
                u += static_cast<unsigned long>(p >> 32) + carry;
                carry = u < (static_cast<unsigned long>(p >> 32) + carry) || (static_cast<unsigned long>(p >> 32) + carry) < carry;
                t += carry;
				count2++;
           }
		   p_right[count1]=v;
           v = u;
           u = t;
           t = 0;
		   count1++;

   }

	count1 = BIG_INTEGER_MAX_WORDS;
	while (count1 <=  2* BIG_INTEGER_MAX_WORDS - 2)
   {
       int count2 = count1 - BIG_INTEGER_MAX_WORDS + 1;
		while (count2 <= BIG_INTEGER_MAX_WORDS - 1)
			{
                p = static_cast<unsigned long long>(value[count2]) *
                    static_cast<unsigned long long>(multiplier.value[count1 - count2]);
                v += static_cast<unsigned long>(p);
                carry = v < static_cast<unsigned long>(p);
                u += static_cast<unsigned long>(p >> 32) + carry;
                carry = u < (static_cast<unsigned long>(p >> 32) + carry) || (static_cast<unsigned long>(p >> 32) + carry) < carry;
                t += carry;
				count2++;
           }

		   p_left[count1 - BIG_INTEGER_MAX_WORDS] = v;
           v = u;
           u = t;
           t = 0;
		   count1++;
   }

   p_left[BIG_INTEGER_MAX_WORDS - 1] = v;

   count1=0;
   while (count1 < BIG_INTEGER_MAX_WORDS)
   {
		value[count1] = p_right[count1];
		count1++;
   }

   return *this;

camper

wozu die Mühe mit p_left, wenn du das Ergebnis sowieso nicht verwendest?

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 ^^