6 replies to this topic

[Nils Pipenbrinck]

Hi folks!

I'm searching for a fast way to find out if a number stored in a float is near to an integer. Basically something like this:

bool IsNear = (fabs(float_number - (int)float_number) <= some_small_value)

I don't really care about the rounding mode, the exact value of some_small_value ect. Only a heuristic is needed. I wouldn't even mind a code that gives false negatives at times. No handling for NAN's and denormals required as well.

To the background: The system I'm working on is quite slow when it comes to FPU stuff. It's not soft-float but close from a performance point of view. To translate it from my system to the x86 world, imagine an FPU operation would be 5 to 10 times slower than the integer counterpart. Rounding and transfering data from and to the FPU are even slower.

So - how do I find out fast if a float is roughly representable as an integer. I need this to accelerate a function which can be done a lot quicker with whole numbers (a special case occures quite often).

Any ideas? Where are the IEEE 754 wizards? :-)

Nils

[pater]

Can we make an assumption about the order of magnitude of the represented values? I.E. anything that has an exponent that it larger than 15 is always close to an integer, because of the precision (although this is irrelevant, since anything > 2^32 is cannot be represented as int anyway). Anything with an exponent smaller than 0 can never be close to an int (except to 0, which can be tested quite easily).

[Nick]

Could you tell us a bit more about the function you want to optimize?

One trick I'm thinking of is to add a large number and subtract it again so the less significant bits gets pushed out. Using 12582912 this actually results in rounding to integer. So you could use it like this:

void main()

{

    float value = 1.001f;


    const float large = 12582912;

    const float small = 12582912 / 256;


    volatile float x = value + large;

    volatile float y = x - large;


    volatile float z = value + small;

    volatile float w = z - small;


    bool isNear = (y == w);

}

[Razor]

That's a cute trick Nick!

I don't suppose you get away with just using fixed point?

[dave_]

I think nick's done the closest thing you can. (although I'm not sure it works for big values?)
Is it actually quicker?

[.oisyn]

Why volatile?

But Nils talked about FPU operations being much slower than their integer counterparts. Another trick is to check the upper N bits (depending on your threshold) starting from the decimal point. If these bits are all zeroes or all ones then it is near an integer.

template<unsigned N> bool IsNear(float f)
{
	unsigned dword = reinterpret_cast<unsigned &>(f);
	unsigned exponent = (dword >> 23) & 0xff;
	unsigned topbit = 0;

	if (exponent < 127-N) 
		return true;	// number is close enough to 0
	else if (exponent < 126)
		return false;	// number is too far away from 0, but less than 0.5
	else if (exponent == 126)
		topbit = 1 << (N - 1); // we need the implicit 1 for values in the range 0.5..1

	const unsigned ones = 0x7fffffff >> (31 - N);
	unsigned mantissa = dword & 0x007fffff;
	unsigned value = ((mantissa >> (150 - N - exponent)) & ones) | topbit;
	return value == 0 || value == ones;
}

Note that this code rounds upwards - if you use N=2, which means a threshold of 0.25, 1.75 is determined to be near an integer while 2.25 is not (but the float preceding 2.25 is). It also might be subject to more optimizations . For N=1, this function always returns true (duh )

[Nils Pipenbrinck]

Thanks, mates.

Oisyns code looks pretty good for my requirement. I think working out an estimate about the integer nearness over the mantissa would have been the way to go. However, it's not relevant for me anymore. I've used the detection code as posted at the thread start and I delivered today, so there is no chance to change it anymore.

In practice it's no bottleneck (also it still is slower than it could be). I was more an academic challenge and I was curious what you guys would come up with.

I like booth ways. Oisyn cracks the number into the component, and Nick does the arithmetic thing. Neat solutions.

Nils