Phony Physics (a.k.a. Fun with Interpolation) April 3rd, 2009
Patrick Stein

In a previous post, I mentioned looking for a polynomial for an application. I am working on an application that involves clicking or dragging tiles around. Once you release the tile, I want it to snap to where it’s supposed to be.

The easiest way to do this is to just warp it to where it’s supposed to go. This isn’t very visually pleasing. The next best thing is to set up a time-interval on which it moves into place. Then, linearly interpolate from where it is to where it’s going (here with t normalized to range between zero and one):

(1-t)x_0 + tx_1

That’s much better than just warping, but it doesn’t have any sort of fade-in or fade-out. It instantaneously has its maximum velocity and then instantaneously stops at the end.

Typically, then one uses a cubic spline to scale the t value before interpolating to get a speed up in the beginning and then slow down in the end.
Read the rest of this entry ⇒

Find the Polynomial You’ve Been Looking For April 2nd, 2009
Patrick Stein

Often, I want to have a polynomial that meets certain criteria. For most applications in the past, I figured it all out by hand.

Today, I was having trouble getting the conditions specified enough to get the sort of polynomial that I was expecting. After finding the coefficients for several sixth degree polynomials in a row, I figured I should instead be able to do something like this with the proper lisp:

(calculate-polynomial-subject-to
    (value :at 0 :equals 0)
    (derivative :at 0 :equals 0)
    (nth-derivative 2 :at 0 :equals 0)
    (value :at 1 :equals 1)
    (derivative :at 1 :equals 0)
    (nth-derivative 2 :at 1 :equals 0)
    (value :at 1/2 :equals 3/4))

That’s all done now (polynomials.lisp). So, for the record, the above is: 26x^3 - 63x^4 + 54x^5 - 16x^6. That is still not quite the polynomial I want for this application, but it’s close. A few minutes of Lisp saved me hours of whiteboard work.

Sapir-Whorf with Programming Languages February 12th, 2009
Patrick Stein

I’ve been coding in Objective-C for a month or so now. It is interesting (in a Sapir-Whorf sort of way), how the language changes the way that I code. Switching from Objective-C to Lisp made me notice something that I hadn’t really noticed when moving from C++/Java/Perl to Lisp.

In Lisp, I will pull something out into a separate function if it makes the current function more self-contained, more one idea. In C++, I will only pull something out into a separate function if I need the same functionality in multiple places.

Actually, it’s even worse than that in C++. For stuff that is less than six or so lines, I might maintain it in several functions. Or, if I’m using some Literate Programming tool, I will just use the same chunk in multiple places. The notable exception in C++ is when I want to use something as a loop conditional, I may bother to break it out into its
own function:

while ( incrementCounter( cntr, min, max, dimensions ) ) {
    // body of loop here
}

In C++ or Objective-C, I might do something like this:

// some portion of my function

unsigned int choice = random() % length;
void* currentChoice = options[ choice ];
    // yes, I know I can memcpy(), but that's not as obvious
for ( unsigned int ii=choice+1; ii < length; ++ii ) {
    options[ ii-1 ] = options[ ii ];
}
--length;

// some code using currentChoice

In Lisp, I would never consider keeping that code inline. I would put it in another function right away.

This, this is one of the things I meant when I said Lisp is just plain fun. It’s easy to make a new function. I can just do it. I don’t have to fret too much over the name. I don’t have to fret too much over the argument
list. I don’t have to pre-declare it in this header file with the same signature as that implementation file. I
don’t have to pretend its a method when it’s really just a function. I can return multiple values if I need to do so. I don’t have to worry much about which compilation units will need to see this to compile.

Part of the maze generation code that I wrote in Objective-C needs to track walls. I don’t need the same structure during generation that I will use once it’s generated. So, I have a Wall class declared. It feels wrong to declare it right in the header file for the Maze. It feels silly to break it out into its own header file. What I should be doing is making a separate MazeFactory and have its implementation include the declaration of this Wall class. But, that is such overkill here. I just want the darn maze.

In Lisp, I would just be done with no feelings of guilt at all.

Multiple Bank Robberies Is Not Surreal January 6th, 2009
Patrick Stein

On December 29th, there were five bank robberies in New York City. The NPR bit on it contained this tidbit:

Anahad O’Connor, metro and breaking-news reporter for The New York Times, says the news was a little surreal because last year there was fewer than one bank robbery a day in the city.

So, how surreal is it, actually? According to O’Connor’s article, there were 280 bank robberies in the first 362 days of 2007. So, there is an average of 280/362 bank robberies per day in NYC (at least for most of 2007).

Now, it would be hard to believe that bank robbers don’t have preferred days of the week. For example, outside of Hollywood films, it is probably much more likely that a bank gets robbed while there are tellers on duty than on days when the bank is closed. It is technically easier to get a person to give you money than to get a 10 inch steel door to give you money.

So, there are probably some days where the raw likelihood is higher than other days. But, for the sake of argument, let’s say that all days are equiprobable since this makes five robberies in one day as improbable as it can be with still an overall average of 280/362 robberies a day.

Similarly, any conspiracy to rob multiple banks would probably tend to cluster them for the same time period so as to thin out the police response. So, let’s assume that each robbery is entirely independent of the others.

Under these minimizing assumptions, the number of NYC bank robberies on a given day is a Poisson distributed random variable with \lambda = \frac{280}{362}. Thus, the probability of five robberies in a given day is a bit over 1 in 1000. [ \frac{\lambda^5 e^{-\lambda}}{5!} \approx 0.0010645 ] That’s a bit more than once every three years. That’s just not surreal.

And, it’s way less surreal than all of that. The same New York Times article says that bank robberies were up 54% at that point in 2008. There were 431 bank robberies in the first 362 days of 2008. Using 431 in place of 280 in the above calculations brings the probability up to almost 6 in 1000 (0.0059982). That’s twice a year, on average.

The moral: probability and gut instinct are not close allies.

Maybe 2008 having 431 bank robberies in the same time that 2007 had 280 wasn’t as improbable as it sounds either. If we assume the real average is 280 bank robberies in the first 362 days of a year, what are the odds of finding a year with 431 bank robberies in the first 362 days?

It turns out, it’s less than 1.5 in 10^{17}. This is roughly once every 10 million age of the universe’s. That might qualify as surreal.

Lisp Package Dependencies October 21st, 2008
Patrick Stein

Some time back, xach posted information about all of the interdependcies amongst the Lisp packages available on Cliki. He had toyed with a few visualization techniques.

Me, I tweaked some old code visualization stuff I had written to output where everything was after it stabilized. Then, I tweaked my ray tracer to read that input and render the output.

Read the rest of this entry ⇒

Updates In Email

Email:

RSS Feeds

l