[tgbrter]

You need only one table look-up, a couple quick operations and no conditionals or multiplying.

The table size required to beat the accuracy of fastlog2 is 512 elements.

edit: The speed ratio is actually about 0.6 in favor of look-up versus fastlog2. Enabling -O3 changes the ratio to 0,9. This is of course not measured in a real-world program where the cache is shared by other stuff.

edit2: I have removed the if statement from fastlog2 and compiled with -O3. The ratio was 1,2.

[dalke]

Indeed, you're right. I forgot about step-function solutions, and thought interpolation/corrections were needed.

512 elements for 7 bits of accuracy sounds reasonable. The article mentioned a 2x improvement for 11 bits, but didn't get to that point.