Yesterday my brother, who is taking an introductory class on Java, asked me a thought problem that was posed in his class that day, which on the surface seems rather silly, but never the less had some interesting solutions. The question boiled down to this:
How can you round a double up to the next highest integer?
Easy I thought.
But there was one other stipulation.
Can’t use new functions we haven’t learned yet.
This problem is starting to get silly, but never the less, the solution seems obvious (I knew he had the modulus operator at his disposal).
Oh, you could implement your own ceiling function. Just take modulus 1, and if it’s non-zero, subtract it from zero and add it to the double.
But to my surprise, this was not possible either.
We haven’t learned if/else yet.
This can as a bit off a surprise, but while I tried to get over this limitation and come up with a new ceiling implementation that did not require the modulus operator, my brother told me the solution someone in his class came up with.
Just add 0.99999999 to the number before casting it to an integer, and if it’s anything greater than .0, it will work.
While clever, and maybe alright if you have the exact number of decimal points as the data type supports, I wouldn’t call this a real solution. There must be a better solution, and after thinking about it some more, I realized you could implement my custom ceiling function without branching, just use mod 1 twice. For example, where f is the floating point number, or double in the case of Java.
f + ((1 - (f % 1)) % 1)
So where does this leave us? Certainly no one could blame the class of beginners for not coming up with this solution, but a problem created by an unwillingness to learn something new isn’t a real problem.
i = Math.abs(i); //Accomplishes the same as. i = i < 0 ? -i : i;
So could we achieve a similar result my ceiling implementation?
In Firefox 40, my branch-free ceiling implementation held it’s own with the native implementations, with both inline and custom function averaging about the same as their native counterpart. However, the version with branching via ternary statement, was significantly slower, by a factor of more than 15. It appears Firefox is able to optimize my non-branching code to hit near-native speeds.
In Chrome 45 and Opera 32 on the other hand, my branching solution actually performed slightly better than my non-branching solution. However, neither of my custom implementations came within half the native speed. It looks like Chrome couldn’t do the same optimizations, and even the native functions were over 7 times slower in my testing.
So what’s the moral of the story here? If there is a native function, you probably should be using it. Micro-optimizations like this sacrifice readability for questionable gains, especially when advances in the engines could turn the optimizations of today into the bottlenecks of tomorrow.
Oh, and if you want to do something that involves learning something new, just learn it!