math - numeros - representacion numerica preescolar

Representación de enteros grandes x86-64?

Question

¿De qué manera las bibliotecas de alto entero nativas de alto desempeño en x86-64 representan un gran número entero en la memoria? (¿o varía? ¿Hay una forma más común?)

Ingenuamente, estaba pensando en almacenarlos como cadenas de números terminadas en 0 en la base 2 ⁶⁴ .

Por ejemplo, supongamos que X está en la memoria como:

[8 bytes] Dn
.
.
[8 bytes] D2
[8 bytes] D1
[8 bytes] D0
[8 bytes] 0

Deje B = 2 ⁶⁴

Entonces

X = D _n * B ⁿ + ... + D ₂ * B ² + D ₁ * B ¹ + D ₀

La cadena vacía (es decir, 8 bytes de cero) significa cero.

¿Es esta una manera razonable? ¿Cuáles son los pros y los contras de esta manera? ¿Hay una mejor manera?

¿Cómo manejarías la firma? ¿El complemento de 2 funciona con este valor de longitud variable?

(Encontré esto: http://gmplib.org/manual/Integer-Internals.html ¿ Qué es una extremidad?)

Answer 1

Yo pensaría que sería como una matriz de menor valor al más alto. Implementé la adición de números de tamaño arbitrario en el ensamblador. La CPU proporciona la marca de transporte que le permite realizar fácilmente este tipo de operaciones. Usted escribe un bucle que realiza la operación en fragmentos de tamaño de byte. El indicador de acarreo se incluye en la siguiente operación usando la instrucción "Agregar con acarreo" (código de operación ADC).

Answer 2

Aquí tengo algunos ejemplos del procesamiento de Big Integers.

Adición

El principio es bastante simple. Necesita usar CF (indicador de acarreo) para cualquier desbordamiento mayor. Pensemos en dos adiciones numéricas de 128 bits.

num1_lo: dq 1<<63
num1_hi: dq 1<<63
num2_lo: dq 1<<63
num2_hi: dq 1<<62
;Result of addition should be 0xC0000000 0x000000001 0x00000000 0x00000000
mov eax, dword [num1_lo]
mov ebx, dword [num1_lo+4]
mov ecx, dword [num1_hi]
mov edx, dword [num1_hi+4]

add eax, dword [num2_lo]
adc ebx, dword [num2_lo+4]
adc ecx, dword [num2_hi]
adc edx, dword [num2_hi+4]
jc .overflow

Substracción

Muy similar a la suma, aunque tu CF ahora se llama pedir prestado.

mov eax, dword [num1_lo]
mov ebx, dword [num1_lo+4]
mov ecx, dword [num1_hi]
mov edx, dword [num1_hi+4]

sub eax, dword [num2_lo]
sbb ebx, dword [num2_lo+4]
sbb ecx, dword [num2_hi]
sbb edx, dword [num2_hi+4]
jb .overflow    ;or jc

Multiplicación

Es mucho mas dificil Necesita multiplicar cada parte del número fisrt con cada parte del segundo número y agregar los resultados. No tiene que multiplicar solo dos partes más altas que seguramente se desbordarán. Pseudocódigo:

long long int /*128-bit*/ result = 0;
long long int n1 = ;
long long int n2 = ;
#define PART_WIDTH 32 //to be able to manipulate with numbers in 32-bit registers

int i_1 = 0; /*iteration index*/
for(each n-bit wide part of first number : n1_part) {
    int i_2 = 0;
    for(each n-bit wide part of second number : n2_part) {
        result += (n1_part << (i_1*PART_WIDTH))*(n2_part << (i_2*PART_WIDTH));
        i_2++;
    }
    i++;
}

División

es aún más complicado. El usuario Brendan en el foro de OsDev.org publicó un pseudocódigo de ejemplo para la división de enteros de n bits. Lo estoy pegando aquí porque el principio es el mismo.

result = 0;
count = 0;
remainder = numerator;

while(highest_bit_of_divisor_not_set) {
    divisor = divisor << 1;
    count++;
}
while(remainder != 0) {
    if(remainder >= divisor) {
        remainder = remainder - divisor;
        result = result | (1 << count);
    }
    if(count == 0) {
        break;
    }
    divisor = divisor >> 1;
    count--;
}