Modular Exponentiation

For performing exponentiation we can take the linear route or we can take the binary route. What is the main idea behind it

Suppose you are to calculate ( x^p) mod n

You can do this in a linear fashion and using the following property of modular operations
(a*b) mod n = (a mod n * b mod n) mod n
 but that is O(n) time complexity and we can do better. 

Observe the following
exponential(x,p) = exponential(x,p/2)<<2           // if p is even
                               x*exponential(x,(p-1)/2)<<2 // if p is odd

Now the number of times the functions is called is log2(b), which is a definite improvement over the linear case. But we can still do better by expressing the power in its binary form. Read the following wikipedia article for understanding
right to left binary method

following is C++ code for modular exponentiation .

Here is problem on SPOJ using the above concept http://www.spoj.com/problems/ZSUM/ . 

Comments are welcome.

           

sieve of eratosthenes

Sieve of Erathosthenes : a find of quick ways to generate primes upto generally less than a million . below is the code for it .

what the sieve of eratosthenes does it that it eliminates all the multiples of previously determined primes .

optimization 1: start eliminating numbers  for prime i starting from i*i
optimization 2: i ends at i*i<upper since any composite below upper will atleast have one prime factor below sqrt(upper)
optimization 3 : any prime can be of type 6k+1 or 6k+5 only .

Using these optimization I have coded the following program which on my i-5 machine takes 2.5s to calculate primes upto 9e7.

Permutations

Hey following is a method using backtracking to print all permutations of a number in C++.

// A program using backtracking to generate premutations of 1,n numbers .

#include <cstdio>

#define MAXCANDIDATES 20

void backtrack(int a[],int k,int n);

int is_a_solution(int k,int n);

void process_solution(int a[],int n);

void construct_candidates(int a[],int c[],int k,int n, int *ncandidates);

int main()
{
    int n;
    scanf("%d",&n);
    int a[n+1];
    for(int i=1;i<n;i++)a[i]=0;
    backtrack(a,0,n+1);
    return 0;
}

int is_a_solution(int k,int n)
{
return (k==(n-1));
}

void process_solution(int a[],int n)
{
     printf("{");
     for(int i=1;i<n;i++) printf("%d,",a[i]);
     printf("\b}\n");
}

void construct_candidates(int a[],int c[],int k,int n,int *ncandidates)
{  
     bool in_perm[n];
     for(int i=1;i<n;i++)in_perm[i]=false;
     for(int i=1;i<k;i++)in_perm[a[i]]=true;
   
     *ncandidates =0;
     for(int i=1;i<n;i++){
           if(!in_perm[i]){
                           c[(*ncandidates)++]=i;
           }
   
     }
}
void backtrack(int a[],int k,int n)
{
     int c[MAXCANDIDATES];
     int ncandidates;
   
     if(is_a_solution(k,n)){
             process_solution(a,n);
     }
     else {
          k=k+1;
          construct_candidates(a,c,k,n,&ncandidates);
          for(int i=0;i<ncandidates;i++){
             a[k]=c[i];
             backtrack(a,k,n);
             }
     }    
}