6000 years in the making

I’m sure all of you are disappointed about missing the grand opening of Ken Ham’s Creation Museum, which I’m sure is a scientific, well-researched, thoroughly-documented, evidence-packed look at why the Genesis creation account (both of them, presumably) is 100% literally true.

(Hopefully your sarcasm detector is still under warranty; that last sentence might’ve overloaded it.)

Anyway, the next best thing is watching the episode of Moral Orel wherein the Missing Link is discovered during a camping trip. (Yes, you have to sit through an ad first, but what do you expect for watching it for free?)

Comments Off

Crazy Subtraction Algorithm

For the curious, here’s a description of the unusual subtraction algorithm I used in Ecumenicalculator. This algorithm converts subtraction into something that looks like addition of two positive numbers, mostly. It has the advantage of guaranteeing that you’ll never try to borrow from a zero.

As a running example, let’s say we want to compute 937,105 – 172,910.

Step 0: Assure that both numbers are positive and that the second number is smaller than the first. If either of those conditions does not hold, either swap the numbers (and negate the result), or realize that you actually have an addition problem and not a subtraction problem.

Step 1: Line the two numbers up vertically, so that the decimal places line up. This step is the same as “normal” subtraction.

   9  3  7  1  0  5
-  1  7  2  9  1  0
===================

Step 2: Replace each digit in the second number with the value (10 – digit). Yes, this means that any 0 digits turn into a 10 “digit”. Deal with it.

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================

Step 3: Add each column, without propogating any carry digits.

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================
  18  6 15  2  9 15

Step 4: Starting with the rightmost column and working left: if the “digit” is greater than or eqal to 10, subtract 10 from it; otherwise, leave it alone and subtract 1 from the “digit” to the left.

This will be easier to illustrate one column at a time. The rightmost one is 15, so we simply subtract 10:

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================
  18  6 15  2  9  5

The second-to-last column is 9, so we leave it alone but subtract 1 from the column to the left of it:

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================
  18  6 15  1  9  5

The antepenultimate column is now 1, so we leave it alone but subtract 1 from the column to the left of it:

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================
  18  6 14  1  9  5

The fourth-from-the-right column is now 14, so we subtract 10 from it:

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================
  18  6  4  1  9  5

The fifth-from-the-right column is 6, so we subtract 1 from the column to the left:

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================
  17  6  4  1  9  5

Finally, the leftmost column is 17, so we subtract 10 from it:

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================
   7  6  4  1  9  5

And lo and behold, 937,105 – 172,910 = 764,195.

Do you see why it works?

OK, here’s why it works. It’s actually very similar to regular subtraction, just with optimistic borrows and doing the operations in a different order. Take an arbitrary column in the original problem, where we want to compute ab. If ab, we simply compute ab = c and are done with it. However, if a < b, we borrow: we compute (a + 10) – b = c and subtract 1 from the column to the left.

In the crazy algorithm, we instead start off by computing a + (10 – b) = d right off the bat. Note that a + (10 – b) = a + 10 – b, which is what we’d normally compute if a borrow were needed. And in fact, if d < 10, then a + 10 – b < 10 and so ab < 0 and a < b, exactly the condition we look for to decide to borrow. Thus, if d < 10, then c = d and we subtract 1 from the column to the left. Otherwise, we compute c = d – 10, which works because d – 10 = a + 10 – b = ab, which is the result for the column if a borrow isn’t needed. Q.E.D.

So there you have it, mathematical proof that this crazy-looking algorithm does in fact work. Also, each column’s intermediate result will always be greater than or equal to 1 (since the “digits” generated in Step 2 always range from 1 to 10 inclusive), so you never wind up trying to borrow from a 0.

And while I proved it for the base-10 case, it generalizes to any arbitrary base, as long as you replace any instances of 10 with your base of choice.

Ecumenicalculator

Behold, my entry to the OMGWTF competition: Ecumenicalculator!

Screenshot of Ecumenicalculator

What makes this apparently simple program WTF-worthy? Just this: it doesn’t use numbers.

Nowhere in the backend code will you see ints, shorts, longs, floats, doubles, or any other numerical types, or any operations on them, or invocations on any functions that accept or return them. (The GUI code does use some ints, but only to the extent that they’re needed to interface with GTK to actually do the drawing, and even then it doesn’t do any math on them.)

How is this possible? Well, the code does use bools, as well as the container classes provided by the STL. And, of course, plenty of my own classes, all of which adhere to the don’t-use-numbers constraint.

OK, but how is this possible? The code uses Church numerals to represent individual digits. So, naturally, I had to implement untyped Lambda calculus in C++.

But of course, Church numerals will only give you nonnegative integers. To represent arbitrary real numbers (OK, technically, only rational numbers), I do what most humans do when writing down numbers: I make a list of digits, with each position being “worth” a different amount. There’s a radix point after the ones digit, and optionally a negative sign in front. I accomplish this mainly by putting multiple Church numerals into an std::list, maintaining an iterator after the ones digit, and a bool to flag for negative numbers.

That’s why the program is called Ecumenicalculator: it does computations on a bunch of Churches working together!

*ducks*

Needless to say, writing something like this without ever explictly using numbers provided by the language can get pretty interesting, especially when you need to do something like reference counting objects (since copying them eats up all available memory). C++ is also most definitely not a language well-suited for implementing untyped Lambda calculus.

