Going Loopy with Loops
Reinventing the wheel can often give a deeper understanding of the problem and highlight some of the esoteric features of your chosen programming language — however, remember to go back to using the standard method and style in your production code!
I like loops, they are predictable, reliable and relatively easy to understand. For many common algorithms there are much more efficient ways of computing the solution, however loops often provide an easy to understand approach to getting to the right answer — eventually.
Recently, when demonstrating looping constructs to a beginner I provided the following three examples which spit out 1 to 10 on the terminal.
// Traditional
for(int i = 1; i <= 10; i++) {
System.out.println(i);
}
// Unorthodox
int i = 0;
while(i < 10) {
System.out.println(i+1);
i = i + 1;
}
// Too smart for own good
for(int i = 0; i < 10; System.out.println(++i));
Each sample was slightly more complex, conceptually, than the next. The final sample demonstrating how the for could be abused to show the desired output on only one correctly formatted line. In it we use my favourite pre-increment operator to push the the 0 up to 1 before we output the number to the display. Of course we could have used 1 and 11 as our bound with the post-increment operator, but any sane programmer would agree that numbering should start at zero.
Extending the code abuse further, while browsing over at Stack Overflow I discovered that while is largely redundant, if you are happy to abuse for some more. Turns out that for, as typically defined, assumes the test condition to be true when omitted and all three sections of the for statement are in fact optional. As one of the moderators put it:
This answer pretty much proves the awesomeness of the “No question is too simple” policy.
— Bill the Lizard
Likewise, while browsing an interesting article on The Daily WTF which highlights a simple method for square root calculation my muse overcame me. The article makes it quite clear that such iterative approximations are not highly regarded (unless you are John Carmack), however, it reminded me of a simple pi calculator that I wrote using JavaScript a number years ago when similarly inspired.
Armed with new knowledge about the abuse of for and an entirely redundant algorithm to code I set about developing a square root function.
double sqrt(double n) {
for(double r = 1; r != n; n = r == (r = 0.5 * (r + (n < 0 ? -n : n) / r)) ? r : n);
return n;
}
There are so many things wrong with this I’m not sure where to start. How about the blatant abuse of the parameter n as both the input and output, simply to avoid declaring another variable? This requires the break condition to determine whether the usually untouched n contains the currently calculated value of the result.
The final chunk of code actually does the calculation of the square root while deterministically assigning the value to n to terminate the loop and return the result. The calculation itself is relatively simple: is the average of our calculated root, r, and n / r equal to the previous value of r? If not, further refine r in the same way.
r == ( 0.5 * ( r + n / r ) )
The calculation, as implemented in my sqrt() function, is complicated somewhat by the embedded assignment of the new value to r, the poor-mans error handling of negative numbers (who wants to deal with imaginary numbers anyway?) and the inline if used to assign the final value to n.
Of course, we could always use the built in Java Math.sqrt() method which efficiently passes the calculation off to the hardware, but where’s the fun in that!?
Comments
Leave a Reply