Schnelle Rechenoperationen mit großen zahlen

Sorry hat länger gedauert war am Nachmitag nicht da, für mich sind große Zahlen bis zu 20-30 Stellen. Es sind Ganze Zahlen, also sowas wie BigInteger. Mich würde insgesamt interessieren, wie man mit solchen Zahlen rechnet also die Theorie, obwohl ich eingentlich nicht alle Rechenoperationen brauche sondern nur +,- sowie dekrement.

Ich benutze inline Assembler von Visual C++, da ich es irgendwie net hinbekomme mit nasm ein Windows 7 lauffähiges Programm zu schreiben.

Die Theorie ist sehr einfach: Addieren mit Übertrag. Dafür gibt es die Befehle Add with carry ADC und Subtract with borrow SBB.
Dekrementieren ist ja nichts weiter, als subtrahieren von 1 bzw. addieren von (-1).

Bsp.:

; 30 Dezimalstellen => 
; benötigte DWORDs = (ceil(log(1E30)/log(2))+31) and -32 = 3 = 96Bit

@dec:
	lea edx,srcA
	add DWORD ptr [edx+0],-1
	adc DWORD ptr [edx+4],-1
	adc DWORD ptr [edx+8],-1

@inc:
	lea edx,srcA
	add DWORD ptr [edx+0],1
	adc DWORD ptr [edx+4],0
	adc DWORD ptr [edx+8],0

@add:
	lea edx,srcA
	lea ecx,srcB
	mov eax,[ecx]
	add [edx],eax
	mov eax,[ecx+4]
	adc [edx+4],eax
	mov eax,[ecx+8]
	adc [edx+8],eax

@sub:
	lea edx,srcA
	lea ecx,srcB
	mov eax,[ecx]
	sub [edx],eax
	mov eax,[ecx+4]
	sbb [edx+4],eax
	mov eax,[ecx+8]
	sbb [edx+8],eax

Der Datentype müsste irgendwie so aussehen:

typedef {
    DWORD a1;
    DWORD a2;
    DWORD a3;
}INT96,*PINT96;

Vielen Dank für die schnellen Antworten. Werde es sofort einmal versuchen.
Mfg SpR

Ich hätte noch eine Frage wie kann ich dieser Struktur jetzt eine große Zahl zuweisen? Theoretisch könnte man ja jeden DWORD manuell zuweisen aber ich bin mir nicht sicher wie ich 200000000000000000 auf 4 DWORD aufteilen soll.

rkhb

SpR schrieb:

Ich hätte noch eine Frage wie kann ich dieser Struktur jetzt eine große Zahl zuweisen? Theoretisch könnte man ja jeden DWORD manuell zuweisen aber ich bin mir nicht sicher wie ich 200000000000000000 auf 4 DWORD aufteilen soll.

Aufteilung: Little Endian, also höchstwertiges DWORD hinten. Da Deine Zahl in ein LongLong hineingeht, statt vieler Worte:

#include <stdio.h>

typedef union
{
	struct
	{
		long long ll;
		int biggest;
	} ll;
	struct
	{
		int a1;
		int a2;
		int a3;
	} bigint;
} big_union;

int main(void)
{
	big_union uni;

	uni.ll.ll = 200000000000000000LL;
	printf ("I64i: %I64i\n",uni.ll.ll);
	printf ("I64u: %I64u\n",uni.ll.ll);
	printf ("I64X: 0x%I64X\n",uni.ll.ll);

	puts ("");

	uni.bigint.a1 = 0xBB140000;
	uni.bigint.a2 = 0x02C68AF0;
	uni.bigint.a3 = 0x00000000;
	printf ("I64i: %I64i\n",uni.ll.ll);
	printf ("I64u: %I64u\n",uni.ll.ll);
	printf ("I64X: 0x%I64X\n",uni.ll.ll);

	return 0;
}

Man möge mich korrigieren, aber ich meine mich erinnern zu können, dass die Elemente in einer C-Struktur im Speicher nicht direkt aufeinander folgen müssen, was aber bei einem C-Array der Fall wäre. In diesem Fall wäre es sicherer mit einem Array zu arbeiten.

viele grüße
ralph

