Numerical Disasters in C

Motivation

Well, the IOCCC shows people how to write high quality C code by using original interpretations of the syntax and grammar rules. Without wanting to insult the entrants, it doesn't give good instruction about writing bad algorithms, since the meaning is often too obscured for people to see what's going on. This, on the other hand is a guide to the world of perverse algorithms. I want people to be able to easily appreciate the beauty and elegance of some of the fastest algorithms out there¹.

All programs will be put in an on line reference that is browsable. I'll also include a tarball of the lot for ease of downloading.

What I want to see in a program

• All the programs must be clear: the clearer the better since I want people to understand them.
• The algorithms can be as perverse as possible, but they mustn't waste time, for instance the following code:

          for(i=0; i < N; i++)
            for(j=0; j < N; j++)
              for(k=0; k < N; k++)
                some_time_consuming_but_useless_function();
          

  would not be allowed. Although it rather effectively makes the algorithm O(N³), the step contributes nothing to the algorithm and does not advance its calculation in any way. In other words, every step has to be useful--although not too useful.

  Another possibility is writing an algorithm that is mathematically correct and even very efficient, but uses a method which has very poor numerical accuracy. The result being that the algorithm may produce a good result in a trivial case, but in an non-trivial case, on a real computer, the results are woeful. Of course, it can't simply introduce errors by artificially truncating the result every step. It has to make more imaginative use of the deficiencies of the FPU.

  These are guidelines, not hard-and-fast rules. If you can think of another kind of Numerical Disaster in C, I will welcome submissions.

• The code doesn't need to be engineered. People aren't going to be using these and engineering it often subtracts from the clarity. Besides if someone decides to use it, execution time will be far more of a problem than the occasional bad input.

  Also, code doesn't need to be generic. These programs are here to illustrate the principle of bad programming, not be a library for people to use. A sorting algorithm that works on integers only is fine since it illustrates the purpose.

• I want to see new and interesting algorithms. Ones that work in ways that haven't been seen before. They don't have to be worse performers than existing algorithms, however. For example, bogosort has pretty much set the upper limit for poor sorting algorithms, being O(n!), but there are some pretty interesting sorting algorithms go as high as O(N⁴lg₂(N)).
• All programs given must contain the code to run the algorithm and a driver program, so that people can compile and run the code just to see it work.

  The main() function can be arranged as follows:

  		 #ifndef LIBRARY
  		 int main()
  		 { 
  		 	...
  		 }
  		 #endif
  		 

  This allows other programs to use the available function as a library, simply by #include'ing the C source file. For instance, a program for computing determinants may wish to make itself available as a library for programs which which to compute matrix inversions.
• All programs must be completely standard ANSI C.
• All programs need a file describing what the algorithm is meant to do.
• All code must be put in to the public domain.

Enter Numerical Disasters In C

Currently, numerical disasters in C is in the form of a browsable directory listing.

1: by that, I mean that these algorithms can waste CPU time faster than any other algorithms available.

Updated July 14^th 2011, 10:52