I need a faster round() in C++ (G++ on OS X 10.6)

[aluminumstudios]

Hi everyone.  I'm hoping that the talented people here can lend a hand.

I have been working on a fractal rendering program in C++ using G++ on Mac OS X 10.6

I include <math.h> and use round() inside several loops extensively.  There is no way to move the calls to round() outside of the loops.

When I sample the running program under Activity Monitor, I see that the calls to round are accounting for up to 30% of execution time under some circumstances.

I tried making a faster rounding function by adding .5 to my double then casting it as an int (truncating the decimal part.)  This resulted in a blocky, jagged image whereas round() results in a smooth, proper image.  This didn't work for my application.

So my question is, are there any good math libraries that have a faster round function than comes with GCC/G++? 

Since OS/X is Unix based I can generally make easy use of any libraries for *nix.

Thanks!

[David Makin]

I'm not 100% certain but I think if you do this:

 SInt32 intval
 double testval = 21.5123f

Then if you do:

  intval = testval

The resulting intval will use whatever "rounding" method the current fpu rounding function (FRNDINT) is set to use at the time - i.e. depending on the RC field:

00 = Round to nearest, or to even if equidistant (this is the initialized state)
01 = Round down (toward -infinity)
10 = Round up (toward +infinity)
11 = Truncate (toward 0)

The setting at runtime in your code will *probably* be 00 unless it's explicitly been set to something else by a compiler directive or previously executed runtime code.

The reason I think your code using round() is so slow is because it is compiling run-time code to explicitly set the RC field to 00 all the time.

Also rounding (FRNDINT) is inherently slow anyway and should be avoided in time-sensitive code wherever possible.

(Just to put that in perspective I *think* I recall it's slower than add, sub, abs or mul but not as slow as other functions)

[aluminumstudios]

Thanks for the reply.

I thought that setting 'int = double' results in a truncating and the decimal portion of the double being dropped in the new int value

[David Makin]

Thanks for the reply.

I thought that setting 'int = double' results in a truncating and the decimal portion of the double being dropped in the new int value

My suggestion was an educated guess, you could only really find out for sure by reading reams of C++ or Objective C documentation or simply testing to see what happens

[Tglad]

I tried making a faster rounding function by adding .5 to my double then casting it as an int (truncating the decimal part.)  This resulted in a blocky, jagged image whereas round() results in a smooth, proper image

It should be exactly the same (for +ve reals), is it simply that you need to cast it back to a double after you have cast it to an int, so that future operations are done on the double.

If you have -ve reals then you need to subtract .5 before casting when it is negative.

[hobold]

You can allow GCC to be a bit sloppy with the IEEE-754 floating point standard with the command line flag "-ffast-math". In rare cases, this can affect the accuracy of your results. But most of the time, it just creates more opportunities for automatic optimization by the compiler with no ill side effects.

[MisterCat]

You can do fairly precise rounding by taking a look at the bitwise values of your doubles.  While you'll need to dig into the precise conventions of the computer you're using, I'm sure it's IEEE 754.  Reading the wikipedia entries for floating point representation will give you much better background than I can here and will probably make more sense.

In short, IEEE doubles are stored in this manner:
sign (1 bit), exponent (11 bits), number (52bits).  Let's call them S,E,N.  The double x is calculated from:
x=S*2^(E-1023)*(1.N).  IEEE 754 doubles use an implied 1 in the mantissa.  

1.  Step one, Calculate the 'real' exponent by getting the value of bits 2-12 and subtracting 1023.  Call this ER.
2.  If ER<= -2, set x to 0 and end.  
3.  If ER is -1,0 or 1, set x to 1 and end
4.  If ER >1, you have to look at on bit(ER+1).  If this bit is 0, x=int(x)-S*1, if the bit is 1, x=int(x)+S*1, where S is the sign of x.

Take a look at
http://babbage.cs.qc.edu/IEEE-754/Decimal.html
This page will help you work with the IEE 754 representation and let you experiment with various numbers to make sure you're understanding meaning of the different bits in your doubles.

On the positive note, doing the bitwise operations isn't all that difficult after you wade through it once.  Step 1 is actually the hardest, as you have to pad out the exponent bit field to 16 bits with 5 zeros , cast it as an int and then subtract 1023.

Good luck,
MisterCat

[knighty]

There is nice trick to perform rounding on a double that I found in an kc script that comes with evaldraw:
double round(double x){return x+3*2^51-3*2^51;}
Of course, you need to disable optimizations in order for it to work, or write it in assembler.

[aluminumstudios]

Thanks for the replies.

Before, when adding .5 to a float and casting it to an int (truncating it) made my image look a little blocky, I didn't investigate it thoroughly.  The problem may have been another bug elsewhere.  I'm trying that again, and in a few (low quality) test images, it really didn't look all that different from round().  I'll have to test some more and if it's OK, I'll go with that!

Does anyone know why round() is so slow in C++?

[hobold]

I guess round() is slow because it implements a specific, slightly unusual, mode of rounding (exact something.5 is rounded away from zero).

You could try rint(), which uses whatever rounding mode is currently selected (typically one that the hardware supports efficiently).

[Nahee_Enterprises]

You can do fairly precise rounding by taking a look at the bitwise values of your doubles.
.......   Take a look at
http://babbage.cs.qc.edu/IEEE-754/Decimal.html

Greetings, and Welcome to this particular Forum !!!   

Thank you for the information, and the link to IEEE-754 Floating-Point Conversion page.
 

[twinbee]

Not sure if this is what you're looking for (converts from double to int, though there's a method from float to int as well), but:

unsigned ftoi(double d)
{
    d += 4503599627370496.0;  // 1 << 52
    return (unsigned &)d;
}

I found it much faster than other standard techniques like casting with (int) etc.