Alas, Concepts, We Hardly Knew Ye

22 July 2009 @ 09:19
by Tyler McHenry in Programming

While catching up on recent postings to Lambda the Ultimate, I was rather surprised to discover that last week concepts were, by a vote of the committee members, completely removed from the C++0x draft specification.

On Monday, July 13th 2009 Concepts were dramatically voted out of C++0x during the C++ standards committee meeting in Frankfurt. [...] When I first heard the news, I couldn’t believe it. Concepts were supposed to be the most important addition to core C++ since 1998. Tremendous efforts and discussions were dedicated to Concepts in every committee meeting during the past five years. After dozens of official papers, tutorials and articles — all of which were dedicated to presenting and evangelizing Concepts — it seemed very unlikely that just before the finishing line, Concepts would be dropped in a dramatic voting.

C++0x is the next version of the C++ language standard. It should more properly be called C++1x, since the chances of it being released within the year are like the chances that Microsoft would contribute code to the Linux kernel — er, bad example. Anyway, the point is that it’s not going to be done this year.

While I’ve been following the development of C++0x with interest, I haven’t been immersing myself in the implementation details. In essence, I want to know what’s coming up, but I’m not too interested in committing to memory the nuts and bolts of a specification that is likely to be revised several more times before it is finalized. I’m not totally abstaining from C++0x until it’s done. I do use some features where they are useful and already implemented, for example I am using unordered_map, the standard library’s version of a hash table, in the latest iteration of my work on the lottery problem. However, my understanding of the majority of C++0x features has been relatively, for lack of a better word, “conceptual”.

The layman’s understanding that I had of the C++0x concepts feature led me to react with shock to learning of it’s removal. It sounded incredibly useful, and I didn’t see what could be such a big problem that it would have to be ripped out entirely. That changed when I read more about concepts as they (were going to) exist in C++0x.

(more…)

Wheel Generation Success and Failure

11 July 2009 @ 17:34
by Tyler McHenry in Article Announcements

In the final installment of the portion of The Lottery Problem article series that has to do with the simple greedy wheel generator, I give a brief complexity analysis of my generation algorithm, and I report on the successes and the failures of the implemented generator:

On a 2.66 GHz Intel Core 2 Duo (though only using a single core), the generator consumed a peak of 1.87 GB of RAM and ran for approximately 36 hours before returning its wheel for 3-matches in a 6-from-49 lottery. [...] The wheel that it generated for my target 6-from-49 3-match lottery was 325 tickets long. While this is in my opinion a pretty good wheel, it is not optimal.

You can read the whole article here. The long and the short of it is that the generator is indeed as efficient as I hoped it would be, but that it is not an optimal generator, as I suspected it would not be. The above-linked article includes a link to download the code for my implementation of this generator, if you wish to download it to play around with it or try to improve upon it.

My hunch is still that this problem is NP-Hard, and so I do not expect that any such simple generator will consistently produce optimal wheels. However, this is not the end of my series of articles on this problem. I do have hope that I can improve the generated wheels substantially by including a heuristic function that avoids the pitfalls of my current generator. Ultimately I would like to produce a generator that produces wheels that are guaranteed to be within a small approximation factor of optimal, or a randomized generator that is optimal with a reasonably high probability.

One small confession is that while I have posted the six articles in the current Lottery Problem series over the course of about six weeks, I had in fact written the entire greedy generator and knew its results before I even began writing the articles. For the heuristic and/or randomized generator that I am considering, I have so far done little more than pondering, so it may well be more than a week or two until the next article is posted.

Detecting C++ Libraries with Autotools

7 July 2009 @ 02:27
by Tyler McHenry in Programming

Autotools, more properly known as the GNU Build System is a set of shell script-based utilities that automate parts of the configuration and compilation process for software that is distributed as source. The autotools are, in my opinion, a bit over-complex and fragile, but they remain the most portable and standardized way of allowing software to be compiled on UNIX-like (and especially Linux) systems.

One of the parts of autotools, called autoconf, is responsible for creating the “configure script” for a source package. If you’ve ever built a piece of free software from source, you have almost certainly encountered the following venerable triumvirate of commands:

./configure make sudo make install

That first command runs the script that is the output of autoconf, and it is responsible for detecting the capabilities and details of the system that the software is being compiled on. It, for example, will check that a sufficiently-recent compiler is available, and what system headers are necessary for various semi-standardized functions that the program uses. One other major function of the configure script is to detect whether or not libraries that the software depends on are available on the system.

The library detection mechanism, however, is biased heavily towards libraries written in C. Since C is of course the lingua franca of the UNIX world, this is understandable. Without cajoling, it really won’t detect libraries written in anything else, unless they have C bindings, and that includes C++. What then do you do if you have a C++ library that you wish to detect using autoconf? If you’re interested in the answer to this question, you probably already know what the problem is, and here I will give two workable solutions.

(more…)

Monty Hall is Falling Down

22 June 2009 @ 15:16
by Tyler McHenry in Mathematics

Today’s entry on Jeff Atwood’s weblog, “Coding Horror” talks about the time-honored probability puzzler known as the Monty Hall problem. If you are unfamiliar with the problem, it deals with devising the optimal strategy for playing a game that was common on the game show “Let’s Make a Deal“, starring Monty Hall, and has a solution that is commonly perceived as unintuitive.

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice? (Whitaker 1990)

This, much like airplane on a treadmill, and 0.999… == 1 are common topics of long, drawn-out arguments on the Internet. But what I want to talk about is not the problem itself (which has been done to death), or Jeff’s post. Rather, I want to discuss a variant problem humorously called the “Monty Fall Problem” proposed by Professor Jeffrey S. Rosenthal of the University of Toronto, which is included in an article titled “Monty Hall, Monty Fall, Monty Crawl”, which was linked from the Coding Horror article.

(more…)

Mechanics of a Greedy Wheel Generator

17 June 2009 @ 19:36
by Tyler McHenry in Article Announcements

Today brings us, at long last, the latest installment in my article series on exploration of the Lottery Problem.

In the previous article, I discussed the design decisions that were made in the greedy lottery wheel generator in order to get around the computational problems inherent in even a simple greedy generator for realistically-sized lotteries. In this article, I will walk through the mechanics of generating all tickets and matches, selecting a ticket for the wheel, and updating ticket meta-data in order to allow the next selection.

You can read the whole article here. In essence, this is a walkthrough, using text, diagrams, and pseudocode, of how exactly I went about implementing a greedy algorithm based lottery wheel generator. This article addresses my solutions to problems of time complexity, much as the previous article largely addressed the solutions to problems of space complexity.

The actual generator was implemented in, of course, C++. However this article contains no actual code, only pseudocode, so as to put emphasis on the algorithms and not the details. Besides, full details of any program can only really be understood by reading code itself, not descriptions of it with snippets. I have still not yet made available the source code to this generator, although that will be forthcoming. Hopefully I will have it cleaned up enough to be suitable for public consumption before the next article in the series is posted.

« Newer Posts Older Posts »