When is a problem not a problem?

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.

Use Math.ceil.

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.

 

Oh well, maybe we can find a good use for this silly piece of code I wrote. If we change our “car” into a “carpet,” and switch over to JavaScript, let’s see what we can do. JavaScript function calls are known for being somewhat expensive, especially in older implementations where things like Math.abs could be replaced with the following for performance gains.

i = Math.abs(i);
//Accomplishes the same as.
i = i < 0 ? -i : i;

So could we achieve a similar result my ceiling implementation?

To jsPerf!

The results I got in my quick testing, which did not include IE/Edge, were rather surprising. I used 6 different test cases, Math.ceil and a variable aliasing it as a control (yes, I know it is technically incorrect to alias a method to a variable in JavaScript, but I wanted to test the speed of the native code without the property lookup overhead), and both of my custom implementations, each as a function and inline in the loop.

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.

The real wildcard here though was Safari 8. In this browser, both of my inline solutions beat out Chrome’s native functions at over 5 times faster. The function calls were much slower, with my non-branching solution being the slowest, but my branching function beating out the native function. What?!? Oh well, Safari isn’t known for using the most advanced JavaScript engine, and I expect future changes will reverse these results.

 

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!

 

Leave a Reply

Your email address will not be published. Required fields are marked *

Are you human? * Time limit is exhausted. Please reload the CAPTCHA.