Fast float to int conversion (truncate)

Question

I'm looking for a way to truncate a float into an int in a fast and portable (IEEE 754) way. The reason is because in this function 50% of the time is spent in the cast:

float fm_sinf(float x) {
    const float a =  0.00735246819687011731341356165096815f;
    const float b = -0.16528911397014738207016302002888890f;
    const float c =  0.99969198629596757779830113868360584f;

    float r, x2;
    int k;

    /* bring x in range */
    k = (int) (F_1_PI * x + copysignf(0.5f, x)); /* <-- 50% of time is spent in cast */

    x -= k * F_PI;

    /* if x is in an odd pi count we must flip */
    r = 1 - 2 * (k & 1); /* trick for r = (k % 2) == 0 ? 1 : -1; */

    x2 = x * x;

    return r * x*(c + x2*(b + a*x2));
}

Did you try compiling with `-ffast-math`? Or omit the copysign function and use `lrint()` instead of a (int) cast — Gunther Piez, Feb 18 '12 at 22:50
Your consts are unnecessarily (or over-optimistically) precise. Single precision IEEE754 is only good for 6 significant figures, double precision is good for 15 digits, and long double varies between compilers and architectures, but even at the x86 FPUs native 80bit format is only good for 20 digits. If you need that level of precision, the code will not work in any case, and an arbitrary precision library would be *much* slower. — Clifford, Feb 18 '12 at 23:44
@Clifford: I know they are overly precise, I just always like to calculate 35 digits so I can support anything up to 128bit with just copy/paste. — orlp, Feb 19 '12 at 00:02
you verified that 50% of the time is in the float to int or 50% of the time is related to that line of code? Are you wanting to truncate and stay in float format? that is not too difficult the exponent tells you were your decimal point is in the mantissa, zero everything to the right of that. If the decimal is to the left (number is a fraction, less than one) then just encode zero. — old_timer, Feb 20 '12 at 03:35
@dwelch: I verified that, 50% to 66% of the time gets spent in the cast. — orlp, Feb 20 '12 at 12:40

score 4 · Answer 1 · answered Feb 18 '12 at 23:43

The slowness of float->int casts mainly occurs when using x87 FPU instructions on x86. To do the truncation, the rounding mode in the FPU control word needs to be changed to round-to-zero and back, which tends to be very slow.

When using SSE instead of x87 instructions, a truncation is available without control word changes. You can do this using compiler options (like -mfpmath=sse -msse -msse2 in GCC) or by compiling the code as 64-bit.

The SSE3 instruction set has the FISTTP instruction to convert to integer with truncation without changing the control word. A compiler may generate this instruction if instructed to assume SSE3.

Alternatively, the C99 lrint() function will convert to integer with the current rounding mode (round-to-nearest unless you changed it). You can use this if you remove the copysignf term. Unfortunately, this function is still not ubiquitous after more than ten years.

score 3 · Accepted Answer · answered Mar 28 '12 at 13:34

3

I found a fast truncate method by Sree Kotay which provides exactly the optimization that I needed.

answered Mar 28 '12 at 13:34

orlp

112,504
36
218
315

score 2 · Answer 3 · answered Feb 18 '12 at 22:27

2

to be portable you would have to add some directives and learn a couple assembler languages but you could theoretically could use some inline assembly to move portions of the floating point register into eax/rax ebx/rbx and convert what you would need by hand, floating point specification though is a pain in the butt, but I am pretty certain that if you do it with assembly you will be way faster, as your needs are very specific and the system method is probably more generic and less efficient for your purpose

answered Feb 18 '12 at 22:27

Ryan

2,755
16
30

3

What makes you think that bitwise hacking in assembler will be faster than the native FP instructions (I'm assuming x86 here) to convert from float to integer? – Oliver Charlesworth Feb 18 '12 at 22:31
@OliCharlesworth There is indeed a trick to do this very efficiently using SSE intrinsics if you're willing to put some constraints on the input. The reason why casting is so slow is because the language requires that the output be correct for all inputs. – Mysticial Feb 18 '12 at 22:36
@Mysticial It'd be nice if one of you would share the trick for this and the limitations - sounds interesting enough. – Voo Feb 18 '12 at 22:42
@Voo I thought I had seen an [SO question](http://stackoverflow.com/q/9161807/922184) about that before. But it turns it out was the other way around. (`int` -> `float`) The second answer is the one to look at. Although it's `int` -> `float`, it can be easily inverted. I use a similar trick for `double` -> `__int64` conversions. – Mysticial Feb 18 '12 at 22:52
@Mysticial Thanks, really interesting. Though I totally agree with Paul R's comment below that answer `clever, if a little obfuscated`. Real clever that. – Voo Feb 19 '12 at 02:17

score 0 · Answer 4 · answered Feb 18 '12 at 22:41

0

You could skip the conversion to int altogether by using frexpf to get the mantissa and exponent, and inspect the raw mantissa (use a union) at the appropriate bit position (calculated using the exponent) to determine (the quadrant dependent) r.

answered Feb 18 '12 at 22:41

Doug Currie

40,708
1
95
119

Dough Currie: I am very dearly sorry, in my haste I forgot to copy one line of my function. I also use the value of the `int` to get a free `fmod`. `fmod` itself was way too slow. – orlp Feb 18 '12 at 22:45
@nightcracker: Have you tried `nearbyint()` for that part? Converting to integer and back to floating point again is going to be slow. – caf Feb 18 '12 at 23:08
@caf: Actually, the latter is very fast. Only converting to integer is very slow. – orlp Feb 18 '12 at 23:10

Fast float to int conversion (truncate)

4 Answers4

Linked