Re: greatest common divisor

[Achim Gaedke <Achim dot Gaedke at physik dot tu-darmstadt dot de>]

Thanks for the answer!

I think, it is worth to have an own section in gsl. In deed some of 
these algorithms are pretty easy, but it is always better to implement 
them once. Sometimes there are trivial pitfalls, these could be avoided.
How many people have written a function that counts the bits set in a 
given integer??? I have written this function more than 10 times last 
year.... The GCD case is more demanding.

On the search for GCD functions, I found the arbitrary precision 
implementation too. GSL functions are not designed for these needs, so I 
would restrict a gsl collection to 32 or 64 bit variables. But the 
implementation should be done reliably. Maybe some prime factor 
functions could be included?

What is the other peoples opinion? Is there place/need for such a small 
section?

Yours, Achim

(Thanks for release 1.6 !)

Linas Vepstas wrote:

> On Wed, Jan 05, 2005 at 02:34:04AM +0100, Achim Gaedke was heard to remark:
>  
>
> > Hi!
> >
> > I was not able to find a standard UNIX function for the greatest common
> > divisor, so I have written one. I put it into the specfunc section, but
> >    
>
>
> FYI,
>
> I've been putting together a small library of various number-theoretic
> function implemented as 32-bit ints, which, besides gcd, includes things
> like the mobius function, the liouville function, the divisor function,
> euler's totient, etc.  I was curious if anyone has any interest in
> these.
>
> Note that these types of functions are usually implemented in arbitrary
> precision math libs, which is where the cryptographers usually work. 
> In my case, I'm exploring fractals, so, for me, I needed speed, and 
> thus went for a 32-bit implementation.  Most of these routines are
> really pretty darn simple, so I'm not taking about a big intellectual
> excercise or lots of hard work; but still, I figure there might be 
> interest, viz. possibly as a fast small-integer number-theory library
> inside of GSL.
>