Vielen Dank für die Antwort ich werde es sofort versuchen,
tut mir leid ,dasss ich nicht früher antworten konnte war aber leider heute ein stressiger Tag.
MfG SpR

Vielen Dank für die Antworten hat alles sehr gut geklappt allerdings stehe ich jetzt wieder vor einem Problem,es handelt sich in diesem Fall um das abfangen von einem Überlauf. Mein Code sieht so aus.

mov eax,addr ; in addr steht die Addresse des Speicherbereiches,welcher für die Speicherung der Zahlen vorgesehen ist
; also in diesem Falle 96 bits Speicherplatz (16 Bytes)
mov dword ptr[eax],0xFFFFFFFF    ; Die Bereiche mit den Zahlen füllen
mov dword ptr[eax+4],0x00000000  
mov dword ptr[eax+8],0xFFFFFFFF
mov dword ptr[eax+12],0xFFFFFFFF
adc dword ptr[eax],64h           ;Hier passiert der Überlauf, das Problem ist das der gesamte Inhalt von dword ptr[eax] gelöscht wird
;ich hatte überlegt ob diese 4 DWORDs als ein großer Speicherbereich gesehen werden kann, damit der CPU diesen Überlauf ausgleicht indem er das nächste DWORD verändert und nicht das andere löscht

Tut mir leid erst geschreiben und dann nachgedacht, jezt weiß i9ch wie es geht allerdings bräuchte ich noch Hilfe beim Verständnis ich bin nämlich mit dem Carry Flag noch nicht wirklich vertraut.

Ich verstehe nicht warum das hier klappt:

mov eax,addr ; addr ist wieder die Addresse des 96 bits Speicherbereiches
add dword ptr[eax],64h
adc dword ptr[eax+4],0
adc dword ptr[eax+8],0
adc dword ptr[eax+12],0

Das klappt zwar einwandfrei aber wieso? Ich addiere ja immer nur 0 dazu was soll sich da ändern? Also mal schnell ausprobiert ob auch das klappt.

mov eax,addr ; addr ist wieder die Addresse des 96 bits Speicherbereiches
add dword ptr[eax],64h
add dword ptr[eax+4],0
add dword ptr[eax+8],0
add dword ptr[eax+12],0

Leider ein Fehlschlag...

96Bits == 3 DWORDs
Das Carry flag entspricht dem Übertrag (Grundschulmathematik )

ADC x,0 beachtet den möglichen Übertrag aus niederwertigeren Stellen.

Ahh danke tut mir leid du hast recht mit den 3 DWORDS = 96 bits
Irgendwie ist mir da ein Fehler unterlaufen^^. Das Ausgeben der Zahlen als hexadezimale Zahlen klappt auch sehr gut allerdings würde ich noch gerne wissen wie man die Zahlen dezimal ausgibt hat das jemand eine Idee?

SpR schrieb:

Ahh danke tut mir leid du hast recht mit den 3 DWORDS = 96 bits
Irgendwie ist mir da ein Fehler unterlaufen^^. Nur verstehe ich deinen Algorithmus nicht ganz, in welchem du ausgerechnet hast wieviele bits für ich für 30 Dezimal Stellen benötige, ich habe mal versucht deinen mit deinem Algorithmus auf dein Ergebnis zu kommen leider scheine ich das Prinzip noh nicht ganz raus zu haben hier der Code:
unsigned long x=(unsigned long)(ceil(log(1E30)/log(2))+31);
x=x&-32;
Leider bekomme ich bei diesem Programm die Zahl 128 raus,welche nichts mit 96 Bits und auch nichts mit 3 DWORDS zutun hat.
Das Ausgeben der Zahlen als hexadezimale Zahlen klappt auch sehr gut allerdings würde ich noch gerne wissen wie man die Zahlen dezimal ausgibt hat das jemand eine Idee?

rkhb

SpR schrieb:

Leider bekomme ich bei diesem Programm die Zahl 128 raus,welche nichts mit 96 Bits und auch nichts mit 3 DWORDS zutun hat.

Ich habe mal auf folgender Seite die Bits gezählt:

http://manderc.manderby.com/concepts/umrechner/index.php

