Topic: GCD of two integers a & b

Properties of GCD:

• gcd(0,0) = 0;
• gcd(u,v) = gcd(v,u);
• gcd(u,v) = gcd(-u,v);
• gcd(u,0) = |u|;

Steps:

• Decompose the problem into a number of simple tasks.
• Specify the order in which these(simple) tasks are to be solved.
• Decomposition into many ways.

Ex:
Problem: Find GCD of two integers a & b
Sub-task: Find GCD of two non-negative integers a & b

Algo:
Auxiliary variables x & y

Steps:

1. set x->a and y->b
2. If y ≠ 0, then

• Decrease y and change x in such a way that they remain non-negative and that the value of gcd(x,y) remains the same
• repeat step 2

    3.  If y = 0, set gcd(x,y) -> x
Decompose step 2 further

Key points:

If x & y are two integers, 
 then q = x div y;
         r = x mod y;

=> x = (x div y) * y + x mod y;
 => x mod y = x - (x div y) * y;

=> gcd(x,y) = gcd(y, x-(x div y)*y) = gcd(y, x mod y);  [ x mod y < y ]

Algo in equations:

1. Set x -> a, y -> b
2. If y ≠ 0, then

• set r -> x mod y
• set x to y
• set y to r
• Repeat step 2

   3. If y = 0, set gcd(a,b) -> x

Softwares:

OpenMP in C-programming - check it for parallel computing

Loop Invariants and graphs:

will be updated soon.....