Programming Question - Compute GCD - Davide SpataroDavide Spataro

Programming Question: Compute the Greatest Common Divisor of two integers (easy)

This question is divided in two parts: you will first asked to write a function that computes the GCD withouth any space/time constraints. The second part will be more challenching, asking for not using multiplication or division or addition.

Part1: write a function that takes two integers as input and returns their gcd using the famous Euclidean algorithm.

Part 2: compute the Greatest Common Divisor of two integers without using multiplication addition or division operators (easy)

Solutions:

Show Solution

Solution part 1:

It is based on the fact that $a,b \in \mathbb{N} \;s.t.\; a=qb+r$ then $gcd(a,b) = gcd(b, r)$

//a > b
int gcdEuler(int a, int b){
	int rem;
	while(b>0){
		rem=a%b;
		a=b;
		b=rem;
	}
	return a;
}

Solution part 2:

Solution is based on the followings:
$a,b \in \mathbb{N}$ then both $a$ and $b$ are even then $gcd(a,b)$ is clearly $2 \times gcd(\frac{a}{2},\frac{b}{2})$ .
If $a$ is even and $b$ is odd then the $gcd$ cannot be even and therefore $gcd(a,b) = gcd( \frac{a}{2},b)$ , respectively $gcd( a,\frac{b}{2})$ . If both numbers are odd and $a > b$ then $gcd(a,b) =gcd(a-b,b)$ , respectively $gcd(a,b-a)$

The function is recursive and use bit shift for multiplying and dividing and use bit AND operator to check whether a number is odd or even.

int gcd(int a, int b){
	
	if(a==0)
		return b;
	if(b==0)
		return a;
	
	//both even
	if(!(a & 0x1) & !(b & 0x1))
		return (gcd(a>>1,b>>1) <<1); 
        //both odd 
        if( (a & 0x1) & (b & 0x1)) if(a>b)
		return gcd(a-b,b);
	else
		return gcd(a,b-a);
		
	if(!(a & 0x1))
		return gcd(a>>1,b);

	//if(!(b & 0x1))
		return gcd(a,b>>1);
		
	
	
	
}

Davide Spataro

Non multa sed multum

Programming Question - Compute GCD

Part1: write a function that takes two integers as input and returns their gcd using the famous Euclidean algorithm.

Solutions:

Solution part 1:

Solution part 2:

Join the Discussion Cancel reply