Handling big numbers in C

Hey, I've been searching for a way of handling big numbers in C for a long time now... I want to handle numbers up to a trillion.

I have found the gmp library, which seems to do exactly what I want, but my compiler (Digital Mars) dosen't have it by default. I went to the gmp website and downloaded the zip file containaing the library but I don't know how to install it... I searched all over the net for a tutorial on how to install the library and found a few of them, but I don't understand the instructions... They seem to use some Unix comands while installing the library =S

So any help at installing the gmp library or pointing me towards another way of handling big numbers in C would be deeply appreciated.

Thanks in advance =)

Are you using Linux? If so, which distro?

Edit: I'm confused, because some of your other posts suggest that you're using Windows, and I don't see any zip files on the GMP website, only tarballs.

I have used gmp, please specify where do you stop in the installation.

robatino

Sorry, I said zip when they're infact .tar.gz files... I forgot that.

I use windows, and thought that .tar.gz files could also be used in windows.

Mortissus

I just download the file containing the library, didn't know what to do after that.

Looking through the gmp-discuss mailing list archives (http://gmplib.org/#MAILINGLISTS), I found this:

Native Windows Binaries for GMP-4.2.1

robatino wich of these files should I download? There are a lot of them =(

I'm using Digital Mars.

I'm not familiar with Windows, but you could just download the pre-built binaries for your system, whatever that is.

Your compiler doesn't give you a 64 bit long long type?

I had an assignment once about this subject. I used linked lists to do the job, the huge integer was given from a file or from stdin and then firstly i saved every digit in nodes including the sign and after this i created add,sub, mul, div, mod etc. I have writen to many lines of code, i advise you to make a given library work as its a hard thing to do.

brewbuck

Yes it does, but when I said a trillion I meant much bigger numbers...

I'm doing Project Euler and a lot of it's challenges involves dealing with ridiculously big numbers... Such as this one:



(I don't if even gmp could handle 28433 * 2^7830457+1, there's probably a smarter way for calculating it's last ten digits, but there are other problems wich for example require you to calculate the max digital sum of a^b where a, b < 100.....)

Lala if you if your using Digital mars, in order to use the GMP you need copying the lib file to the Lib folder under \dm\lib and copy the header file on to the \dm\include folder. And that then include the header in your main code.

Hope you can star using the library.

ssharish2005

> you need copying the lib file to the Lib folder under \dm\lib
> and copy the header file on to the \dm\include folder
Doesn't DM support the usual -I and -L compiler flags for specifying additional places to find include files and libraries?

Messing with the standard implementation directories isn't a good idea IMO.

> I don't if even gmp could handle 28433 * 2^7830457+1, there's probably a smarter way for calculating it's last ten digits,

If all you want is the last 10 digits, you can compute using modular arithmetic, reducing modulo 10^10 as you go:

http://en.wikipedia.org/wiki/Modular_arithmetic

So you can first compute the last 10 digits of 2^7830457 by successively doubling, lopping off any digits past the last 10 as you go, so you never have more than 11 digits. Then take the resulting at most 10 digit number, multiply by 28433, then take the last 10 digits of that. Finally, add 1 and take the last 10 digits of that. Intuitively, it should be pretty obvious why this works, even if you don't know about modular arithmetic.

Edit: Since doubling is cheap (bitwise left shift) and reducing mod 10^10 is expensive, for efficiency you would double as many times as you could before exceeding your machine's capacity, before reducing. You could also avoid the multiplication by 28433, by starting with 28433 and doubling it 7830457 times (reducing as you go).

Sorry for the delay. To install GMP try this:

tar xvf gmp-4.2.1.tar.gz
cd gmp-4.2.1
./configure
make
make install

Good luck, any problems just ask ;)

robatino

I've tried following your instructions but my code didn't work... Am I on the right track?

Code:

---

#include <stdio.h>

int main ()
{
    unsigned long long number = 28433;

    for (int i = 0; i <= 7830457; i++)
    {
        number = (number << 1) &#37; 10000000000;
    }

    number++;

    printf ("%d",  number);
    return 0;
}

---

ssharish2005

I've copied all the .lib files to the lib directory and all .h files to the include directory but when I tried to compile a code that was in project euler's forum I get a bunch of errors...

Code:

---

Error 42: Symbol Undefined ___gmpz_clear
 Error 42: Symbol Undefined ___gmpz_get_str
 Error 42: Symbol Undefined ___gmpz_add
 Error 42: Symbol Undefined ___gmpz_ui_pow_ui
 Error 42: Symbol Undefined ___gmpz_init

---

Inside the zip file was a dll file wich I didn't copy to any folders... Maybe the error is there.

Mortissus

I don't know where and how to use these comands :(

E &#233; sempre bom encontrar um brasileiro por ai =)

Your code looks almost right, except for 3 things:
1) To iterate 7830457 times, the loop condition should be "i < 7830457", not "i <= 7830457".
2) I suspect that the constant 10000000000 may be treated as an int by default, instead of a long long, and get truncated. Try writing the constant as 10000000000LL or 10000000000LLU instead; that should tell the compiler that the constant is long long or unsigned long long, resp. Do this everywhere you use this number.
3) After "number++;", you need to reduce number mod 10000000000 again, just in case it happened to be exactly 10000000000.

