Reading Guide : Generic Algorithms

This page consists of some generic algorithm which just should be known by everybody !


Euclids GCD Algorithm :

To find the GCD of m and n :

1. Set p = m and q = n;
2. Until q exactly divides p, Repeat
    2.1 p =q and q= (p % q) .
3. Terminate with answer = q.

Java Implementation :

public static int gcd (int m, int n)
{
 int p = m;  int q = n;

while (p % q != 0) {
 int r = p % q;
 p =q;  q= r; }
return q;
}

Power Algorithm :

To calculate m to the power of n :

1 One way to do is .. multiply m to itself n times: Iterative Algorithm :
Space complexity = O(1); Time complexity = O(n);

public static int power(int m, int n)
{
int p = 1;
for(int i=0; i<n;i++)
 p = p * m;
return p;
}

2. Another way is to be a little smart about it : Smart power algorithm :
Space Complexity : O(1). Time complexity : O(log n)

public static int power(int m, int n){
int p =1 ; int q = m; int r = n;
while ( r > 0 ){
if (r %2 == 1)  p = p * q;
r = r/2;  q = q * q;
}
return p;
}

Recursive Power Algorithm :

1. To calculate m to the power of n recursively :

public static int power (int m, int n){
if ( n ==0 )
 return 1;
else
 return m * power(m,n-1);
}

2. The Smart Recursive power algorithm :

public static int power ( int m, int n) {

if( n== 1)
 return 1;
else {
int p =  power(m,n/2);
if (n % 2 == 1)
 return m * p *p;
else
 return p * p;
}
}

Change the base of an integer.

To change the base of an integer, the algorithm is as follows :

let i be the integer and b be the base to which it is being rendered to.

1. if i < 0 , render - sign and then render -i
2. if  0 <= i <=r , render i as it is.
3. if i>=r , let d = i % r. render i/r and then render d.