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.

## No comments:

## Post a Comment