libgmp.md

LibGMP

On LibGMP

• Official Website

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.

• G -> GNU, for GNU's Not Unix
  • Free and open source Unix ecosystem
  • Includes GCC, Glibc, others
• MP -> Mixed Precision
  • ints have no fixed size
  • ∴ not necessarily any maximal value
  • ∴ not necessarily finite
  • ∴ may be regarded as integers
• We only care about
  • integers (or signed integers) and
  • naturals (or unsigned integers).
  • On RSA
    • Most arithmetic may proceed unsigned
    • Critical arithmetic, is very challenging without signed values.
• One of our first mentions of available memory.
  • We have thus far written memory safe code.
  • Not intentionally, but by not introducing memory management.
  • LibGMP introduces memory management in a way.

Usage

• We will begin with this Containerfile

FROM ubuntu

RUN apt update && apt install gcc vim python3 -y

• We will follow this tutorial
• We will first use this file:

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

int fact(int n){
  int i = 1, p = 1;
  for (; i <= n ; ++i){
    p = p * i;
  }
  return p;

}

int main(int argc, char * argv[]){
  int n = atoi(argv[1]); /* Extract the command line argument */
  printf ("%d ! = %d \n", n, fact(n));
  return 0;
}

• We can evaluate this vs. Python

fact = lambda n : n * fact(n-1) if n else 1

• We find that

  • C factorial of 10 and Py factorial of 10 are both 3628800 (decimal representation)
  • C factorial of 20 is negative, -2102132736
  • Py factorial of 20 is positive, 2432902008176640000

• We implement a factorial use the mpz_t type supported by the <gmp.h> library.

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

int main(){

  char inputStr[1024];
  mpz_t n;
  int flag;

  (void)printf ("Enter your number: ");
  (void)scanf("%1023s" , inputStr);

  /* 1. Initialize the number */
  (void)mpz_init(n);
  (void)mpz_set_ui(n,0);

  /* 2. Parse the input string as a base 10 number */
  flag = mpz_set_str(n,inputStr,10);

  /* Print n */
  printf ("n = ");
  mpz_out_str(stdout,10,n);
  printf ("\n");

  /* 3. Add one to the number */
  mpz_add_ui(n,n,1); /* n = n + 1 */

  /* 4. Print the result */
  printf ("n + 1 = ");
  mpz_out_str(stdout,10,n);
  printf ("\n");

  /* 5. Square n+1 */
  mpz_mul(n,n,n); /* n = n * n */

  printf ("(n + 1) ^ 2 = ");
  mpz_out_str(stdout,10,n);
  printf ("\n");

  /* 6. Clean up the mpz_t handles or else we will leak memory */
  mpz_clear(n);

  /* 7. Return 0 to denote non-error exist status */
  return 0;
}

• When we try to compile, we yield the following error:

fact.c:1:10: fatal error: gmp.h: No such file or directory
    1 | #include <gmp.h>
      |          ^~~~~~~
compilation terminated.

• We need to install GMP!
• I just looked it up and found https://askubuntu.com/questions/207724/how-to-install-the-latest-gmp-library-in-12-04.

sudo apt-get install libgmp3-dev

• On containers:
  • We do not use sudo
  • We use modern ubuntu with apt instead of apt-get

apt install libgmp3-dev

• I simply updated my Containerfile.

FROM ubuntu

RUN apt update && apt install gcc vim python3 libgmp3-dev -y

Compiler flags

• Compile with -lgmp

gcc fact.c -o -lgmp

I/O

• We will use mpz_import

void mpz_import (mpz_t rop, size_t count, int order, size_t size, int endian, size_t nails, const void *op) 

void * mpz_export (void *rop, size_t *countp, int order, size_t size, int endian, size_t nails, const mpz_t op)

• I did this, after some testing

mpz_import(m0, S, -1, sizeof(uint64_t), 0, 0, a);

mpz_export(c, NULL, -1, sizeof(uint64_t), 0, 0, m0);

Final File

/* 4096_t.c */

#include <gmp.h>
#include "4096_t.h"

uint64_t bigadd(uint64_t *in0, uint64_t *in1, uint64_t *sum) {
        mpz_t m0, m1;
        memset(sum, 0, 4096 / 8);
        mpz_init(m0);
        mpz_init(m1);
        /* mpz_inits(m0, m1, NULL) */
        mpz_import(m0, S, -1, sizeof(uint64_t), 0, 0, in0);
        mpz_import(m1, S, -1, sizeof(uint64_t), 0, 0, in1);
        mpz_add(m0,m0,m1);
        mpz_export(sum, NULL, -1, sizeof(uint64_t), 0, 0, m0);
        mpz_clear(m0);
        mpz_clear(m1);
        return 0;
}

uint64_t bigsub(uint64_t *min, uint64_t *sub, uint64_t *dif) { return 0; };
uint64_t bigmul(uint64_t *in0, uint64_t *in1, uint64_t *out) { return 0; };
uint64_t bigquo(uint64_t *num, uint64_t *den, uint64_t *quo) { return 0; };
uint64_t bigrem(uint64_t *num, uint64_t *den, uint64_t *rem) { return 0; };