c - 实现 BigInteger

Question

我需要在 C 中实现 1024 位数学运算。我实现了一个简单的 BigInteger 库，其中整数存储为数组“typedef INT UINT1024[400]”，其中每个元素代表一个数字。它变得如此缓慢，所以我决定使用 1024 位 UINT64 数组来实现 BigInteger:“typedef UINT64 UINT1024[16]”

例如，数字:1000 表示为 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1000}，18446744073709551615 作为 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0xFFFFFFFFFFFFFFFF} 和 18446744073709551616 作为 {0,0,0,0,0,0 ,0,0,0,0,0,0,0,0,1,0}。

我开始编写将 char 数组数字转换为 UINT1024 并将 UINT1024 转换为 char 数组的函数，它使用 <= 0xFFFFFFFFFFFFFFFF 的数字。这是我所做的:

void UINT1024_FROMSTRING(UIN1024 Integer,const char szInteger[],UINT Length) {
int c = 15;
UINT64 Result = 0,Operation,Carry = 0;
UINT64 Temp = 1;
while(Length--)
{
    Operation = (szInteger[Length] - '0') * Temp;
    Result   += Operation + Carry;
   /*Overflow ?*/
    if (Result < Operation || Temp == 1000000000000000000)
    {
        Carry  = Result - Operation;
        Result = 0;
        Integer[c--] = 0;
        Temp = 1;
    }
    else Carry = 0;

    Temp *= 10;
}

if (Result || Carry)
{
    /* I DONT KNOW WHAT TO DO HERE ! */
}

while(c--) Integer[c] = 0;}

所以请问我如何实现它，是否可以使用 UINT64 实现它以提高速度，或者只是坚持每个数组元素是数字的数字，这对于 1024 位操作来说非常慢。

PS:我不能使用任何现有的库!

提前致谢!

---

更新仍然无法弄清楚如何进行乘法运算。我正在使用这个功能:

    void _uint128_mul(UINT64 u,UINT64 v,UINT64 * ui64Hi,UINT64 * ui64Lo)
{
   UINT64 ulo, uhi, vlo, vhi, k, t;
   UINT64 wlo, whi, wt;
   uhi = u >> 32;
   ulo = u & 0xFFFFFFFF;
   vhi = v >> 32;
   vlo = v & 0xFFFFFFFF;
   t = ulo*vlo;    wlo = t & 0xFFFFFFFF;
   k = t >> 32;
   t = uhi*vlo + k;
   whi = t & 0xFFFFFFFF;
   wt = t >> 32;

   t = ulo*vhi + whi;
   k = t >> 32;
   *ui64Lo = (t << 32) + wlo;
   *ui64Hi = uhi*vhi + wt + k;
}

然后

void multiply(uint1024_t dUInteger,uint1024_t UInteger)
{
    int i = 16;
    UINT64 lo,hi,Carry = 0;

        while(i--)
        {
            _uint128_mul(dUInteger[i],UInteger[15],&hi,&lo);
            dUInteger[i] = lo + Carry;
            Carry = hi;
        }
}

我真的需要一些帮助，在此先感谢!

Answer 1

您需要为您的 UINT1024 类实现两个函数，乘以整数并添加整数。然后，对于您转换的每个数字，将前一个值乘以 10，然后加上该数字的值。