Re: Time for built-in Rational and Complex classes?

On Oct 30, 2005, at 8:38 AM, Mathieu Bouchard wrote:

> 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駘:+1.514.383.3801 - http://artengine.ca/matju
> Freelance Digital Arts Engineer, Montr饌l QC Canada
>

I have used the second algorithm you show.  Here it is again:
http://www.nist.gov/dads/HTML/binaryGCD.html

-Charlie