Für 1E30, also für eine 1 mit 30 Nullen, braucht man 100 Bits, also 4 DWords zu je 32 Bits.

Die Formel lautet also richtig:

int dwords = (int) ceil(log(1E30)/log(2)/32);

Das Ausgeben der Zahlen als hexadezimale Zahlen klappt auch sehr gut allerdings würde ich noch gerne wissen wie man die Zahlen dezimal ausgibt hat das jemand eine Idee?

Beherrscht Du die Umwandlung Integer zu Dezimal (http://dcla.rkhb.de/umwandlung/int2dez.html)? Bei der Division durch 10 musst Du auf die Grundlagen der Division zurückgreifen: http://dcla.rkhb.de/div.html. Ein Beispiel für zwei Dword-Register gibts hier: http://dcla.rkhb.de/div64.html. Die Erweiterung auf 4 Dwords überlasse ich Dir.

Ich frage mich, ob man dafür auch die 128-Bit-SSE-Register nutzbar machen könnte. Weiteres weiß ich aber nicht.

viele grüße
ralph

Vielen dank Ralph das reicht vollkommen aus ich werde mich sofort einmal reinlesen.
Mfg SpR

rkhb

SpR schrieb:

Vielen dank Ralph

Bitte, gern geschehen. Danke für die Rückmeldung.

das reicht vollkommen aus ich werde mich sofort einmal reinlesen.

Erst spitz machen, und dann "genug" schreien? Nix da :

#include <stdio.h>
#include <string.h>

typedef union
{
	struct
	{
		unsigned int dwords[4];
	} bigint;
	struct
	{
		unsigned long long ll;
		unsigned long long big;
	} ll;
} big_union;

void bigint_add (void* big1, void* big2)
{
	_asm
	{
		mov edi, big1
		mov esi, big2

		mov eax, [esi+0]
		mov edx, [esi+4]
		mov ecx, [esi+8]
		mov ebx, [esi+12]

		add [edi+0], eax
		adc [edi+4], edx
		adc [edi+8], ecx
		adc [edi+12], ebx
	}
}

void bigint_sub (void* big1, void* big2)
{
	_asm
	{
		mov edi, big1
		mov esi, big2

		mov eax, [esi+0]
		mov edx, [esi+4]
		mov ecx, [esi+8]
		mov ebx, [esi+12]

		sub [edi+0], eax
		sbb [edi+4], edx
		sbb [edi+8], ecx
		sbb [edi+12], ebx
	}
}

void bigint_inc (void* big)
{
	_asm
	{
		mov edi, big

		mov eax, 1
		xor ecx, ecx

		add [edi+0], eax
		adc [edi+4], ecx
		adc [edi+8], ecx
		adc [edi+12], ecx
	}
}

void bigint_dec (void* big)
{
	_asm
	{
		mov edi, big

		mov eax, 1
		xor ecx, ecx

		sub [edi+0], eax
		sbb [edi+4], ecx
		sbb [edi+8], ecx
		sbb [edi+12], ecx
	}
}

unsigned int bigint_div10 (void* big)
{
	_asm
	{
		mov esi, big
		mov ebx, 10

		mov eax, [esi+12]
		xor edx, edx
		div ebx
		mov [esi+12], eax

		mov eax, [esi+8]
		div ebx
		mov [esi+8], eax

		mov eax, [esi+4]
		div ebx
		mov [esi+4], eax

		mov eax, [esi+0]
		div ebx
		mov [esi+0], eax

		mov eax, edx					// Rückgabe: Rest
	}
}

__declspec(naked) void bigint_isnull () // Übergabe ESI: Zeiger auf BigInt
{
	_asm
	{
		mov eax, [esi]
		or eax, [esi+4]
		or eax, [esi+8]
		or eax, [esi+12]
		test eax, eax
		ret
	}
}

int bigint_is_null (void* big)
{
	_asm
	{
		mov esi, big
		mov eax, [esi]
		or eax, [esi+4]
		or eax, [esi+8]
		or eax, [esi+12]
		test eax, eax
		setz al
		movzx eax, al
	}
}

void bigint2dez (void* big, char* buf)
{
	big_union big1;
	memcpy (&big1,big,sizeof(big_union));

	_asm								// http://dcla.rkhb.de/umwandlung/int2dez.html
	{
		xor cl, cl
		lea esi, big1

		Schleife_1:
		push esi
		call bigint_div10
		add esp, 4
		push eax
		add cl, 1
		call bigint_isnull
		jnz Schleife_1

		mov edi, buf
		Schleife_2:
		pop eax
		or al, 00110000b
		stosb
		loop Schleife_2
		mov byte ptr [edi], 0
	}
}

int main(void)
{
	big_union big1, big2;
	char dez[40] = "buf";

	big1.ll.ll = 0x4674edea40000000; big1.ll.big = 0x0000000c9f2c9cd0; // 1e30
	printf ("hex\t0x%016I64X%016I64X\n",big1.ll.big,big1.ll.ll);
	bigint2dez (&big1, dez);
	printf ("dez\t%s\n",dez);

	bigint_inc (&big1);
	bigint2dez (&big1, dez);
	printf ("inc\t%s\n",dez);

	big2.ll.ll = 123456; big2.ll.big=0;
	bigint_add (&big1, &big2);
	bigint2dez (&big1, dez);
	printf ("add\t%s\n",dez);

	bigint_dec (&big1);
	bigint2dez (&big1, dez);
	printf ("dec\t%s\n",dez);

	big2.ll.ll = 123457; big2.ll.big=0;
	bigint_sub (&big1, &big2);
	bigint2dez (&big1, dez);
	printf ("sub\t%s\n",dez);

	bigint_inc (&big1);
	bigint2dez (&big1, dez);
	printf ("inc\t%s\n",dez);
	if (bigint_is_null (&big1)) puts ("Fehler: Falsches Null");

	bigint_sub (&big1, &big1);
	bigint2dez (&big1, dez);
	printf ("sub\t%s\n",dez);
	if (bigint_is_null (&big1)) puts ("Nu is aber Null");

	return 0;
}

An dem Programm gibts noch einiges zu optimieren und zu lernen. Du könntest Dir auch überlegen, wo Du drehen musst, um mit 50-stelligen Zahlen zu arbeiten. Da ich die Routinen auch für mich selbst nutze, würde ich mich freuen, wenn ich auf Fehler aufmerksam gemacht werde.

viele grüße
ralph

rkhb schrieb:

Da ich die Routinen auch für mich selbst nutze, würde ich mich freuen, wenn ich auf Fehler aufmerksam gemacht werde.

Sollten die Routinen unter Windows benutz werden, müssen ESI, EDI und EBX gesichert werden (Win/IntelABI)

rkhb

masm schrieb:

Sollten die Routinen unter Windows benutz werden, müssen ESI, EDI und EBX gesichert werden (Win/IntelABI)

Danke für den Hinweis.

Netterweise macht das mein Microsoft-Compiler automatisch. Der PellesC-Compiler macht es aber nicht automatisch. Ich habe mir hin- und herüberlegt, ob ich die Register sichern soll oder nicht. Meiner Meinung nach sind diese Register aber nur innerhalb der Windows- und C-Routinen gefährdet. Ich bewege mich hier aber außerhalb davon. Mit einem Beispiel, wo die Veränderung von ESI, EDI und EBX zur Katastrophe führt, wäre mir sehr geholfen.

viele grüße
ralph

Problem gibt es nur bei Callback Funktionen wie z.B. Fensterprozedur, Enumeratoren, ...
Was passiert, hängt von der Windows Version ab. Neuere Versionen scheinen wohl etwas toleranter zu sein, trotzallem sollte man sich einfach an die ABI halten da ansonsten die Potentielle Absturzgefahr besteht

Ich werde darauf achten allerdings hätte ich jetzt noch ein Problem ich berechne die Maximale Dezimalzahl von 4096 bits allerdings kann ich schlecht überprüfen ob die dezimalzahl stimmt, kennt jemand eine Seite oder kann seine Ergebnisse mit meinen abgleichen?
Vielen Dank nocheinmal für die gute Hilfe dank euch verstehe ich jetzt nicht nur wie man mit diesen großen Zahlen rechnet sondern auch die Hintergründe.
MfG SpR