Malloc() to create a new size for integers for use with math - Guidance needed

Question

My goal is to create a integer type with a bigger size than 4 bytes, or 8 if I use long. I tried malloc to try and give more bytes in the memory for a bigger integer, but it still broke on the 31st iteration (gave a negative number). here's my code:

int main()
{
    int x = 31; //(normally an int can do up to 30 without going negative so this is my test number)
    int i;

    int *bigNum = NULL;
    bigNum = malloc((sizeof(int)*2));
    *bigNum = 1;
    for (i=0; i<x; i++) {
          *bigNum = *bigNum * 2;
          printf("%d \n", *bigNum);
    }
    free(bigNum);
}

Output:

2
4
...
..
...
1073741824
-2147483648

_it still broke on the 31st iteration_ ....you have a **very good an crystal** evidence of what is going on....... — LPs, Jan 24 '17 at 10:04
There's really no need to use `malloc` and dynamic allocation and pointers here. Just defining your `bigNum` variable like a normal variable would work just as well (or just like what you have now anyway). — Some programmer dude, Jan 24 '17 at 10:05
Possible duplicate of [How to store a very long integer value in a C program for an exam :- 98474737475747374739399](http://stackoverflow.com/questions/2252896/how-to-store-a-very-long-integer-value-in-a-c-program-for-an-exam-98474737475) — Ari0nhh, Jan 24 '17 at 10:07
As for what's happening, you have an *overflow*. While overflowing a signed integer (like you do) is technically *undefined behavior* what actually happens is something that depends on how negative numbers are represented on your computer. Read about [*two's complement*](https://en.wikipedia.org/wiki/Two's_complement) for more information about that. — Some programmer dude, Jan 24 '17 at 10:08
It doesn't matter if you'll allocate more memory for a type.. It is still a 4-byte `int` and it would overflow as your code demonstrates. To store bigger numbers you need to create your own type with underlying logic or use some library like BigInt — Yuriy Ivaskevych, Jan 24 '17 at 10:08
P.P - the INT_MAX is 2147483647 Raw nN - sorry about that, will be more careful next time LPs - your sarcasm actually made me laugh lmao!! Also thanks for everyones comments really gave me a better insight — Rand, Jan 24 '17 at 10:11

score 1 · Answer 1 · answered Jan 24 '17 at 10:08

1

Although you have allocated more memory for your integer, no other part of the system knows this, including:

the compiler doesn't know this;
the CPU chip doesn't know this.
printf doesn't know this.

So all calculations are just carried out using the native int size.

Note that you can't tell the CPU chip you use larger integers; it is a physical/design limitation of the chip.

answered Jan 24 '17 at 10:08

Paul Ogilvie

25,048
4
23
41

Makes a lot of sense! Thank you – Rand Jan 24 '17 at 10:20

score 0 · Accepted Answer · answered Jan 24 '17 at 10:07

0

Dereferencing an int * gives you an int no matter how much extra memory you allocate for it.

If you want a dat type able to hold more information, try a long (although the guarantee is that it will be at least as big as an int).

If you want to handle integers beyond what your implementation provides, use a bignum library, like MPIR.

answered Jan 24 '17 at 10:07

paxdiablo

854,327
234
1,573
1,953

I am interested in the logic behind a bignum library, how do they produce these datatypes? – Rand Jan 24 '17 at 10:16
@SteveSlayo Any integer is an array of bytes, where the first byte values 0 to 2^8 - 1, second byte is values 2^8 to 2^16 -1 and so on. Formally something like `2^(0*8) <= b0 - 1 <= 2^(1*8)`, `2^(1*8) <= b1 - 1 <= 2^(2*8)`, ... , `2^(n*8) <= bn - 1 <= 2^((n+1)*8)`. – Lundin Jan 24 '17 at 10:26
@Rand, if only I had an answer for that. Wait a minute, I *do:* http://stackoverflow.com/questions/1218149/arbitrary-precision-arithmetic-explanation/1218185#1218185 :-) – paxdiablo Jan 24 '17 at 10:45
@paxdiablo you cheeky bugger. That was an amazing write up, completely answered my question, thx! – Rand Jan 24 '17 at 12:51

chux - Reinstate Monica · Answer 3 · 2017-01-24T15:47:15.390

goal is to create a integer type with a bigger size

To handle multi-int integers, code also needs supporting functions for each basic operation:

int main(void) {
    int x = 31;

    RandBigNum *bigNum = RandBigNum_Init();
    RandBigNum_Assign_int(bigNum, 1);
    for (int i=0; i<x; i++) {
      RandBigNum_Muliply_int(bigNum, 2);
      RandBigNum_Print(bigNum);
      printf(" \n");
    }

Now, how might implement all this? Many approaches.

Below is a simply, incomplete and untested one. It is not necessarily a good approach, but to present an initial idea of the details needed to accomplish a big number library.

//  Numbers are all positive.  The first array element is the size of the number
typedef unsigned RandBigNum;

#define RandBigNum_MAXP1 (UINT_MAX + 1ull)

RandBigNum *RandBigNum_Init(void) {
  return calloc(1, sizeof *RandBigNum);
}

void RandBigNum_Muliply_int(RandBigNum *x, unsigned scale) {
  unsigned carry = 0;
  for (unsigned i = 1; i <= x[0]; i++) {
    unsigned long long product = 1ull * x[i] * scale + carry;
    x[i] = product % RandBigNum_MAXP1;
    carry *= product / RandBigNum_MAXP1;
  }
  if (carry) {
    unsigned n = x[0] + 2;
    x = realloc(x, sizeof *x * n); // re-alloc check omitted
    x[x[0]] = carry;
    x[0]++;
  }
}

// many other functions

Malloc() to create a new size for integers for use with math - Guidance needed

3 Answers3