3

x86-64上のhig-performanceネイティブbig-integerライブラリは、メモリ内の大きな整数をどのように表しますか？（またはそれは異なりますか？最も一般的な方法はありますか？）

素朴に私はそれらを基数264の0で終わる数の文字列として保存することを考えていました。

たとえばX、メモリ内に次のようにあるとします。

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

B = 264とします

それで

X = D n * B n + ... + D 2 * B 2 + D 1 * B 1 + D 0

空の文字列（つまり、8バイトのゼロ）はゼロを意味します。

これは合理的な方法ですか？この方法の長所と短所は何ですか？もっと良い方法はありますか？

署名をどのように処理しますか？2の補数はこの可変長値で機能しますか？

（これが見つかりました：http：//gmplib.org/manual/Integer-Internals.html 手足は何ですか？）

4

2 に答える 2

2

配列の最低値から最高値になると思います。アセンブラで任意のサイズの数値の加算を実装しました。CPUは、これらの種類の操作を簡単に実行できるようにするキャリーフラグを提供します。バイトサイズのチャンクで操作を実行するループを記述します。キャリーフラグは、「キャリー付き追加」命令（ADCオペコード）を使用した次の操作に含まれます。

于 2012-07-18T18:42:23.937 に答える
0

ここに、大きな整数を処理するいくつかの例があります。

添加

原理は非常に単純です。CFより大きなオーバーフローには（キャリーフラグ）を使用する必要があります。2つの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

減算

加算と非常によく似ています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

乗算

はるかに難しいです。最初の数値の各部分に2番目の数値の各部分を掛けて、結果を加算する必要があります。確実にオーバーフローする最も高い2つの部分だけを乗算する必要はありません。擬似コード：

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

分割

さらに複雑です。OsDev.orgフォーラムのユーザーBrendanが、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--;
}
于 2013-08-13T07:11:18.673 に答える