Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net