4 ms·
There are lots of cute tricks for rounding to integer and to integral values. A few of my favorites: 1. Round to an integral value according to the current ro
by stephencanon 14y ago
There are lots of cute tricks for rounding to integer and to integral values. A few of my favorites:
1. Round to an integral value according to the current rounding mode, allowing inexact to be set (rintf( ) in C, pretty close to what Pascal is going for in his example):
// All suitably large floats are integral already.
if (fabsf(x) >= 0x1.0p23f) return x;
// Otherwise we can force rounding to occur in the
// units position by simply adding and subtracting
// 2**23 with the correct sign.
const float forceRound = copysignf(0x1.0p23f, x);
return x + forceRound - forceRound;
If you want the result as an integer and it’s in the [-2^23, 2^23] range, you can just rip out bits 0:22 of the floating-point representation of x + forceRound via a mask, which is really simple (faster than hardware convert-to-integer instructions on some architectures!).
If the calls to fabsf and copysignf look like hazards to you, keep in mind that good compilers lower them to one or two bitwise operations on most architectures (though I tend to write these routines in assembly to avoid any risk of missed optimization).
2. Round to nearest, ties away from zero (roundf( ) in C, which can be annoying because it doesn’t correspond to a hardware rounding mode on most architectures):
// All suitably large floats are integral already.
if (fabsf(x) >= 0x1.0p23f) return x;
// Now that we know (int32_t)x cannot raise invalid,
// we can use that to get truncf(x).
const float truncated = (int32_t)x;
// Compare the residual to 0.5 to determine if the
// result needs to be adjusted away from zero.
if (fabsf(x - truncated) >= 0.5f)
return truncated + copysignf(1.0f, x);
return truncated;
This is also a pretty close analogue to what Pascal was considering. I like my implementation more because it doesn’t spuriously raise the inexact flag (whereas Pascal’s implementation does). This still isn’t a complete implementation of roundf( ), as it gets the sign of zero wrong when the result should be negative zero. Left as an exercise to the reader.
3. Since people asked about doing the rounding using integer operations elsewhere in the discussion: assume the input is known to be in the interesting range already, and that we have some utility functions for converting between a floating-point number and its encoding (which is a NOP architecturally, but requires a union or memcpy or other type-punning in C):
const uint32_t xRep = toRep(x);
const uint32_t xAbs = xRep & 0x7fffffff;
const uint32_t xSgn = xRep & 0x80000000;
// If |x| > 2**23, or x is Inf or NaN the result is x.
if (xAbs > 0x4b000000) return x;
// If |x| < 1.0f, the result is +/-0 if |x| < 0.5f and
// +/-1 otherwise.
if (xAbs < 0x3f800000) {
if (xAbs < 0x3f000000) return fromRep(xSgn);
return fromRep(xSgn | 0x3f800000);
}
// Otherwise, use the exponent of x to identify the
// units bit of x.
const int exponent = xAbs - 0x3f800000 >> 23;
const uint32_t unitsBit = 0x00800000 >> exponent;
// "Add 0.5 to x” by adding half the units bit to the
// encoding. If this doesn’t change the exponent it
// really is equivalent to adding 0.5. If it carries
// into the exponent, then it’s not actually the same,
// but it still does what we need it to do. After
// “adding 0.5”, we simply mask off the fractional
// bits to get the result.
return fromRep(xAbs + (unitsBit >> 1) & -unitsBit);
This doesn’t set inexact, obviously, which makes it unsuitable for some uses (but actually nearbyint( ) is required not to set inexact, so this is pretty useful there). It’s actually even less code than it looks like; C tends to make this sort of thing relatively verbose. On ARM a complete implementation is about 12 instructions, for example.
N.B. although I write this sort of stuff professionally, I’m just sketching code here without even checking if it compiles. Test before use.
- pascal_cuoq 14y agoSir, you are stealing my next blog post and then some. Ah, well...
- stephencanon 14y agoSorry! As consolation, I’ll tell you the following (totally obvious unless you understand floating-point, in which case it is shocking) little lemma I happened upon the other day: assuming default rounding, the result of x+x+x+x is exact. And please do write your next blog post anyway, I love this sort of thing =)
- pascal_cuoq 14y agoIs • one of the four operations +, -, * , /? For -, x-x-x-x is -2x, representable if there is no overflow, and obtained with only exact steps. For +, the result is 4x, again representable. The second and third operations do not seem like they are going to be exact but the error might just compensate. Should this be studied by case analysis on the last bit of the significand? For * and /, I just don't see it.
- deleted 14y ago[deleted]
- stephencanon 14y agoThat should have been +. Fixed. As you say: > The second and third operations do not seem like they are going to be exact but the error might just compensate. Should this be studied by case analysis on the last bit of the significand? That’s exactly right. There’s a simultaneously ugly and clever proof by looking at the 3 low-order bits of the intermediate terms. I haven’t found a more elegant one yet. It follows trivially that x+x+x+x+x is correctly rounded, but it breaks down when you get to x+x+x+x+x+x.
- pascal_cuoq 14y agoI don't know if this can be considered an improvement over brute-force case analysis: If x is a power of two, then each floating-point operation in x+x+x+x is exact. If x isn't a power of two: fl(3x) = 3x + e1 |e1|≤ulp(3x)/2 fl(fl(3x) + x) = fl(3x) + x + e2 |e2|≤ulp(4x)/2 (ulp(4x) because once set apart the case when x is a power of two, there is no way fl(fl(3x) + x) can be in a binade other than the binade of 4x) Now there are two cases: - if 3x is in the binade of 2x, then ulp(3x) = ulp(2x) = ulp(4x)/2. In this case fl(fl(3x) + x) is within (3/4)ulp(4x) of 4x. The only floating-point number within (3/4)ulp(4x) of 4x is 4x. - if 3x is in the binade of 4x: Then the real number 3x cannot be a midpoint for its binade. If floating-point numbers of the binade of 4x are all multiples of 2^p, then all midpoints for this binade are multiples of 2^(p-1). But x is of the form n * 2^(p-2), and 3x = (3n/2) * 2^(p-1) cannot be a midpoint. Since 3x is not a midpoint for its binade, we can in fact improve the inequality |e1|≤ulp(3x)/2 into |e1|<ulp(3x)/2. It follows that fl(fl(3x) + x) is in this case again strictly within ulp(4x) of 4x. I do feel that this is a little hand-wavy as proofs go. In particular, I set apart the case when x is a power of two to make it clear that fl(fl(3x) + x) and 4x are in the same binade in the rest of cases, but I wonder whether it's possible that fl(3x) is a power of two and whether that deserves special attention.