Re: dlw_int/dlw_gcd review summary

From: helmut.zeisel_at_[hidden]
Date: 2001-10-10 08:42:40

--- In boost_at_y..., "Moore, Paul" <paul.moore_at_a...> wrote:

> 
> Speaking as the author of the rational library, I guess should
> express my view here.
> 

Good idea.

> My key design goals when developng the rational library were (1) 
simplicity,
> (2) MSVC compatibility, and (3) compatibility with some 
(hypothetical)
> "unlimited integer" type.

I agree that these goals are important.

> 
> The unlimited integer compatibility requirement is to ensure that it 
*is*
> possible to use rationals to avoid strange rounding and boundary 
case
> issues. This isn't possible with limited-precision integers. But as 
I don't
> have the time or expertise to write a good long-integer class, I 
just make
> sure it's *possible* to do so.

One main criterion for the unlimited integer class
I am working on is indeed that it is compatible
with your rational class.
This compatiblity came indeed almost by itself,
so your rational class is well designed with
respect to this.

I have only one problem with rational_cast, see 

http://groups.yahoo.com/group/boost/message/15728

for details.

An other problem is that my unlimited integer
class and your rational class
do not work under MSVC++.
Since this compatibility is very important
to you, I will try to fix that problem.

> 
> Given all of the above, I have some serious reservations about using 
the GCD
> library in rational.hpp. First of all, if there is a MSVC 
compatibility
> problem, I definitely won't be using it. Sorry, but that's absolute.

The good news is that these problems are only
with respect to the compile time gcd.
Your rational class uses run time gcd and
this works under MSVC.

> Secondly, all the talk I've seen of Euclidean rings and the like, is
> worrying. Goal (1) "simplicity" means that rational.hpp
> will stay resolutely
> targeted at integers - not rings,
> or any other mathematical construct.

Now your are speaking particulary to me.
The funny thing is that gcd becomes even simpler
when writing a general version for Euclidean rings.

Below you write

> OK, your GCD handles negative numbers - mine doesn't need to
> (as rational
> has always normalised to positive before calling it).
> There may be a cost to
> this generality, which can't be avoided.

Exactly the check for negative numbers makes the
algorithm less general, not more general as expected.
If this check is ommited,
the algorithm will be simpler and will work
for every Euclidean ring.
When entering negative integers, you just will not
know whether the result will be positive or
negative, but for your rational class this will not matter
at all since you are calling it for positive numbers only.

> (I'm
> a mathematician by training, so I do know the terms, btw -
> I'm just glossing
> over details here to avoid obscuring the point).
> I worry that if the GCD
> library is stated as supporting rings or whatever,
> there will be a knock-on
> tendency to ask for rational to support them as well.
> And I don't  want to
> spend my time rejecting such requests
> (and explaining my reasons each time).

I might have asked in the future ;-)
I think that most of the class works indeed for more
general structures, I did, however, not yet check in detail.

> 
> PS Stop press: I just looked at the library.
> First impression - bloody hell,
> that's complicated!

This was also my first impression.
Most of the complicated stuff, however, is needed
for the compile time gcd, not for the run time gcd.

> 
> In more detail (looking only at gcd_integer -
> I simply don't follow the
> rest!) the requirements on the integer type are very different to my
> version.
> Mine needs (informally) operator%, assignability, operator+=,
> operator< against (literal) 0, and while(m) to work. Yours needs
> constructibility from a literal 0 (via static_cast),
> unary operator+ and
> operator-, < and != comparisons vs zero, operator%= operator+,
> as well as
> the strange trick at the end of using a+b (which, btw, is the *only*
> dependency on operator+) to avoid testing for zero. 

I like your original implementation more than the
implementation in gcd_integer.
OTOH, the additional requirements
are reasonable for integer like types
and are in particular statisfied by my unlimited integer type.

> (How can you be sure
> that adding zero is cheaper than a zero test?)

It is indeed more expensive for my unlimited integer type.
The time critical part, however, is the modulos operation,
so the overall performance will hopefully
not change much.
I did, however, not make any performance tests.

> 
> No, I'm afraid that unless a more detailed read of the class
> (which I'll try
> to do at some stage!) changes my mind,
> I don't want to use this GCD in place
> of the one in rational.hpp.

As I understand, it was a major design goal for
dlw_gcd to factor out this code to
a more general class.
So this situation is not very staisfying.

Helmut