It’s hip2b2

As programmers, we are used to dealing with lots and lots of numbers. Most of the time these numbers are quite small and manageable. Something they get really large and ugly. We create all sorts of programs to deal with these giants numbers collectively know as BIGNUM. Why do we need them? There are extreme cases where our standard data types (int and float) do not quite cut it anymore. These data types have fixed precision and therefore do not have the flexibility of dealing with BIGNUMs.

However, there is nothing to fear. Most programming languages already come with libraries that help programmers deal with these BIGNUMs. I would like to talk about one know as GMP or GNU MP.

GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on. GMP has a rich set of functions, and the functions have a regular interface.

This short blog post will show one how to quickly get down and dirty using GMP.

1. Install GMP. Fortunately, most Linux systems come with GMP installed. However, if you are one of the unfortunate few to not have it installed try doing following (for Fedora systems only).

   yum install gmp gmp-devel
   

   These commands will install GMP and its dependencies on your system.

2. Write a Test Program. Here is a short test program you can use to test BIGNUM.

   #include <gmp.h>
   
   int main () {
           mpz_t sum, x, y;
   
           mpz_init (x);
           mpz_set_str (x, "199999999999999999999999", 0);
           mpz_init (y);
           mpz_set_str (y, "1", 0);
           mpz_init (sum);
   
           mpz_add (sum, x, y);
           gmp_printf ("GMP X + Y = %Zd.n", sum);
   
           return 0;
   }
   

   In a nutshell, this program initializes three (3) GMP Integers (MPZ). X is loaded with a really large number and Y loaded with a smaller one. The sum of both X and Y are stored in the variable sum. The value of the variable sum is then displayed on the screen. More later on.

3. Compile and Build Program. You can them execute the following command to compile and build this test program in one go.

   gcc -o huge huge.c -lgmp
   

   Take note that you have to explicitly link this program with the GMP libraries that are installed in your system.

Then you can run the program in the usual way. Now, it should be easy to write programs that require arbitrary precision arithmetic. You might ask … are these computations efficient? Lets find out.

Here is a test program using regular C arithmetic functions defined in math.h.

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

int main ()
{
        double x,y;

        x = 999999999;
        y = 9;

        printf ("X^Y=%E.n", pow(x,y));

        return;
}

Here is a similar program using GMP instead.

#include <gmp.h>

int main ()
{
        mpf_t x, pow;

        mpf_init (x);
        mpf_init (pow);
        mpf_set_str (x, "999999999", 0);

        mpf_pow_ui (pow, x, 9);

        gmp_printf ("X^Y=%FE.n", pow);

        return;
}

Then we compile and run both program. We use the command time to determine how long each program takes to complete. Here are the results.

Not much difference right. That is some numbers that fit into regular C arithmetic. Nothing special here. Now check this program out. It allows me to specify the number value of X.

#include <gmp.h>

int main (int argc, char *argv[])
{

        if (argc < 2) {
                gmp_printf ("Error: Insufficient argumentsn");
                return 0;
        }

        mpf_t x, pow;

        mpf_init (x);
        mpf_init (pow);
        mpf_set_str (x, argv[1], 0);

        mpf_pow_ui (pow, x, 9);

        gmp_printf ("X^Y=%FE.n", pow);

        return 0;
}

Here are the results:

How come the time it takes to compute a consequently bigger number takes just the same amount of time as a smaller number? This is probably because raising a number (no matter how big) to a single digit number is not a really computationally expensive and it is linearly complex. In English, our computers are still fast enough to handle numbers this big. The only limitation is the data structure we choose to store our numbers.

With GMP, we can definitely store more.

This entry was posted on Monday, August 27th, 2007 at 9:22 am and is filed under Technology, Academics, Parallel Computing, HPC. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.