Edit: Oh, and 4) The printf() specifiers for long long and unsigned long long should be &#37;ll and %llu, respectively. %d is for int. I think this is correct, based on some googling, I've never actually used them.

robatino

Thanks a lot robantino =) I find it amazing how small the code is...

Code:

---

#include <stdio.h>

int main ()
{
    unsigned long long number = 28433;

    for (int i = 0; i < 7830457; i++)
    {
        number = (number << 1) &#37; 10000000000LLU;
    }

    number = (number + 1) % 10000000000LLU;

    printf ("%llu",  number);
    return 0;
}

---

For added efficiency, note that the slowest operation is the &#37;, and you can minimize the number of times that gets called by doing as many bitwise left shifts as you can without exceeding the capacity of an unsigned long long, before using %. Suppose number was 9999999999, which is less than 2^34, and the maximum value of an unsigned long long is (2^64)-1. Then you could double number 30 times without overflow, and this is the worst case, since you started out with the largest possible 10-digit number. This means you can do your left shifts in chunks of 30, so you can left-shift by 30 261015 times, followed by a single left shift by 7 (since 7830457 == 261015*30 + 7). This way you only have to do about 1/30 as many % operations. I'll leave it to you to work out the messy details.

The same problem done using the gmp library, by uranther posted at the project euler's forum:

Code:

---

int main(void)
{
    mpz_t pow, product, final;
    char *finalstring;

    mpz_init(pow);
    mpz_init(product);
    mpz_init(final);

    mpz_ui_pow_ui(pow, 2, 7830457);
    mpz_mul_ui(product, pow, 28433);
    mpz_add_ui(final, product, 1);

    finalstring = mpz_get_str(NULL, 10, final);

    printf("%s\n", finalstring+strlen(finalstring)-10);

    return 0;
}

---

Robantino if you have some spare time can you please take a look at this code, it's my implementation of the sieve of erasthothenes... For some reason it ain't working:

Code:

---

#include <stdio.h>
#include <math.h>

int main(void)
{
    int primes[1000000];
    int totalPrimes = 0;

    for (int i = 0; i < 1000000; i++)
        primes[i] = 1;

    for (int i = 0; i < 1000; i++)
    {
        if ((isPrime(i)) && primes[i])
        {
            int mul = 1;
            while ( (i * mul) < 1000000)
            {
                primes[i*mul] = 0;
                mul ++;
            }
        }
    }

    for (int i = 0; i < 1000000; i++) // testing the code
        if (primes[i])
            printf("&#37;d ", i);

    return 0;
}

int isPrime (int n)
{
    for (int i = 2; i < sqrt(n); i++)
    {
        if (!(n % i))
            return 0;
    }

    return 1;
}

---

Code:

---

  int primes[1000000];

---

You're trying to allocate 4 MB statically (assuming 4 byte ints). This may fail immediately, and in general you shouldn't try to allocate more than a fraction of a MB that way. Allocate the array dynamically using malloc() instead.

Code:

---

  for (int i = 2; i < sqrt(n); i++)

---

It should be "i <= sqrt(n)", and should be written instead as "i*i <= n", as this will both be faster and you don't have to worry about floating-point arithmetic. You could also check for divisibility by 2, and then by the odd numbers from 3 up, to reduce the time by a factor of 2.

Edit: Actually, you could precompute the biggest integer less than or equal to sqrt(n) (call it m) and then use "i <= m" which is even faster. You need to be careful that floating-point error doesn't cause it to be one too small.

Edit: I think if you let m = sqrt(n + .5), where m is an int, that should work. The .5 should prevent m from being too small, without making it any bigger. There could be a better way, though.

Code:

---

  if ((isPrime(i)) && primes[i])

---

You don't need to call isPrime(i), since if primes[1] == 1, then you know i is prime (so you can just get rid of the isPrime() function, and ignore most of my previous comments). Just use

Code:

---

  if (primes[i])

---

Standard C90 doesn't allow variable declarations in the middle of a block:

Code:

