Install GMP in ubuntu 12.04 and GMP factorial code (for arbitrary very large number)

Firstly, I have to install this thingy.. GMP.., because our homework about fermat factorization method.. for arbitrary large number we know its impossible to use ordinary variable type.. e.g. int, float, double, even long doube, or unsigned long int.. , and GMP is the answer from google.. wahaha

OK, the installation actually you can find it in official web.. but for simplicity we can use:

sudo apt-get install libgmp3-dev

just it..

so we can try now.. for example, if we have to write code in C++ for factorial (n!) our simple result just like this:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
int fact(int n){
  /* 
     Function: fact (n) 
     Returns: n! 
  */
 
  int i;
  int p = 1;
 
  for (i=1; i <= n ; ++i){
    p = p * i;
  }
  return p;
 
}
 
int main(int argc, char * argv[]){
  int n;
 
  if (argc <= 1){
    /* Check if user has a command line argument */
    printf ("Usage: %s <number>", argv[0]);
    return 2;
  }
 
  n = atoi(argv[1]); /* Extract the command line argument */
 
  assert( n >= 0);
 
  /* Print the factorial */
  printf ("%d ! = %d \n", n, fact(n));
 
  return 1; 
}

or using recursif:

#include<iostream>
using namespace std;

double fact(double n){ //double: agar bisa untuk int(n) yang besar
    double res;
    if (n == 0){res = 1;}
    else{res = n*fact(n-1);}
    return res;}
    

int main(){
    int n;
    cout << "Program menghitung n!\n" ;
    cout << "n = "; cin >> n;
    if (n < 0) {cout << "hanya untuk bilangan n>=0\n"; return 0;}
    else{cout << n << "! = " << fact(n) << "\n";}
    
    return 0;}

that program work just fine.. but shamefully for n < 17, if you don't believe me just try it yourself.. -_-! for example 17!, the result is -288522240 (why?),
so if I want to calculate 2507! –my birthday.., how is it possible?
the answer: yes, we can use GMP library.. hehehe..
factorial code using GMP:

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

void fact(int n){
    int i;
    mpz_t p; /* mpz_t is type defined for GMP integers. It is a pointer to the internals of GMP integer data structure */

    /* Initialize the number */
    mpz_init_set_ui(p,1); /* set p = 1 */
    for (i=1; i<=n; ++i){
        mpz_mul_ui(p,p,i); /* p = p*i */ 
        /* multiplication using GMP */
    }

    printf("%d! = ", n); /* print result */
    mpz_out_str(stdout,10,p);
    printf("\n");
    
    /* Clear up the mpz_t handles or else we will leak memory */
    mpz_clear(p);
}

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

    if (argc <=1){
        printf("Usage: %s <number> \n", argv[0]);
        return 2;
    }

    n = atoi(argv[1]);
    assert(n>=0);
    fact(n);

    return 1;
}

compile:

gcc -o fact_gmp fact_gmp.cpp -lgmp

try (2507!):

./fact_gmp 2507

Result: (~7437 digit of integer)

