brainwagon "There is much pleasure in useless knowledge." — Bertrand Russell


Drawing “circles” ala Marvin Minsky…

In my re-reading of Levy's book Hackers, I was reminded of an interesting bit of programming lore regarding an early display hack that Marvin Minsky did for circle drawing. It's an interesting hack because the lore was that it was originally coded by mistake, and yet the result proved to be both interesting and even useful. I first learned of this years ago when Blinn did an article on different ways to draw a circle, but also learned that it was part of the MIT AI memo called "HAKMEM". Here's the basic idea:

One way that you can draw a circle is to take some point x, y on the circle, and then generate new points by rotating them around the center (let's say that's the origin for ease) and connecting them with lines. If you have a basic understanding of matrix math, it looks like this:

/ x' \   /  cos theta  sin theta \ / x \
|    | = |                       | |   |
\ y' /   \ - sin theta cos theta / \ y /

(I should learn how to use MathML, but you hopefully get the idea). The matrix with the cosine and sine terms in it is a rotation matrix which rotates a point around by the angle theta. Apparently Minsky tried to simplify this by noting that cos(theta) is very nearly one for small theta, and that sin(theta) can be approximated by theta (we can get this by truncating the Taylor series for both). Therefore, he thought that (I'm guessing here, but it seems logical) that we could simplify this as:

/ x' \   /   1  eps \ / x \
|    | = |          | |   |
\ y' /   \ -eps  1  / \ y /

Okay, it's pretty obvious that this seems like a bad idea. For one thing, the "rotation" matrix isn't a pure rotation. It's determinant is 1 - eps^2 1 + eps^2, which means that points which are mapped move slowly toward away from the origin. Nevertheless, Minsky apparently thought that it might be interesting, so he went ahead an implemented the program. I'll express it here is pseudo-code:

newx = oldx - eps * oldy
newy = oldy + eps * newx

Note: this program is "buggy". The second line should (for some definition of should) read "oldy + eps * oldx", but Minsky got it wrong. Interestingly though, this "bug" has an interesting side effect: it draws circles! If eps is a power of 2, you can even implement the entire thing in integer arithmetic, and you don't need square roots or floating point or anything. Here's an example of it drawing a circle of radius 1024:

Well, there is a catch: it doesn't really draw circles. It draws ellipses. But it's still a very interesting bit of code. The first thing to note is that if you actually write down the transformation matrix that the "wrong" equations implement, the determinant is one. That helps explain why the point doesn't spiral in. But there is another odd thing: if you implement this in integer based arithmetic, it's eventually periodic (it doesn't go out of control, all the round off errors eventually cancel out, and you return to the same point again and again and again). In HAKMEM, Schroeppel proclaims that the reason for the algorithm's stability was unclear. He notes that there are a finite number of distinct radii, which indicates that perhaps the iterative process will always eventually fill in the "band" of valid radii, but the details of that seem unclear to me as well. I'll have to ponder it some more.

Addendum: The real reason I was looking at this was because the chapter in Hackers which talks about Spacewar! also talks about the Minskytron whose official name was TRI-POS. It apparently uses some of this idea to draw curves in an interesting way. HAKMEM item #153 also suggests an interesting display hack:

ITEM 153 (Minsky):
To portray a 3-dimensional solid on a 2-dimensional display, we can use a single circle algorithm to compute orbits for the corners to follow. The (positive or negative) radius of each orbit is determined by the distance (forward or backward) from some origin to that corner. The solid will appear to wobble rigidly about the origin, instead of simply rotating.

Might be interesting to implement.

Addendum2: I goofed up the determinant above, it should be 1 + eps^2, not 1-eps^2. Corrected.


My Thoughts on The Acceleration of Addictiveness

Paul Graham has a interesting little missive over on his website on the increasing trend toward addictiveness in our society:

The Acceleration of Addictiveness.

I don't think it is bad as far as it goes, but I wonder why he didn't ask what I thought was the obvious question: "why are things becoming more addicting?"

Let's consider what we eat as an example. Hardly a day goes by when you can't find a story about the obesity epidemic that is going on here in the United States. We're getting fatter, and we are having fatter kids. And everyone is asking why this should be happening.

I think the answer is really quite simple: we are addicted to food. Well, not food precisely, but to things that we eat which sort of vaguely resemble food, but are engineered to be addicting.

No doubt some of you are tsk-tsking. You'll probably post a comment which says that what we eat is a personal choice, that we have control, and that we simply don't exercise enough and that we eat the wrong things. You probably will also look at the people you know who still smoke, and wonder why they simply don't quit.

I'm going to say that while you are right in a sense (nobody can get you to quit except you) but you are wrong in that it is simple or easy. Nobody really likes to be overweight, if it were easy to avoid being so, they would. If you examine the rate at which people successfully lose weight and keep the weight off, you'd find it was vanishingly small. In that respect, it seems very similar to drug and alcohol addiction. The actual effectiveness of even well accepted treatment options like AA is near zero, if not actually negative. But that's another posting...

If there is an acceleration in addictiveness, it seems to me that there is an increase in the number of suppliers of these addictive products. Let's call them what they really are: pushers. Pushers are willing to sell products to consumers which aren't really good for them. They are eager to reduce the cost of their product, to increase its availability, and to increase their potency. They may not start selling addictive products intentionally, but let's face it: it's much easier to sell products to addicts than to people who can take or leave your product.

Pushers will tell you that they are just filling a demand, and that their consumers are adults who are responsible for their own choices. At best this is denial. At worse, it's just a lie that attempts to shift responsibility to the addict.

It astonishes me that there are still people farming tobacco and making cigarrettes. Not because it should be illegal, but because it takes an inhuman lack of respect for others to profit from selling them products which are so dangerous. I've begun to feel the same way about many packaged food producers and fast food purveyors, who carefully market "food" which is sadly nutritionally deficient and which maximizes the use of things like HFCS and processed white flour to reduce costs and to unnaturally manipulate appetite. And perhaps we should begin to consider companies like Facebook to be in this realm as well: they are using games and social interaction as an enticement to reveal much of your private information, and this only works if they can entice you to return again and again.

If we are concerned about our increasingly addictive, impatient, immediate gratification based society, perhaps we should all be asking ourselves whether we are becoming pushers: purveyors of behaviours which are ultimately bad for us. If we are, perhaps we should consider forgoing the profits that dealing addiction can reap, and figure out how to apply our effort and ingenuity in more productive directions.

Filed under: Rants and Raves 1 Comment