Most of the software published on bearcave.com is either elegant, useful, interesting or, ideally, a combination of all three. But I don't find all software equally fun to write. Nor am I equally good at all types of algorithms. This Web page publishes those algorithms that I have written once and don't want to write again. Given the ubiquitous nature of the Web publishing this code here means that I will be able to access it when ever I need it. Its also possible that it will be useful to others (although some of these algorithms are a bit obscure).
It also occurs to me that another way to look at this Web page is as the bearcave.com garage or attic. Men, myself included, have a habbit of squirreling away all sorts of things because "they might be useful someday". The algorithms here are not exactly fundamental algorithms that come up all the time. But they are cached away here incase I ever need them again. And as I said, I don't really want to write this code twice.
This is a C++ class that converts an IEEE double (e.g., a 64 bit floating point value) to the equivalent ASCII representation, in scientific notation.
Unlike the Sierpinski code, which I think has a certain elegance, this code is simply useful, especially if you are implementing library code like printf or sprintf. It is one of those pieces of code that I wrote years ago and keep around so I don't have to write it again.
This function is passed an array of 32-bit words, a low bit and a high bit. Bits are numbered from zero. The function will set the bits from low bit to high bit to one. This is pretty obscure, I admit. But this little function took much longer to write than I thought it should. And who knows, I might need it some day.
A small C++ program that generates a Verilog design for a multiplier composed from cascaded full adders.
Using the C++ Standard Template Library (STL) vector::erase function
The STL vector is a template container that organizes elements in sequential order and allows reference via the index operator []. The erase() function allows an element to be removed from the vector container without leaving a "hole". The erase() function takes an iterator argument. This Doxygen generated documentation for erase_demo.cpp demonstrates who to create and use an iterator and the erase() function.
A tar file containing the source code and the Doxygen script to regenerate the documentation can be downloaded here.
Unbalanced binary tree search, insert and delete (Doxygen generated documentation)
Over the years I've written lots of tree search and insert code. An application that comes up a bit less is tree search, insert and delete. I wrote this code in 1996. The tree delete is kind of tricky. I used Introduction to Algorithms (first edition, 1990) by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest as a reference in developing this code (I've since purchased the second edition of this book).
Balanced trees, like red/black trees or AVL trees guarantee an optimal tree branch length at the cost of a more complex algorithm (although search is as fast). This code was written for a case where the keys were in an even pseudo-random distribution.
A UNIX tar file containing the source files for this algorithm can be downloaded here.
A Java version of this binary tree algorithm is also available here.
Calculating Permutations and Job Interview Questions
The permutation of a set is the number of ways that the items in the set can be uniquely ordered. For example, the permutations of the ste { 1, 2, 3} are { 1, 2, 3}, { 1, 3, 2}, { 2, 1, 3}, { 2, 3, 1}, { 3, 1, 2} and { 3, 2, 1}. For N objects, the number of permutations is N! (N factorial, or 1 * 2 * 3 * ... N).
Random programs that make use of UNIX/POSIX/Linux system calls.