Showing posts with label Monte Carlo. Show all posts
Showing posts with label Monte Carlo. Show all posts

Sunday 17 July 2016

Program 2: Monte Carlo Algorithm

MTech VTU Advanced Algorithm Lab (2nd sem)

Design, develop, and write a program to implement a Monte Carlo algorithm to test the primality of a given integer and determine its performance.

#include<stdio.h>
#include<stdlib.h>
int Modular_Exponentiation(int, int, int);
void Binary(int, int *, int *);

int main()
{
            int n, res;
            printf("\n Enter a no n:");
            scanf("%d", &n);
            if(n <= 0)
            {
                        printf("\n Please enter a +ve number!!!");
                        exit(0);
            }
            res = Modular_Exponentiation(2,n-1,n);
            if(n == 1)
                        printf("\n %d is prime!!!", n);
            else if((res % n) == 1)
                        printf("\n %d is prime!!!", n);
            else
                        printf("\n %d is not prime!!!", n);
            return 0;
}

int Modular_Exponentiation(int a, int b, int n)
{
            int c, d, bin[20] = {0}, k, i;
            c=0, d=1;
            Binary(b, bin, &k);
            for(i = k; i >= 0; i--)
            {
                        c = 2*c;
                        d = (d*d) % n;
                        if(bin[i] == 1)
                        {
                                    c++;
                                    d = (d*a) % n;
                        }
                        printf("\n i=%d, bi=%d, c=%d, d=%d", i, bin[i], c, d);
            }
            return d;
}

void Binary(int b, int *bin, int *k)
{
            int i = 0, n = b;
            *k = 0;
            *bin = 0;
            while(b != 0)
            {
                        bin[i] = b % 2;
                        *k = *k+1;
                        b /= 2;
                        i++;
            }
            *k = *k-1;
            printf("\n Binary equivalent of %d is:", n);
            for(i = *k; i >= 0; printf("%5d", bin[i--]) );
}


Output:

Case 1:
 Enter a no n:
 Binary equivalent of 4 is:    1    0    0
 i=2, bi=1, c=1, d=2
 i=1, bi=0, c=2, d=4
 i=0, bi=0, c=4, d=1
 5 is prime!!!

Case 2:
 Enter a no n:9
 Binary equivalent of 8 is:    1    0    0    0
 i=3, bi=1, c=1, d=2
 i=2, bi=0, c=2, d=4
 i=1, bi=0, c=4, d=7
 i=0, bi=0, c=8, d=4
 9 is not prime!!!