Quick Shine

I've posted before that I like puzzles. I came across another challenge that recently appeared on the hacker news feed - here is the actual post.

The premise is that there is a slow floating point operation that is taking place that can be sped up by using integer-only operations without causing any change in the output of the equation. For reference, here is the function that is reported to be slow:

---

unsigned char SlowBrightness(unsigned char r,
                             unsigned char g,
                             unsigned char b)
{
  return 0.289f * r +
         0.587f * g +
         0.114f * b + 1e-5f;
}

---

My approach to this was to try and estimate the floating point values by composing large enough integer fractions. The goal here is to find a single denominator (optimally a power of 2) that is capable of hosting three numerators that will result in the values listed. The reason to aim for a power of two in the denominator is that a dividing by powers of two can be efficiently implemented as a right bit shift.

At 2¹⁹, the following values result as numerators: 151519, 307757 and 59769 representing 0.289, 0.587 and 0.114 respectively. To check what type of error was related to these values I also evaluated the division and compared to the original values.

---

0.28900000
0.28899955 (151519/524288)

0.58700001
0.58699989 (307757/524288)

0.11400000
0.11400032 (59769/524288)

---

There was error, but since there was conveniently a constant in the original equation I could mitigate by adjusting the constant if necessary.

Once I had the values, I wrote the following test harness:

---

#include <stdio.h>

#define R(r) (151519UL*(r))
#define G(g) (307757UL*(g))
#define B(b) (59769UL*(b))
#define C    (5)

typedef unsigned char uchar;

uchar SlowBrightness(uchar r, uchar g, uchar b) {
    return 0.289f * r + 0.587f * g + 0.114f * b + 1e-5f;
}

uchar FastBrightness(uchar r, uchar g, uchar b) {
    return (R(r) + G(g) + B(b) + C) >> 19;
}

int main () {
    uchar r = 0, g = 0, b = 0;
    for (; r < 255; ++r)
        for (g = 0; g < 255; ++g)
            for (b = 0; b < 255; ++b)
                if (SlowBrightness(r,g,b) != FastBrightness(r,g,b))
                    printf("FAIL: %d,%d,%d\n", r,g,b);
    return 0;
}

---

The constant value of C came from 1e-5f represented as 5 / 2¹⁹. As expected, I had to increase the value of C to compensate for the difference in my estimated numbers. After the adjustment (the minimum constant ended up being 72) I was able to run and match all values of the two calls. I also achieved the bonus for minimal constants and only using +, * and >> operations.