Never been to DZone Snippets before?

Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

About this user

Alexandru Scvortov

« Newer Snippets
Older Snippets »
Showing 1-1 of 1 total  RSS 

GCD: Divide et Impera

Calculates the Greatest Common Denominator (GCD) of an array of ints using a Divide at Impera approach.

Time: O(lg(n))
Memory: O(n)

   1  
   2  #include <stdio.h>
   3  
   4  int gcd(int a, int b) {
   5  	int r = a % b;
   6  	while (r) {
   7  		a = b;
   8  		b = r;
   9  		r = a % b;
  10  	}
  11  	return b;
  12  }
  13  
  14  int gcdv(int *v, int p, int r) {
  15  	if (r == p + 1) {
  16  		//printf("%d,%d: %d\n", p, r, gcd(v[p], v[r]));
  17  		return gcd(v[p], v[r]);
  18  	}
  19  	
  20  	if (r == p) {
  21  		//printf("%d: %d\n", r, v[r]);
  22  		return v[p];
  23  	}
  24  	
  25  	int q = (p + r) / 2;
  26  	//printf("%d,%d: %d\n", p, r, gcd(gcdv(v, p, q), gcdv(v, q + 1, r)));
  27  	return gcd(gcdv(v, p, q), gcdv(v, q + 1, r));
  28  }
  29  
  30  int main(int argc, char *argv[]) {
  31  	int v[] = {45, 60, 125, 345, 65, 9875, 4555};
  32  	
  33  	printf("GCD: %d\n", gcdv(v, 0, 6));
  34  	
  35  	return 0;
  36  }
  37
to c GCD algorithm divide et impera by scvalex on Sep 28, 2007
« Newer Snippets
Older Snippets »
Showing 1-1 of 1 total  RSS