Here’s some representative excerpts from the source code to demonstrate some of the hijinks that are going on to pull this off:

static const MyDigit radix (MyDigit ().successor ().successor ().successor ().successor ().successor ().successor ().successor ().successor ().successor ().successor ());

[calculator.cpp:39]

Well, how else are you going to get 10 when you haven’t created any other numbers yet? Compute the number after the number after the number after the number after the number after the number after the number after the number after the number after the number after zero!

typedef Curry< Curry< Curry<AddImpl> > > Add;

[church.h:235]

How can you not like recursive class template instantiation? Each Lambda expression class’s operator() only takes one argument, so when you need four arguments, you need to do some Currying. Making currying a class template lets you write the currying code once and apply it wherever you want.

Lambda result = band (iszero (sub (_numeral) (rhs._numeral))) (bnot (iszero (sub (rhs._numeral) (_numeral)))) (t) (f);

[church.cpp:173-174]

Thanks to operator(), it’s possible to write code that looks downright functional. Can you tell what that line is computing? (Hint: the variables all have obvious names.) Also, I think if I can work in five more sets of parentheses somewhere in there, I become an honorary Lisp programmer.

delete this;

[lambda.cpp:71]

You probably never want to do that unless you know what you’re doing.

If you want to see more (including recursive Lambda calculus expressions and a subtraction algorithm that guarantees you’ll never try to borrow from a zero), now that the entry deadline has passed, you can download the source for Ecumenicalculator and try it out.

The Chains! No!

I had heard about how bad the third-party Zelda games for the CD-i were, but thanks (?) to YouTube, now anyone can experience the pain themselves.

Here’s the final battle and ending of The Wand of Gamelon. There’s just so much wrong with this, it’s hard to know where to start, and it’s just a two minute clip….

Entry #100204 Submitted

After much feverish work, my entry to the OMGWTF programming contest has been submitted.

It may not be the most evil code I’ve ever written, but it almost certainly is the most breathtakingly needlessly elaborate code I’ve ever produced.

Of course, you’ll get the details on just what makes this code so amazing once the submission deadline passes, even though I’m pretty sure no one else would be crazy enough to implement what I’ve implemented.

Mwa ha ha ha! Mine is an evil laugh!

OMGWTF++

There are two essential components to my forthcoming entry in the OMGWTF competition. To avoid giving away any details of what I’m up to just yet, we’ll call these two components “the asylum” and “the inmates”.

These code names are obviously meant to evoke the saying “the inmates are running the asylum”. In this case, however, the inmates have also designed the asylum.

As of a few minutes ago, the asylum has been essentially completed. It’s currently filled with licensed architects inspecting the structure to make sure it isn’t going to fall down anytime soon. They’re baffled by some aspects of the design, to be sure, but it seems to be working as planned.

Hopefully they’ll be able to escape before the inmates take over. Then things are going to get seriously crazy. It’s quite likely the end result will be unlike anything anyone has ever created. Probably for good reason.

I’m also finding that C++ is a surprisingly fitting language for this project, both because it has some fairly crazy features (hi, templates!) and because it’s utterly unsuited to the fundamental paradigm those inmates can’t stop talking about.

Comments Off

OMGWTF

I am sorely tempted to enter The Olympiad of Misguided Geeks at Worse Than Failure Programming Contest (a.k.a. OMGWTF). The challenge: to write the most “Clever” (and possibly “Buggy”) calculator possible without being “Ugly” or failing the test cases.

Given the skeleton code provided, all that has to be done is to implement four functions:

  • One that adds two floating point numbers.
  • One that subtracts them.
  • One that multiplies them.
  • One that divides them.

Of course, a “Correct” solution is downright trivial, obvious, and straightforward. “Correct” is also not a judging criterion.

I’ve got some ideas for ways to attack this, though (un)fortunately I don’t see a good way at the moment to use Church numerals with floating point. But that’s hardly my only idea.

Ultimately, the question is: can the Code Master General code like a Code Master Second Lieutenant?

[Editor’s note: This is also not the post I alluded to, um, two posts ago now.]

Tease

Fun fact: if you file your taxes thinking you owe $X to the state, and a couple weeks later you unexpectedly get a refund check in the mail from aforementioned state for exactly $X, and you contact said state’s tax office to confirm that you are in fact due a refund, there is a chance that the answer will be “no.”

(OK, so apparently I lied last time when I said what the next post’s topic would be.)

X versus Amidakuji

Doing some random browsing of Wikipedia recently, I came across the entry on amidakuji. Yeah, I had never heard of it either. It’s this Japanese way to graphically do a permutation on a set of objects.

But looking at the graphic on the page, I realized, hey, I’ve seen this before:

That giant robot spider you fight in Mega Man X? Its movements are completely determined by amidakuji. It’s obvious that the spider follows the tracks that appear on the wall, but I had never realized it always takes the horizontal paths it encounters as it goes down.

Maybe I was too hung up on killing the baby robot spiders it drops on you to notice.

(And for the record, I totally would’ve put together my own screen shot and/or video instead of grabbing something off of YouTube, if not for the fact that my SNES emulator has recently fallen victim to this bug.)

Next time: more stuff I found while randomly browsing Wikipedia!

Comments Off