c++.de :: Schnelle Rechenoperationen mit großen zahlen

Unregistrierter

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.

Unregistrierter

Ich verstehe nicht warum das hier klappt:

Assembler:
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.

Assembler:
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...

Unregistrierter

96Bits == 3 DWORDs :warning:

Das Carry flag entspricht dem Übertrag (Grundschulmathematik :o)

)

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

Unregistrierter

Ahh danke tut mir leid du hast recht mit den 3 DWORDS = 96 bits :o)

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?

Unregistrierter

SpR schrieb:

Ahh danke tut mir leid du hast recht mit den 3 DWORDS = 96 bits :o)

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:

C++:
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 Mitglied 21:16:08 25.05.2012 Titel:

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);

Zitat:

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

Unregistrierter

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

rkhb Mitglied 12:13:40 26.05.2012 Titel:

SpR schrieb:

Vielen dank Ralph

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

Zitat:

das reicht vollkommen aus ich werde mich sofort einmal reinlesen.

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

:

C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211	#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

Unregistrierter

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 Mitglied 13:10:05 26.05.2012 Titel:

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