From: Mathieu Bouchard <matju@...>
Date: 2005-10-31T01:38:54+09:00
Subject: Re: Time for built-in Rational and Complex classes?

On Thu, 27 Oct 2005, Gavin Sinclair wrote:
> I agree with people's comments that implementing GCD and LCM in C
> would be a good start.

excerpt from GridFlow's grid.h :

------------------8<--------cut-here--------8<------------------

// a remainder function such that div2(a,b)*b+mod(a,b) = a and for 
// which mod(a,b) is in [0;b) or (b;0]. in contrast to C-language
// builtin a%b, this one has uniform behaviour around zero.
static inline int mod(int a, int b) {
int c=a%b; c+=b&-(c&&(a<0)^(b<0)); return c;}

// greatest common divisor, by euclid's algorithm
// this runs in log(a+b) number operations
template <class T> static T gcd (T a, T b) {
	while (b) {T c=mod(a,b); a=b; b=c;}
	return a;
}

// greatest common divisor, the binary algorithm. haven't tried yet.
template <class T> static T gcd2 (T a, T b) {
	int s=0;
	while ((a|b)&1==0) { a>>=1; b>>=1; s++; }
	while (a) {
		if (a&1==0) a>>=1;
		else if (b&1==0) b>>=1;
		else {T t=abs(a-b); if (a<b) b=t; else a=t;}
	}
	return b<<s;
}

------------------8<--------cut-here--------8<------------------

BTW if someone has a faster mod() template I would be interested. In 
particular I want to be able to eliminate the conditional jump (of 
shortcutting c) without adding an extra % or / operation.

____________________________________________________________________
Mathieu Bouchard - t�l:+1.514.383.3801 - http://artengine.ca/matju
Freelance Digital Arts Engineer, Montr�al QC Canada