Arithmetic with arbitrarily large integers

C implementation of arithmetic with arbitrarily large integers

A library called GMP implements arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating point numbers. In particular, a subset of GMP supports arithmetic operations on integers whose size is limited only by the available memory in the machine GMP runs on.

GMP is free software developed as a part of the GNU Project and distributed by the Free Software Foundation. Information about the GMP library can be found on the GNU MP Home Page. Complete documentation for GMP is available in the GMP Manual.

Example 1

Here is the program gcd.c:


#include <stdio.h>
#include <gmp.h>

void gcd(mpz_t d, mpz_t x, mpz_t y, mpz_t a, mpz_t b);

int main(int argc, char *argv[])
{
  mpz_t d, x, y, a, b;
  mpz_init(d); mpz_init(x); mpz_init(y); mpz_init(a); mpz_init(b);

  if (argc != 3)
    {
      printf("SPECIFY TWO INTEGERS!\n");
      exit(1);
    }
  else
    {
      mpz_set_str(a,argv[1],10);
      mpz_set_str(b,argv[2],10);
    }

  gcd(d,x,y,a,b);

  printf("       a = ");
  mpz_out_str (stdout, 10, a);
  printf (",\n");
  printf("       b = ");
  mpz_out_str (stdout, 10, b);
  printf (",\n");
  printf("gcd(a,b) = ");
  mpz_out_str (stdout, 10, d);
  printf (".\n");
  printf("Furthermore, gcd(a,b) = ax+by with\n");
  printf("       x = ");
  mpz_out_str (stdout, 10, x);
  printf (",\n");
  printf("       y = ");
  mpz_out_str (stdout, 10, y);
  printf (".\n");
 

  mpz_clear(d); mpz_clear(x); mpz_clear(y); mpz_clear(a); mpz_clear(b);
  return 0;
}

void gcd(mpz_t d0, mpz_t x0, mpz_t y0, mpz_t a, mpz_t b)
{
  mpz_t d1, d2;
  mpz_t x1, x2;
  mpz_t y1, y2;
  mpz_t q;

  mpz_init(d1); mpz_init(d2);
  mpz_init(x1); mpz_init(x2);
  mpz_init(y1); mpz_init(y2);
  mpz_init(q);
  
  if ( (mpz_sgn(a)==0) && (mpz_sgn(b)==0) )
    {
      printf("ERROR: TRIED TO COMPUTE gcd(0,0)\n");
      exit(1);
    }

  if (mpz_sgn(a) < 0)
    mpz_neg (a, a);

  if (mpz_sgn(b) < 0)
    mpz_neg (b, b);

  if (mpz_cmp (a, b) < 0)
    mpz_swap (a, b);

  mpz_set (d0, a); mpz_set_ui (x0, 1); mpz_set_ui (y0, 0);
  mpz_set (d1, b); mpz_set_ui (x1, 0); mpz_set_ui (y1, 1);

  while(mpz_sgn(d1) != 0)
    {
      mpz_fdiv_qr (q, d2, d0, d1);

      mpz_mul (x2,  q, x1);
      mpz_sub (x2, x0, x2);

      mpz_mul (y2,  q, y1);
      mpz_sub (y2, y0, y2);

      mpz_set(d0, d1); mpz_set(x0, x1); mpz_set(y0, y1);
      mpz_set(d1, d2); mpz_set(x1, x2); mpz_set(y1, y2);
    }

  mpz_clear(d1); mpz_clear(d2);
  mpz_clear(x1); mpz_clear(x2);
  mpz_clear(y1); mpz_clear(y2);
  mpz_clear(q);
}

Example 2

The following program prints five integers chosen from the set {1,2,...,n} randomly under the uniform distribution:


#include <stdio.h>
#include <time.h>
#include <gmp.h>

int main(int argc, char *argv[])
{
  long seed; int count;
  gmp_randstate_t california; mpz_t  n, temp;

  gmp_randinit(california, 0, 128); mpz_init(n); mpz_init(temp);

  if (argc != 2)
    {
      printf("SPECIFY AN INTEGER!\n");
      exit(1);
    }
  else
    mpz_set_str(n,argv[1],10);

  /* use time (in seconds) to set the value of seed: */
  time (&seed);    
  gmp_randseed_ui (california, seed);

  for(count=5; count; count--)
    {
      mpz_urandomm (temp, california, n);
      mpz_out_str (stdout, 10, temp);
      printf ("\n");
    }

  gmp_randclear (california); mpz_clear(n); mpz_clear(temp);
  return 0;
}

Back to the table of contents of Vašek Chvátal's course notes