Implementing BigInteger

Question

I need to implement a 1024bit math operations in C .I Implemented a simple BigInteger library where the integer is stored as an array "typedef INT UINT1024[400]" where each element represent one digit. It turned up to be so slow so i decided to implement the BigInteger using a 1024bit array of UINT64: "typedef UINT64 UINT1024[16]"

so for example the number : 1000 is represented as {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1000}, 18446744073709551615 as {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0xFFFFFFFFFFFFFFFF} and 18446744073709551616 as {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0}.

I started wih writing the function to convert a char array number to an UINT1024 and an UINT1024 to a char array, it worked with numbers <= 0xFFFFFFFFFFFFFFFF. Here's what i did:

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

So please how can i implement it and is it possible to implement it using UINT64 for speed or just to stick with each array element is a digit of the number which is very slow for 1024bit operations.

PS: I can't use any existing library !

Thanks in advance !

Update Still can't figure out how to do the multiplication. I am using this function:

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

Then

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

I really need some help in this and Thanks in advance !

Why not just use one of the implementations out there that already exist? — hatchet - done with SOverflow, Mar 01 '14 at 20:04
Why do you not use libraries such as [GMP](https://gmplib.org/)? — Lee Duhem, Mar 01 '14 at 20:05
`#include ` and `typedef char UINT1024[1024 / CHAR_BIT + !!(1024 % CHAR_BIT)];` will give you 1024 bits, plus 1 extra byte if `CHAR_BIT` isn't a power of 2. For example, a system with 9 bits per byte (`CHAR_BIT == 9`) will result in 1024/9 + 1 = 113+1 = 114 bytes because 113*9==1017 bits, which is too small, unlike 114*9==1026 bits. Then it is merely a matter of converting binary to decimal and vice-versa. You might change `!!(1024 % CHAR_BIT)` to a plain 1 to allow tracking whether an overflow occurs. That is wasteful in the common 8-bit char computers we know and is thus optional. — , Mar 01 '14 at 23:37
So the character array is ASCII `0123456789ABCDEF`? Is `char[0]` the low 4 bits (little-endian) or high? You also seem to be using base-10 in the function. It's not clear why. — Brett Hale, Mar 02 '14 at 03:57

score 1 · Accepted Answer · answered Mar 01 '14 at 20:11

1

You need to implement two functions for your UINT1024 class, multiply by integer and add integer. Then for each digit you convert, multiply the previous value by 10 and add the value of the digit.

answered Mar 01 '14 at 20:11

Mark Ransom

299,747
42
398
622

I didn't fully understand your answer. I now posted the code of convert from string. – HMVC Mar 01 '14 at 20:25
1

@HMVC you're working backwards from the tail end of the string, my algorithm is for working from the beginning of the string. Instead of multiplying `Temp` by 10 I multiply the previously calculated result by 10. I don't need a `Temp` that way. – Mark Ransom Mar 01 '14 at 20:28
I'm gonna write the Add & Multiply functions and see if it gonna work. Thanks for your help ! – HMVC Mar 01 '14 at 20:33
I completed the addition function but i couldn't make the multiplication though. The problem exactly is how to multiply UINT64 with UINT64 their low & high parts and extracting the overflow. – HMVC Mar 04 '14 at 18:57
@HMVC you need to split each UINT64 into two pieces, multiply each piece by the pieces from the other to make 4 outputs, then sum all 4 into a 128-bit number. See http://stackoverflow.com/a/741371/5987 for summing. – Mark Ransom Mar 04 '14 at 19:30

score 0 · Answer 2 · answered Mar 01 '14 at 22:26

Writing, debugging, defining test cases, and checking they do work right is a huge undertaking. Just get one of the packaged multiprecission arithmetic libraries, like GMP, perhaps though NTL or CLN for C++. There are other alternatives, trawl the web. Jôrg Arndt's Matters Computational gives source code for C++.

score 0 · Answer 3 · answered Mar 02 '14 at 10:25

If you are doing this for your education, you should take the middle road between your two previous approaches. Put more than 1 bit into a leaf or digit, but do not use the full bit range of the integer type.

The reason is that this may significantly simplify the multiplication operation if you can at first just accumulate the products a[i]*b[j] in c[i+j]. And then normalize the result to the fixed digit range. c has length 2N-1, and this should fit into 1024 bit, so a and b are restricted to 512 bit.

If the arrays a and b hold N digits with maximum value B-1, B=2^b, then the largest of the c[k] is c[N-1] with bound N*(B-1)^2. Thus the design constraints are

(2N)*b>=1024
ld(N)+(2b)<=64

b   N   2N*b    ld(N)+2b

32  16  1024    68
24  22  1056    53
28  19  1064    61

So one possibility is to set b=28, B=1<

Even more suited for educational purposes would be to set B=10^d, e.g. with d=9, so that conversion from and to string is relatively trivial.

Implementing BigInteger

3 Answers3