Fall 2006 Building blocksGMP and pari library programmingBoth GMP (Gnu Multi-Precision library) and Pari’slibrary are powerful tools for C programming.Generally, GMP is not as featureful, but it sits veryclose to the metal. Pari gives you much wider rangeof basic types and functions on those types.COP 4342Fall 2006 Building blocksGMP programmingGMP has three basic types: floating point, integers,and rationals.Functions are also divided by the same threeclasses.COP 4342Fall 2006 Building blocksGMP programmingThe types are identified by the following namingconvention:mpz_t # type for integersmpz_* # names for integer functionsmpf_t # type for floatsmpf_* # names for floating point functionsmpq_t # type for rationalsmpq_* # names for rational functionsCOP 4342Fall 2006 Building blocksWriting a GMP programWriting a C program with GMP is easy if a bit tedious.First, you need to pull in the headers:#include <unistd.h> // or stdio.h and stdargs.h should work#include <gmp.h>COP 4342Fall 2006 Building blocksWriting a GMP programNext you declare variables:#include <unistd.h> // or stdio.h and stdargs.h should work#include <gmp.h>int main(){mpz_t x, y; // types are simple to use}COP 4342Fall 2006 Building blocksWriting a GMP programNow you must initialize any variables before use:#include <unistd.h> // or stdio.h and stdargs.h should work#include <gmp.h>int main(){mpz_t x, y;mpz_init(x); // critical, otherwise errors are unpredictablempz_init(y); //}COP 4342Fall 2006 Building blocksWriting a GMP programCompiling and linking is simple:gcc -o prog prog.c -lgmpCOP 4342Fall 2006 Building blocksWriting a GMP programWhen creating a subroutine, make sure you clearthe variables after you finish using them (despite thestatic declaration, that’s just a pointer to the actualdynamically allocated memory for the variable):COP 4342Fall 2006 Building blocksWriting a GMP program#include <unistd.h> // or stdio.h and stdargs.h should work#include <gmp.h>void func(){mpz_t x;mpf_t y;mpz_init(x);mpf_init(y);mpz_clear(x); // otherwise you have a memory leak!mpf_clear(y); //return;}COP 4342Fall 2006 Building blocksSimple example program#include <unistd.h>#include <gmp.h>char *answers[3] = { "composite", "probably prime", "prime" } ;int main(int argc, char *argv[]){int result;mpz_t n;mpz_init(n);mpz_set_str(n,argv[1],10); // set the value of n from a string in base 10result = mpz_probab_prime_p(n,20); // do a primality test with 20 repetitionsgmp_printf("%Zd is %s\n",n,answers[result]);}COP 4342Fall 2006 Building blocksInteger functions: assignmentvoid mpz_set (mpz_t result, mpz_t op) # z = zvoid mpz_set_ui (mpz_t result, unsigned long int op) # z = uintvoid mpz_set_si (mpz_t result, signed long int op) # z = signed intvoid mpz_set_d (mpz_t result, double op) # z = doublevoid mpz_set_q (mpz_t result, mpq_t op) # z = q (via truncation)void mpz_set_f (mpz_t result, mpf_t op) # z = f (via truncation)int mpz_set_str (mpz_t result, char *str, int base)# return 0 means string was completely a number# in the indicated base, -1 means that it wasn’tvoid mpz_swap (mpz_t result1, mpz_t result2) # swap two valuesCOP 4342Fall 2006 Building blocksInteger functions: arithmeticvoid mpz_add (mpz_t sum, mpz_t op1, mpz_t op2) # z = z + zvoid mpz_add_ui (mpz_t sum, mpz_t op1, unsigned long int op2) # z = z + uintvoid mpz_sub (mpz_t diff, mpz_t op1, mpz_t op2) # z = z - zvoid mpz_sub_ui (mpz_t diff, mpz_t op1, unsigned long int op2) # z = z - unitvoid mpz_ui_sub (mpz_t diff, unsigned long int op1, mpz_t op2) # z = uint - zvoid mpz_mul (mpz_t result, mpz_t op1, mpz_t op2) # z = z * zvoid mpz_mul_si (mpz_t result, mpz_t op1, long int op2) # z = z * signed intvoid mpz_mul_ui (mpz_t result, mpz_t op1, unsigned long int op2) # z = z * uintvoid mpz_neg (mpz_t result, mpz_t op) # z = -zvoid mpz_abs (mpz_t result, mpz_t op) # z = |z|COP 4342Fall 2006 Building blocksRational number functions: arithmeticvoid mpq_add (mpq_t sum, mpq_t addend1, mpq_t addend2) # q = q + qvoid mpq_sub (mpq_t difference, mpq_t minuend, mpq_t subtrahend) # q = q - qvoid mpq_mul (mpq_t product, mpq_t multiplier, mpq_t multiplicand) # q = q * qvoid mpq_div (mpq_t quotient, mpq_t dividend, mpq_t divisor) # q = q / qvoid mpq_neg (mpq_t negation, mpq_t operand) # q = - qvoid mpq_abs (mpq_t result, mpq_t op) # q = |q|void mpq_inv (mpq_t inverted_number, mpq_t number) # q = 1 / qCOP 4342Fall 2006 Building blocksFloating point functions: arithmeticvoid mpf_add (mpf_t sum, mpf_t op1, mpf_t op2) # f = f + fvoid mpf_add_ui (mpf_t sum, mpf_t op1, unsigned long int op2) # f = f + uintvoid mpf_sub (mpf_t diff, mpf_t op1, mpf_t op2) # f = f - fvoid mpf_ui_sub (mpf_t diff, unsigned long int op1, mpf_t op2) # f = uint - fvoid mpf_sub_ui (mpf_t diff, mpf_t op1, unsigned long int op2) # f = f - uintvoid mpf_mul (mpf_t result, mpf_t op1, mpf_t op2) # f = f * fvoid mpf_mul_ui (mpf_t result, mpf_t op1, unsigned long int op2) # f = f *uintvoid mpf_div (mpf_t result, mpf_t op1, mpf_t op2) # f = f / fvoid mpf_ui_div (mpf_t result, unsigned long int op1, mpf_t op2) # f = uint / fvoid mpf_div_ui (mpf_t result, mpf_t op1, unsigned long int op2) # f = f / uintvoid mpf_sqrt (mpf_t root, mpf_t op) # f = sqrt(f)void mpf_sqrt_ui (mpf_t root, unsigned long int op) # f = sqrt(uint)void mpf_pow_ui (mpf_t result, mpf_t op1, unsigned long int op2) # f = f ˆ fvoid mpf_neg (mpf_t negation, mpf_t op) # f = - fvoid mpf_abs (mpf_t result, mpf_t op) # f = |f|COP 4342Fall 2006 Building blocksComparison functionsint mpz_cmp (mpz_t op1, mpz_t op2) # returns negative if op1 < op2,# 0 if op1 == op2# positive if op1 > op2int mpz_cmp_ui (mpz_t op1, unsigned long int op2) # same for uintint mpf_cmp (mpf_t op1, mpf_t op2) # same for floatsint mpf_cmp_ui (mpf_t op1, unsigned long int op2) # sameint mpq_cmp (mpq_t op1, mpq_t op2) # same for rationalsint mpq_cmp_ui (mpq_t op1, unsigned long int num2, unsigned long int den2)COP 4342Fall 2006 Building blocksOther useful functionsint mpz_probab_prime_p (mpz_t N, int repetitions)# returns 0 if N definitely composite# 1 if probably prime# 2 if definitely primevoid mpz_nextprime (mpz_t result, mpz_t N)# result is next prime greater than Nvoid mpz_gcd (mpz_t result, mpz_t op1, mpz_t op2)# result is GCD(op1,op2)int mpz_jacobi (mpz_t a, mpz_t b)# jacobi (a/b) Calculate the Jacobi symbol (a/b). This is defined only for b odd.int mpz_legendre (mpz_t a, mpz_t p)# legendre (a/p)COP 4342Fall 2006 Building blocksOther useful functionsunsigned long int mpz_remove (mpz_t result,