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
(*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