x86-64 Big Integer Representation?

问题:

How do hig-performance native big-integer libraries on x86-64 represent a big integer in memory? (or does it vary? Is there a most common way?)

Naively I was thinking about storing them as 0-terminated strings of numbers in base 2⁶⁴.

For example suppose X is in memory as:

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

Let B = 2⁶⁴

Then

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

The empty string (i.e. 8 bytes of zero) means zero.

Is this a reasonable way? What are the pros and cons of this way? Is there a better way?

How would you handle signedness? Does 2's complement work with this variable length value?

(Found this: http://gmplib.org/manual/Integer-Internals.html Whats a limb?)

回答1:

I would think it would be as an array lowest value to highest. I implemented addition of arbitrary sized numbers in assembler. The CPU provides the carry flag that allows you to easily perform these sorts of operations. You write a loop that performs the operation in byte size chunks. The carry flag is included in the next operation using the "Add with carry" instruction (ADC opcode).

回答2:

Here I have some examples of processing Big Integers.

Addition

Principle is pretty simple. You need to use CF (carry-flag) for any bigger overflow. Let's think about two 128-bit number addition.

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

Substraction

Very similar to addition, although you CF is now called borrow.

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

Multiplication

Is much more difficult. You need to multiply each part of fisrt number with each part of second number and add the results. You don't have to multiply only two highest parts that will surely overflow. Pseudocode:

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++;
}

Division

is even more complicated. User Brendan on OsDev.org forum posted example pseudocode for division of n-bit integers. I'm pasting it here because principle is the same.

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