---

  int mul = 1;

---

This is another gcc nonstandard extension. For standards-compliant code, declare mul at the beginning of main() with the other variables, and then just set it to 1 inside the if statement.

Declaring i inside each of the for loops is only allowed in C99, not C90. You should declare i at the start of main(), not inside the for loops. Also, when you initialize the values primes[i], you should initialize primes[0] and primes[1] to 0, and the rest to 1.

Code:

---

  for (int i = 0; i < 1000; i++)

---

This loop should start at 2, not 0. Finally, mul should be initialized to 2, not 1 (otherwise you end up setting primes[i] to 0).

Hehe to be pretty honest with you I don't know how to use malloc :P I've just gone back to programing and I don't quite remember some aspects like pointers or memory... So I can't make that change in the code :( If you could please do it for me...

About the other change, removing the isPrime routine, I've done it.

I've also noticed a huge error, if that variable mul is set to 1 initially all multiples of the prime will be stripped, including the prime itself! So now mul is set to two.

Code:

---

#include <stdio.h>

int main(void)
{
    int *primes = malloc(1000000 * sizeof (int));
    int totalPrimes = 0;
    int mul;

    for (int i = 0; i < 1000000; i++)
        primes[i] = 1;

    primes[0] = 0;
    primes[1] = 0;

    for (int i = 2; i < 1000; i++)
    {
        if (primes[i])
        {
            mul = 2;
            while ( (i * mul) < 1000000)
            {
                primes[i*mul + 2] = 0; // because the loop starts at two
                mul ++;
            }
        }
    }

    for (int i = 0; i < 1000000; i++) // testing the code
        if (primes[i])
            printf("&#37;d ", i);

    return 0;
}

---

Edit: Sorry I've missed your last post :P Hehe we've spotted the same errors =)

Code:

---

  primes[i*mul + 2] = 0;

---

Take out the "+ 2". You should also #include <stdlib.h> whenever using malloc(), and to get your code to compile, I had to declare i at the start of main(), not in the for() loops. With these changes, your code works properly. Here is a version I got working earlier (I tend to write compressed code). I use assert() as a quick-and-dirty way to check malloc() for NULL.

Code:

---

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

int main(void) {
  int i, mul, *primes;

  assert(primes = malloc(1000000*sizeof(int)));
  primes[0] = primes[1] = 0;
  for (i=2; i<1000000; i++) primes[i] = 1;

  for (i=0; i<1000; i++) {
    if (primes[i]) {
      for (mul=2*i; mul<1000000; mul += i) primes[mul] = 0;
    }
  }

  for (i=0; i<1000000; i++) {
    if (primes[i]) printf("&#37;d\n", i);
  }

  free(primes);
  return 0;
}

---

Perfect! Thanks a lot for your help.

Here's a very recently (2004) discovered algorithm that improves upon the sieve of Eratosthenes.

http://en.wikipedia.org/wiki/Sieve_of_Atkin

I received today an email telling me that the thread had new messages. The notification system is sooooo slow. Is this hapenning to everyone?

I'm doing one of euler's challenges, and I'm completely clueless about this one =P

It tells you that there are eight coins in circulation in england: 1p, 2p, 5p, 10p, 20p, 50p, &#163;1 (100p) and &#163;2 (200p).

And then it asks you how many different ways can &#163;2 be made using any number of coins.

If someone could just show an algorithm wich would be helpfull here... I don't even know where to start =/

Here's my code so far, I tried implementing a greedy algorithm because it's the only one google pointed me out:

Code:

---

#include <stdio.h>

int main(void)
{
    int coins[] = {1, 2, 5, 10, 20, 50, 100}, i, j, temp, ways = 1;

    // I've removed the 200p coin and increased the ways var

    for (i = 6; i >= 0; i++)
    {
        temp = 200;
        temp -= coins[i];

        while (temp > 0)
        {
            for (j = 6; j >= 0; j++)
            {
                if (temp >= coins[j])
                {
                    temp -= coins[j];
                    break;
                }

                if (j == 0)
                    printf("No solutions....");
            }
        }

        ways++;
    }

    return 0;
}

---

Well, the number of 200p coins in any combination adding up to 200p is either 0 or 1. For each of these possibilities, you can work out the possible numbers of 100p coins (0, 1, or 2 in the first case, 0 in the second). For each of these, etc., etc. You could count all the possibilities with a set of nested loops, one for each type of coin, with the outermost loop being for 200p.

Edit: For an arbitrary set of denominations, you could define a function that takes as arguments the desired sum, the number of different denominations, and an array containing the values (preferably in decreasing order), and returns the number of combinations. It can be implemented recursively.