BigNumber-Klasse und rechnen mit Basis 2^64 im Stellenwertsystem bei größtem internen Datentyp von 64 Bit

Hallo

Für BigNumber-Klassen wird immer wieder empfohlen in Basis 2^64 zu rechnen. Ich frage mich gerade wie das möglich sein soll, wenn der größte Basisdatentyp 64 Bit hat (unsigned long / ulong).

Meine Klasse hat ein Array aus Digit-Objekten. Jedes Digit stellt eben eine Ziffer zur Basis "radix" da.

Folgende Hilfsfunktion multipliziert zwei Digits (intern ist Digit.digit wieder ein ulong):

public static void Mul(Digit a, Digit b, ref Digit carry, out Digit product)
{
	ulong radix = a.radix;    //die basis des stellenwertsystems.
	product = new Digit(radix, (a.digit * b.digit + carry.digit) % radix);

	//das geht nicht gut für hohe Basen
	carry = new Digit(radix, (a.digit * b.digit + carry.digit) / radix);
}

Dabei ist carry bei Funktionsaufruf ein möglicher Übertrag des vorherigen Schrittes und bei Verlassen der Funktion der neue Übertrag.
Das funktioniert alles Prima, wenn die Basis nicht zu groß wird.

Quizfrage: Wie berechnet man den carry-Wert, wenn der Ausdruck a.digit * b.digit + carry.digit bei hoher Basis (d.h. auch hohen möglichen Werten für die Ziffern) bereits einen ulong-Überlauf fabriziert?

Damit das nicht passiert, d.h. es zu keinem ulong-Überlauf kommt, dürfte die Basis maximal 2^32 - 1 sein.
Vielleicht lässt sich aber auch etwas in der Art der carry-Berechnung ändern, mir fällt nur nichts ein.

Danke und LG

Christoph

C++ garantiert dir gar nicht, dass unsigned long 64 Bits lang ist. Insofern bist du eh schon plattformabhängig. Dann kannst du auch mit inline assembler arbeiten und den Multiplikationsbefehl der CPU für 64-Bit-Zahlen nutzen. Der gibt dir nämlich ein 128-Bit-Ergebnis.

Das ist C#

camper

ad hoc könntest du die 64-bit Digits in zwei 32bit-Anteile aufteilen, und damit dann die Multiplikation ausführen. Damit erledigt sich das Überlaufproblem.