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>(c onst 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>(s td::complex) )

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

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

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

if (std::numeric_l imits<T>::is_in teger) {
// 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?

--
Jef Driesen

[Siemel Naran]

"Jef Driesen" <je********@nos pam.hotmail.com > wrote in message
news:cj******** **@ikaria.belne t.be...

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 <>
int round<int>(cons t double x) {
template <>
double round<double>(c onst 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>(s td::complex) )

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

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

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

if (std::numeric_l imits<T>::is_in teger) {
// 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(c onst S x);

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

etc

[Jef Driesen]

"Siemel Naran" <Si*********@RE MOVE.att.net> wrote in message
news:CS******** *************@b gtnsc05-news.ops.worldn et.att.net...

"Jef Driesen" <je********@nos pam.hotmail.com > wrote in message
news:cj******** **@ikaria.belne t.be...

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.

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_li mits<int>::min( );
const R maximum = std::numeric_li mits<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).

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 <>
int round<int>(cons t double x) {

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

template <>
double round<double>(c onst 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>(s td::complex) )

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

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

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

if (std::numeric_l imits<T>::is_in teger) {
// 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.

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(c onst S x);

template <typename T, typename S>
inline
T generic_round<T ,S,true>(const S x) {
const S round_error = std::numeric_li mits<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

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>(c onst 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>(s td::complex) )

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

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

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

if (std::numeric_l imits<T>::is_in teger) {
// 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?

--
Jef Driesen

[Siemel Naran]

"Jef Driesen" <je********@nos pam.hotmail.com > wrote in message

"Siemel Naran" <Si*********@RE MOVE.att.net> wrote in message

"Jef Driesen" <je********@nos pam.hotmail.com > wrote in message

// 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)
}

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).

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_li mits<int>::min( );
const R maximum = std::numeric_li mits<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)

> 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)
> } 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).

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).

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_li mits<int>::min( );
const R maximum = std::numeric_li mits<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?

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)

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?

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 .