What is correct by common sense: (int) blabla * 255.99999999999997 or round(blabla*255)?

Question

Recently I found this interesting thing in webkit sources, related to color conversions (hsl to rgb):

http://osxr.org/android/source/external/webkit/Source/WebCore/platform/graphics/Color.cpp#0111

const double scaleFactor = nextafter(256.0, 0.0); // it's here something like 255.99999999999997
// .. some code skipped
return makeRGBA(static_cast<int>(calcSomethingFrom0To1(blablabla) * scaleFactor), 

Same I found here: http://www.filewatcher.com/p/kdegraphics-4.6.0.tar.bz2.5101406/kdegraphics-4.6.0/kolourpaint/imagelib/effects/kpEffectHSV.cpp.html

(int)(value * 255.999999)

Is it correct to use such technique at all? Why dont' use something straight like round(blabla * 255)? Is it features of C/C++? As I see strictly speaking is will return not always correct results, in 27 cases of 100. See spreadsheet at https://docs.google.com/spreadsheets/d/1AbGnRgSp_5FCKAeNrELPJ5j9zON9HLiHoHC870PwdMc/edit?usp=sharing

Somebody pls explain — I think it should be something basic.

Answer 1

Normally we want to map a real value x in the (closed) interval [0,1] to an integer value j in the range [0 ...255].

And we want to do it in a "fair" way, so that, if the reals are uniformly distributed in the range, the discrete values will be approximately equiprobable: each of the 256 discrete values should get "the same share" (1/256) from the [0,1] interval. That is, we want a mapping like this:

[0    , 1/256) -> 0
[1/256, 2/256) -> 1 
...
[254/256, 255/256) -> 254
[255/256, 1]       -> 255

We are not much concerned about the transition points [*], but we do want to cover the full the range [0,1]. How to accomplish that?

If we simply do j = (int)(x *255): the value 255 would almost never appear (only when x=1); and the rest of the values 0...254 would each get a share of 1/255 of the interval. This would be unfair, regardless of the rounding behaviour at the limit points.

If we instead do j = (int)(x * 256): this partition would be fair, except for a sngle problem: we would get the value 256 (out of range!) when x=1 [**]

That's why j = (int)(x * 255.9999...) (where 255.9999... is actually the largest double less than 256) will do.

An alternative implementation (also reasonable, almost equivalent) would be

j = (int)(x * 256); 
if(j == 256)  j = 255;  
// j = x == 1.0 ? 255 : (int)(x * 256); // alternative

but this would be more clumsy and probably less efficient.

round() does not help here. For example, j = (int)round(x * 255) would give a 1/255 share to the integers j=1...254 and half that value to the extreme points j=0, j=255.

[*] I mean: we are not extremely interested in what happens in the 'small' neighbourhood of, say, 3/256: rounding might give 2 or 3, it doesn't matter. But we are interested in the extrema: we want to get 0 and 255, for x=0 and x=1respectively.

[**] The IEEE floating point standard guarantees that there's no rounding ambiguity here: integers admit an exact floating point representation, the product will be exact, and the casting will give always 256. Further, we are guaranteed that 1.0 * z = z.

Answer 2

In general, I'd say (int)(blabla * 255.99999999999997) is more correct than using round().

Why?

Because with round(), 0 and 255 only have "half" the range that 1-254 do. If you round(), then 0-0.00196078431 get mapped to 0, while 0.00196078431-0.00588235293 get mapped to 1. This means that 1 has 200% more probability of occurring than 0, which is, strictly speaking, an unfair bias.

If, isntead, one multiplies by 255.99999999999997 and then floors (which is what casting to an integer does, since it truncates), then each integer from 0 to 255 are equally likely.

Your spreadsheet might show this better if it counted in fractional percentages (i.e. if it counted by 0.01% instead of 1% each time). I've made a simple spreadsheet to show this. If you look at that spreadsheet, you'll see that 0 is unfairly biased against when round()ing, but with the other method things are fair and equal.

Answer 3

Casting to int has the same effect as the floor function (i.e. it truncates). When you call round it, well, rounds to the nearest integer.

They do different things, so choose the one you need.