Re: [Boost-users] Rational: [PATCH] Eliminate excessive calls to gcd and add operator%

Subject: Re: [Boost-users] Rational: [PATCH] Eliminate excessive calls to gcd and add operator%
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2012-05-20 18:56:40

AMDG

On 05/20/2012 11:58 AM, Mario Lang wrote:
> I am using boost/rational.hpp in my code to represent musical time with
> rational numbers.  I have found some possible improvements.  These
> improvements have accumulated into a small patch which I'd like to
> present for review.  I think it is worth applying.  There doesn't appear
> to be a maintainer for rational.hpp though, so I am writing to the list.
> 
> The story: In my application I need a remainder operation. Looking at
> rational.hpp and its work-horse operators.hpp it became rather obvious
> that rational.hpp can and (in my opinion) should implement operator%=
> and friends.  operator%= can easily be defined as
> 
> return operator-= (other * rational_cast<int_type>(*this / other));
> 
> I have been using this definition for operator%= successfully in my code
> for quite a while.

I'm not sure that this is a good idea.  For
integers, an important property is the relationship
between / and %:

(a / b) * a + a % b = a

This doesn't hold with your operator%.
In fact, your definition of % for rational
would also work for floating point, but
notice that C uses a named function, fmod
instead of an operator.  I'd prefer to
go that route with rational.

>  During a profiling session it showed up which made
> me think a bit more.  Actually, the current way how rational.hpp
> implements mixed-mode operators is a waste of performance.  It calls the
> corresponding operator with a temporary rational where the denominator
> is always equal to 1.  However, this means that there are excessive
> (unnecessary) calls to boost::math::gcd performed by the operators.  For
> instance, addition of two rational numbers needs two calls to gcd.  On
> the other hand, addition of a rational number and an integer can be
> performed without any gcd at all (n += d * i).  Similarily,
> multiplication of two rational numbers needs two calls to gcd, while
> multiplication of a rational with an integer only needs one call to gcd.
> So it is definitely worth it to actually define the mixed mode operators
> not in terms of the already existing operators but reimplement them with
> the unnecessary calls to gcd removed.
> 

This part looks good.

> After this, the definition of operator%=(const rational&) results in one
> less call to gcd (because there is one mixed-mode multiplication
> involved) and the definition of operator%=(param_type) saves two
> unnecessary calls to gcd since there is one mixed-mode multiplication
> and one mixed-mode division involved.  Obviously, all code that involves
> mixed-mode operators benefits from these changes.
> 
> As a side effect of reading code I noticed that the definition of
> operator=(param_type) (assign from an integer) also does unnecessary
> gcd.  It currently calls assign(n, 1) which itself calls normalize()
> which does gcd.  However, as above, we know that there is no need to
> calculate gcd of (n, 1) since it will always be 1.  So I changed the
> definition of operator=(param_type) to directly assign the parameter to
> num and set den to 1, instead of calling assign().  Another useless call
> of gcd squashed!
> 

This looks good.

> On top of these, we can observe that now that boost::rational provides
> operator%= it is actually an instance of ordered_euclidean_ring_operators.
> 
> Comments and committers welcome.
> 

In Christ,
Steven Watanabe