Implementing a templated "round" function?

[Jef Driesen]

I need to implement a function to implement the rounding of floating point
values. At the moment i have two different implementations, depending on the
type of the return value (integer or double).

// Integer calculation (fast)
int iround(const double x) {
return (x>=0 ? static_cast<int>(x + 0.5) : static_cast<int>(x + 0.5)
}
// Floating point calculation (slow)
double dround(const double x) {
return (x>=0 ? floor(x + 0.5) : ceil(x + 0.5)
}

But then I have 2 different functions for the same functionality. To solve
this, I created a template function with 2 specialisations:

template <typename T> T round(const double x);
template <>
int round(const double x) {
return iround(x);
}
template <>
double round<double>(const double x) {
return dround(x);
}

I can add specialisations for the other data types (float, long, short,
char, signed/unsigned,...) as well. I did not add a 'default'
specialisation, because the round function is only usefull for numeric
types. At this time my function accepts only double precision floating point
values, and I would like to have equivalent functions for float, double and
long double. I did add a second template parameter S for the source type:

template <typename T, typename S>
T round(const S x) {
...
}

The problem is now how do I implement this function?

I could add a specialisation for every combination of S and T, but this is a
lot of work, and there are only 4 usefull implementations possible:
- S and T are floating point type -> implementation using floor/ceil
(dround)
- S is a floating point type and T an integer type -> implementation using
static_cast (iround)
- S is an integer type and T is an integer or floating point type -> simply
static_cast to T
- otherwise no implementation is necessary (should not compile if this is
possible, to prevent e.g. round<double>(std::complex) )

I was thinking of using only one 'default' specialisation and using
std::numeric_limits:

template <typename T, typename S>
T round(const S x)
{
if (std::numeric_limits<S>::is_integer)
// Integer type needs no rounding.
return static_cast<T>(x);

// Find rounding error.
const S round_error = std::numeric_limits<S>::round_error();

if (std::numeric_limits<T>::is_integer) {
// Integer calculation (fastest).
return (x>=0 ? static_cast<T>(x + round_error) : static_cast<T>(x +
round_error)
} else {
// Floating point calculation (slower).
return (x>=0 ? floor(x + round_error) : ceil(x + round_error)
}
}

But this will results in a performance degradation if the compiler is unable
to optimize (eliminate) the 'if' statements. And the function has also an
implementation for data types other then integer and floating point types.
Any advice on this problem?

 

[Siemel Naran]

I need to implement a function to implement the rounding of floating point
values. At the moment i have two different implementations, depending on the
type of the return value (integer or double).

// Integer calculation (fast)
int iround(const double x) {
return (x>=0 ? static_cast<int>(x + 0.5) : static_cast<int>(x + 0.5)
}
// Floating point calculation (slow)
double dround(const double x) {
return (x>=0 ? floor(x + 0.5) : ceil(x + 0.5)
}

The first function looks suspect because it loses precision. Anyway, if the
true and false clauses of operator ? are the same, you can avoid the
comparison.

Anyway, have you measured the time difference?

But then I have 2 different functions for the same functionality. To solve
this, I created a template function with 2 specialisations:

template <typename T> T round(const double x);
template <>
int round(const double x) {
return iround(x);
}

Should that be

template <>

template <>
double round<double>(const double x) {
return dround(x);
}

I can add specialisations for the other data types (float, long, short,
char, signed/unsigned,...) as well. I did not add a 'default'
specialisation, because the round function is only usefull for numeric
types. At this time my function accepts only double precision floating point
values, and I would like to have equivalent functions for float, double and
long double. I did add a second template parameter S for the source type:

template <typename T, typename S>
T round(const S x) {
...
}

The problem is now how do I implement this function?

I could add a specialisation for every combination of S and T, but this is a
lot of work, and there are only 4 usefull implementations possible:
- S and T are floating point type -> implementation using floor/ceil
(dround)
- S is a floating point type and T an integer type -> implementation using
static_cast (iround)
- S is an integer type and T is an integer or floating point type -> simply
static_cast to T
- otherwise no implementation is necessary (should not compile if this is
possible, to prevent e.g. round<double>(std::complex) )

I was thinking of using only one 'default' specialisation and using
std::numeric_limits:

template <typename T, typename S>
T round(const S x)
{
if (std::numeric_limits<S>::is_integer)
// Integer type needs no rounding.
return static_cast<T>(x);

// Find rounding error.
const S round_error = std::numeric_limits<S>::round_error();

if (std::numeric_limits<T>::is_integer) {
// Integer calculation (fastest).
return (x>=0 ? static_cast<T>(x + round_error) : static_cast<T>(x +
round_error)
} else {
// Floating point calculation (slower).
return (x>=0 ? floor(x + round_error) : ceil(x + round_error)
}
}

But this will results in a performance degradation if the compiler is unable
to optimize (eliminate) the 'if' statements. And the function has also an
implementation for data types other then integer and floating point types.
Any advice on this problem?

It's worthwhile to check the assembly to see if your compiler does the
optimization.

Anyway, you can put the numeric_limits::is_integer into the function or
class template argument list. Here is the idea:

template <typename T, typename S>
inline
T round(const S x) {
return generic_round<T, S,T::is_integer>(x);
}

template <typename T, typename S, bool is_integer>
inline
T generic_round(const S x);

template <typename T, typename S>
inline
T generic_round<T,S,true>(const S x) {
const S round_error = std::numeric_limits<S>::round_error();
return T(x + round_error);
}

etc

 

[Jef Driesen]

The first function looks suspect because it loses precision.

IIRC the floating point representation of integer numbers is exact. If you
are talking about a possible under/overflow in the conversion from double to
int, you are correct. In the final code I will probably add code to prevent
under/overflows:

const R minimum = std::numeric_limits<int>::min();
const R maximum = std::numeric_limits<int>::max();
if (x < minimum)
return minimum;
else if (x > maximum)
return maximum;

Anyway, if the true and false clauses of operator ? are the same,
you can avoid the comparison.

This is a typo. The last "+0.5" should become "-0.5" in both functions.

Anyway, have you measured the time difference?

Yes I did and dround is (1.89 times) faster than iround, unless I
static_cast the result of dround to int (factor 0.73).

Should that be

template <>
int round<int>(const double x) {

Another typo. But it don't think my syntax was incorrect.

is

It's worthwhile to check the assembly to see if your compiler does the
optimization.

MSVC7.1 does the optimization. I don't know about other compilers.

Anyway, you can put the numeric_limits::is_integer into the function or
class template argument list. Here is the idea:

template <typename T, typename S>
inline
T round(const S x) {
return generic_round<T, S,T::is_integer>(x);
}

template <typename T, typename S, bool is_integer>
inline
T generic_round(const S x);

template <typename T, typename S>
inline
T generic_round<T,S,true>(const S x) {
const S round_error = std::numeric_limits<S>::round_error();
return T(x + round_error);
}

etc

Looks interesting to me.

 

[Marcin Kalicinski]

// Integer calculation (fast)

int iround(const double x) {
return (x>=0 ? static_cast<int>(x + 0.5) : static_cast<int>(x + 0.5)
}
// Floating point calculation (slow)
double dround(const double x) {
return (x>=0 ? floor(x + 0.5) : ceil(x + 0.5)
}

Why do you think the 1st version is integer calculation and is fast? It is
floating point calculation just as the 2nd version is.

What's more, on the 80x86 platform the first version will be actually a lot
slower than the second.

Have you profiled them?

Cheers,
Marcin

 

[Siemel Naran]

Yes I did and dround is (1.89 times) faster than iround, unless I
static_cast the result of dround to int (factor 0.73).

Sorry, I'm a bit confused. I thought dround is slower. Are you saying that
dround is faster, but if you cast the return from double to int, then it is
slower?

IIRC the floating point representation of integer numbers is exact. If you
are talking about a possible under/overflow in the conversion from double to
int, you are correct. In the final code I will probably add code to prevent
under/overflows:

const R minimum = std::numeric_limits<int>::min();
const R maximum = std::numeric_limits<int>::max();
if (x < minimum)
return minimum;
else if (x > maximum)
return maximum;

Anyway, these checks will make iround slower, right? Maybe then dround is
better?

 

[Jef Driesen]

// Integer calculation (fast)

Sorry, I'm a bit confused. I thought dround is slower. Are you saying that
dround is faster, but if you cast the return from double to int, then it is
slower?

In my previous post I swapped the time values by accident. But my
conclusions where still correct. A small example:

const double x = 1.5;
double a = dround(x); // Relative time is 0.73
int b = iround(x); // Relative time is 1.00
int c = static_cast<int>(dround(x)); // Relative time is 1.89

If the result needs to stay in floating point format, dround is faster. If
the result needs a static_cast to integer, iround is faster. I need this
conversion from double to int in many of my image processing applications,
where calculations are performed on floating point numbers (to prevent
under/overflows, integer divisions,...) but the final result should be an
integer type (often unsigned char).

double

Anyway, these checks will make iround slower, right? Maybe then dround is
better?

Of course, but if I do add these checks to iround, I should add them also in
the code above when casting the result of dround to int.

 

[Jef Driesen]

// Integer calculation (fast)

Why do you think the 1st version is integer calculation and is fast? It is
floating point calculation just as the 2nd version is.

What's more, on the 80x86 platform the first version will be actually a lot
slower than the second.

Have you profiled them?

The first version is indeed slower than the second version one, because of
the (slow) cast from double to int. But in my applications (image
processing) I need to store the results of my calculations as integers. If I
use the second version, I need a static_cast anyway. In this case it's
faster to use the first function .