2507! = 10053809200816771023335980463786967410378763471223140545276689810352767955682714738854845919702447388514103856302311436370194582203486599165304119022951945824540771684713138953363593259393009875501930245302225541111641257286000126065876980879115726288508140332417816557806899879372971840561324541119780215451900682272706550489727388765539373406732259864780581250932337142106146589421794901330863102974791254371806318228696516898533843000936135139955578676395215422723779302419728333455254548480792666470752066365282571926022718788805655867264458326142773408083335807526002307437761490631351584362276970818550624441750529711199750666383988736362020482077265166512991024913794697526054837358524206342491564544788210588041861060719338315348528335973897324033104218918656759522047565109971209923229071656144051287074680450031177238147066590022787193629686470638520662850913072748959476942077889610721548965425121921377964971389686227946311127299075433642001125714190923538131060557834621360673074674995409391680768876035404380118259207607392120636457817229580312143327749921018795304994761978492602805084948914233461374168049539391346142544895061192292126876046680979622789482524958937432277190475075720743020153367735877179808617262047745120320271742627452669210779999438266213729875918388318824973832984679371914063783624890731216241931739691882996742218427529320122155725380171952099036906718178075305768022173389928234984384900751583462352051011301410020306199883023553333711812882137269092652750336171201733644865911932051918482371956920284097476681995743702624844928913865481181471059053093088229247792614324626908761786173313549854463597167376124694988276722756890806145556355307798118961057058355488841180186869692588185696264630255610004509658970083620364198704408042736643154604657266956753010658065634625501483048513636542891794930729845206716406952256193173696104271546923339256545113917360603782272566051188300257669789378849343610840184187645616414669627917381422001312063422876727276554481338539151985392268040978798907530189294518176580549371791989011382323339713643075658085235404319147674155540418662258550547187657907912060740118125568983085170982703568136050352991798458250842004965046263077707006510036189660002952082769211864684149235235407241728546976007886121858779460056358178578791205395163225356165850855359066538986283618980621122067144416046655587737391198882627458622644979703638776695380705805260063538246318906600963209406016890199294946569693682012540827892159275722214459467094582254286192867695078128617574073912607020140068057324580142506927721617343057074227252776363848574909668510907050707146974808932843268358798207693869374629719418475423162386631021177667796382309631867172071636549262567211138251879961024217177415101369111065004569552756209687984618039610677876307153093002347402024780094087101781889706315815709759241417167079149401890136851730708416058402041246705977424028950471004721962182059474648427699438846879350640680007104859130931388992624564281621007773978058516283685622781434911439220286872466279314701083264570570635505917180487334552500637741423060103148475598579304800874820736532752773256395526667257495915661269647154071463723525524830218935384463608070861689610856211930598418603781967291416736237061885715653681110597393943624689392679880310805598706568283396134080012891331446269972028793290064341129182893027190597642957087200895298861758059601164522861272965866874731277182269856750699882676190951161144239974196515912083495358280976467123790384698246961805603440698869332807069211785897141004542459901730901963980115659297974575953028762218609835888724334435276533213473355217073528354305066920156667540732319624554331695336179417253545832924156740045064086029138007293144447763227731333548974133572497955776237904682562209138728250825125408804237879206291243043960063409996758310618050636410140276093859168915672501314917024717305576313868080750233802961894165784510580796231456967389888693282192296094591712809550838523635099150139346921379184893881585543373915383836215863868377512603799743650728866827276371815486313067506302113292756744800849472334665104413688860627615920202193496951107152850123634321897299924702993465413303586810120517765297813278149936319815721599973246913701880837543763335637714515421505743606525371140445864300899271042019558740235412601861193891340244318668826737349041219296864757988860164109136094993559881246759891610255880014105247717586246208209877373345068965402797697990871479941839036602999898670764380500576116726566268799540063469762038870470174617739278805589290411001885824021082843318236193048023486747281771177889973908012429696383270098064500395536963324621493418631043657074004246106018260599673499179653489924001154352060588219387179170923849850286449278038454134665299002452060750842043661177258889204552081451388351114617869318725969562919001546294528735644424080181640681637730362526167081942018034249221719702644174601785169480931442616391862380955903488365429328145187512503674766621007749439606841894270275034370271419505141853029658851350663618807566484914873620451258840699794146859019251979543802558636053493361750465903224415821157707353062888823123339705418065467220796641747336255322679284760414209197573160442941375924619236668134540529519765422123008660231066928030409193905649933220410935928630856531440776455809692261222837486466974726445402447507251667476704815762277402889209967705691510000505847782776672358075485341170947193459219099157610895374931924271716865417612423369731316593488536571933710316423398767020114668271341912778019029879604920198050437829114505283307074114969732173726564098359429481997209989950243326543470469654370517682201038815643691650811640139528027289124625180279001295981671260606344930656722411336790751934520157627898470549055874030340462094246513608993665061968790837302008560259457575685074308322034642824193310669242836275224890224238205528049471027744408419327467714291344251546293097565659626702939965861643781857874994977997718505195766993619695835521738641968562960553432802978568370883099582962603940148558519852628266390294784435370563512250258743714323497471318572298144399340445935752871142468742418832908014963029340147312538428778707644029295349728371689664078043496136083754931214094492834931748750319033111309648116402494610766642944225874899308855828554137831683466880215191336051713408487466812575020585815187116533801664696890799812737067704627151995601367329736854543060977306845098621996231276022581851221582789686853878728711021267581436480913818588859257317204257689398336010266818058522417189044662207089626275902784234267156416643102940542802801572157720215199330805690340356889287203510495268454729990965093379618299389203200797205119432757518937071603152724187185397724417855117820961039099930123334524029898046032117822914560000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

hehehe.. it works!

ref: http://www.cs.colorado.edu/~srirams/classes/doku.php/gmp_usage_tutorial

About these ads

c / c++, gmp, large number, ubuntu

March 1, 2013

9 Comments