Вопрос по biginteger, math, arbitrary-precision, x86-64 – x86-64 Большое целочисленное представление?

3

Как высокопроизводительные собственные большие целочисленные библиотеки в x86-64 представляют большие целые числа в памяти? (или это меняется? Есть ли самый распространенный способ?)

Наивно я думал о том, чтобы хранить их как строки с нулевыми концами чисел в базе 264.

Например, предположим,X в памяти как:

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

Пусть B = 264

затем

X = Dn * Bn + ... + D2 * B2 + D1 * B1 + D0

Пустая строка (то есть 8 байтов нуля) означает ноль.

Это разумный способ? Каковы плюсы и минусы этого пути? Есть ли способ лучше?

Как бы вы справились с подписью? Работает ли дополнение 2 с этим значением переменной длины?

(Нашел это:http://gmplib.org/manual/Integer-Internals.html  Что за конечность?)

«Конечность» это размер слова. (или, скорее, базовый). Обычно это 32 или 64 бит. Так что число представлено в базе2^32 или же2^64. Mysticial

Ваш Ответ

2   ответа
2

это будет как массив от минимального значения до самого высокого. Я реализовал добавление чисел произвольного размера в ассемблере. Процессор обеспечиваетнести флаг это позволяет вам легко выполнять эти виды операций. Вы пишете цикл, который выполняет операцию в кусках байтового размера. Флаг переноса включается в следующую операцию с использованием «Добавить с переносом». инструкция (код операции АЦП).

Нет извините. Я написал это 25 лет назад в колледже. Добавление bignums легко реализовать, и уже есть пара хороших библиотек с открытым исходным кодом.
Ваш ASM Bignum решение с открытым исходным кодом?
0

Addition

Принцип довольно прост. Вам нужно использоватьCF (флаг переноса) для любого большего переполнения. Давайте подумаем о добавлении двух 128-битных чисел.

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

Очень похоже на дополнение, хотя выCF сейчас называется брать.

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

Это намного сложнее. Вам нужно умножить каждую часть первого числа на каждую часть второго числа и добавить результаты. Вам не нужно умножать только две старшие части, которые наверняка переполнятся. псевдокод:

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

еще сложнее. Пользователь Brendan на форуме OsDev.orgотправил пример псевдокода для деления n-битных чисел. Я вставляю это здесь, потому что принцип тот же.

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--;
}
ОП спрашивает оx86_64не x86. А в x86_64 вам нужно всего 2 регистра для представления 128-битного числа. Для добавления rdx: rax к r11: r10 требуется только 2 инструкции:add r10, rax; adc r11, rdx

Похожие вопросы