Dr. Dobb's Journal April, 2005
Binary Floating-Point Arithmetic
Dear DDJ,
In the past 20 years or so, the IEEE-754 Standard has brought about substantial improvements in the portability and reliability of programs that use binary floating-point arithmetic. But a lot has changed in 20 years, and we've realized that there are a few things in the Standard that could have been done better.
One of them is the Signaling NaN (sNaN). Signaling NaNs were intended to extend the Standard in ways we could not foresee at the time. The idea was that sNaNs, together with carefully implemented versions of the optional trapping feature, would allow a user to implement new features in an economical and portable way for debugging or arithmetic extensions. Unfortunately, since traps were optional and each manufacturer chose to implement them in a slightly different way, sNaNs were not provided with the support they needed to flourish. Making traps both mandatory and portable is not feasible.
The only remaining feature about sNaNs that could be counted on from one implementation to the next is that when an sNaN is encountered, it sets the Invalid flag and turns into a Quiet NaN (qNaN). Using this feature to extend the Standard turns out to be cumbersome and perhaps almost as easy to implement with qNaNs alone. For example, there have been attempts to fill uninitialized data with qNaNs containing identifying information sufficient to track down attempts to consume uninitialized variables.
Beyond that, we know of very little that has been done with sNaNs, and none of it is portable. Further, recent informal inquiries have turned up no current use of sNaNs. In an attempt to simplify the Standard, we are, therefore, considering making sNaNs no longer mandatory with a view to their ultimate elimination. But we are concerned that doing so would violate the precedent established in 1985. We suspect the constituency counting on this one portable feature of sNaNs just might be empty. If so, the precedent serves no one and the elimination of sNaNs would cause no harm and do much good.
Therefore, to perform due diligence, we are asking the software community if there is any portable software out there that requires this one feature of sNaNs in order to function. We would also like to learn about nonportable software that requires sNaNs.
If you are responsible for such software, please contact us at snans@nonabelian.com with a description of the purpose of the software and how it uses sNaNs to accomplish that purpose. Source code would help but is not necessary if the application is clear enough. We thank you for your help in settling this matter.
Dan Zuras
Chairman, IEEE-754R
GA in the Real World
Dear DDJ,
While reading "Genetic Algorithms & Optimal Solutions" by Michael Larson (DDJ, April 2004), I was surprised that Michael used a GA for this problem. That is because it seemed possible to directly test each combination of variables in less than the 20 seconds the author achieved; it also did not seem to be a good application of genetic algorithms.
Out of curiosity, I tested the direct computation approach. My first attempt minimized processing in the inner most loop through QP2; i.e., Q+2, where Q is one of Michael's control variables. My results were comparable to Michael's. Wishing to get faster results, I converted my (object Pascal) code to inline assembler and replaced floating-point instructions with 64-bit integer multiplication and division instructions using the EDX:EAX register pair. While doing that, I ran into an overflow error. While resolving that error, I realized that my inner loop variable needed to be constrained to prevent overflow. That led to the more significant realization that I could directly compute an upper and lower bound of QP2 for the desired tolerance level for any combination of P, PO, and Divider. This reduced the number of iterations needed to directly test each potentially feasible combination of variables by a factor sometimes larger than 100. The results of these changes is that for all examples I tried, the computation of all feasible combinations of variables were completed in around 1 second on my 150-MHz Thinkpad 380D running Windows 98SE. Had the program stopped after finding the first feasible solution, the times would have been a lot smaller.
Even had the problem not been amenable to solution by direct computation, my sense is that this problem is still not a good candidate for solution by a GA. That's because GAs should be used for problems where combining individual solutions, each containing good building blocks, is likely to result in better solutions. For example, in the travelling salesman problem, it is plausible that combining the best segments of individually good solutions might result in a better solution having those segments. In contrast, in this problem, the better the initial solution, the more likely it is that changing part of it will result in an output frequency that is worse.
Given the large number of acceptable solutions to the examples I tried, many of which had over a thousand solutions with a 0.01 percent tolerance level, it seems likely that just trying randomly generated 26-bit pseudorandom numbers would be better than using a GA. Several good pseudorandom number generators, such as those developed by Pierre L'Ecuyer, can be found on the Internet.
Phil Troy
philtroy@mail.com
Quincy 2005
Dear DDJ,
I am an Australian lecturer in IT. I am currently "doing up" Al Stevens' Quincy 2002 into a Quincy 2005 version with minor enhancements and fixes useful for my teaching. As the "spruced-up" version may be of use to other C/C++ teachers and learners around the world, I intend to make Quincy 2005 available on the Internet to anyone. A prototype web page is [available] at http://codecutter.net/tools/quincy/.
The main changes are to the project page and the build options page. The binary release also contains MingW and all the required libraries for development of simple graphics programs. This ensures that all students have the same compiler version at the start of semester, which simplifies the teacher's task a lot.
I still have a lot to do to fix and polish up Quincy for the start of semester, but the current version on that page can give a fair idea of the "visible" changes. The current source (built with Visual Studio .NET 2003) is also available there. Thanks for Quincy.
Jean-Loup Komarower
Swinburne University
jkomarower@venus.it.swin.edu.au
Al responds: Jean-Loup, thanks for telling me about how you are using Quincy. That's exactly how I hoped programmers and educators would use it. Let me know if you have any problems that I can help with, but realize that it has been two or three years since I looked at the code. I suggest returning the Windows version to the About dialog. It helped me isolate platform-dependent issues when users reported problems.
DDJ