多精度加法实现

Question

我正在尝试为基于 radix-2^32 表示的 256 位操作数实现多精度算法。为此，我将操作数定义为：

typedef union UN_256fe{

uint32_t uint32[8];

}UN_256fe;

这是我的 MP 加法函数：

void add256(UN_256fe* A, UN_256fe* B, UN_256fe* result){

uint64_t t0, t1;
t0 = (uint64_t) A->uint32[7] + B->uint32[7];
result->uint32[7] = (uint32_t)t0;
t1 = (uint64_t) A->uint32[6] + B->uint32[6] + (t0 >> 32);
result->uint32[6] = (uint32_t)t1;
t0 = (uint64_t) A->uint32[5] + B->uint32[5] + (t1 >> 32);
result->uint32[5] = (uint32_t)t0;
t1 = (uint64_t) A->uint32[4] + B->uint32[4] + (t0 >> 32);
result->uint32[4] = (uint32_t)t1;
t0 = (uint64_t) A->uint32[3] + B->uint32[3] + (t1 >> 32);
result->uint32[3] = (uint32_t)t0;
t1 = (uint64_t) A->uint32[2] + B->uint32[2] + (t0 >> 32);
result->uint32[2] = (uint32_t)t1;
t0 = (uint64_t) A->uint32[1] + B->uint32[1] + (t1 >> 32);
result->uint32[1] = (uint32_t)t0;
t1 = (uint64_t) A->uint32[0] + B->uint32[0] + (t0 >> 32);
result->uint32[0] = (uint32_t)t1;

}

为了简单起见，我没有使用循环实现它。现在，当我在 main:

中测试我的函数时

#include <stdint.h>
#include <stdio.h>
#include <inttypes.h>
#include "mmulv3.0.h"

int main(){

UN_256fe result;
uint32_t c;

UN_256fe a = {0x00000f00,0xff00ff00,0xffff0000,0xf0f0f0f0,0x00000000,0xffffffff,0xf0fff000,0xfff0fff0};
UN_256fe b = {0x0000f000,0xff00ff00,0xffff0000,0xf0f0f0f0,0x00000000,0xffffffff,0xf0fff000,0xfff0ffff};
c = 2147483577;
printf("a:\n");
for(int i = 0; i < 8; i +=1){
    printf("%"PRIu32, a.uint32[i]);
}
printf("\nb:\n");
for(int i = 0; i < 8; i +=1){
    printf("%"PRIu32, b.uint32[i]);
}

add256(&a, &b, &result);
printf("\nResult for add256(a,b) = a + b:\n");
for(int i = 0; i < 8; i +=1){
    printf("%"PRIu32, result.uint32[i]);
}

return 0;
}

我有：

a:
38404278255360429490176040423221600429496729540433049604293984240
b:
614404278255360429490176040423221600429496729540433049604293984255
Result for add256(a,b) = a + b:
652814261543425429483622537896770241429496729537916426254293001199

然而，当我用 sage 验证我的结果时，我得到：

sage: a=38404278255360429490176040423221600429496729540433049604293984240
sage: b=614404278255360429490176040423221600429496729540433049604293984255
sage: a+b
652808556510720858980352080846443200858993459080866099208587968495

你能帮帮我吗？

Answer 1

在数字之间写一个 space 字符会有所帮助。

但是 384 + 6144 + 1 是多少？我认为你是从错误的一端添加的。

Answer 2

加法算法似乎是正确的，但您无法通过单独转换每个分量来以十进制形式打印这些 256 位整数。

想想这个简单的例子：0x100000000，存储为 { 0,0,0,0,0,0,1,0 }，将打印为 10 而不是 4294967296。以 10 为基数的转换比简单的加法要复杂得多。

Answer 3

以十进制打印多精度数字需要一些代码，因为许多数字取决于整个 uint32[8]。

用十六进制打印出来就容易多了。

fputs("0x", stdout);
for (int i = 0; i < 8; i +=1){
    printf("%08" PRIX32, a.uint32[i]);
}

多精度加法实现

Multi-precision addition implementation

c

biginteger

uint32-t

multiprecision