Re: dlw_gcd review comments.

From: helmut.zeisel_at_[hidden]
Date: 2001-09-27 02:16:03

--- In boost_at_y..., "Hubert HOLIN" <Hubert.Holin_at_B...> wrote:
> Paris (U.E.), le 26/09/2001 (just in time...).
> 
> 
> 		I recommend Boost accept that library. 

I also recommend to accept it.

> 
> 		A few comments are in order, however:
> 
> 1) use of the "%" operator might lead to portability problems, as 
noted 
> by another; the best fix would probably be to move to positive 
numbers 
> sooner.
>

I do not see a real problem with "%".
AFAIK, the only implementation dependeny occurs when
at least one of the arguments is negative.
Since (a/b)*b + a%b == a and abs(a%b)<abs(b),
the Euclidian algorithm will converge to the correct value,
we just do not know whether the result will be positive
or negative.

OTOH, the line

    IntegerType  a_abs = ( (a < zero) ? -a : +a );

is too restrictive for non-integer-like types.
It should be a kind of normalization, not an absolute value:

Consider e.g. a fictive nostd::complex<int>
which is an Euclidian ring with
4 divisiors of one: 1,i,-1,-i;
hence there are 4 equivalent solutions for the gcd.

E.g., a=3+4i is equivalent to -4+3i, -3-4i, and 4-3i.
They are clearly different from abs(3+4i)=5,
and "a<zero" maxes no sense for complex numbers.

Anyway, the implementation allows an escape via
template specialization...

> 
> 5) use of this library for other integer-like type (say a "big 
> integer") necesitates to specialise internals of this library for 
this 
> other type, instead of requiring that the new type defines the 
> necessary algorithmic behavior; this is bad from an orthogonality 
point 
> of view; this is also the converse of our discussion about sync's 
> template template parameter :-)
> 

The runtime-gcd as it is works fine with my big integer class
without any additional specialization,
so IMHO the default implementation of the template
is suitable for every integer-like type.

Maybe one could achieve some performance gain
by specialization, but this is a different topic.

Helmut