A Blog by Richard Kiss

I’ve been working on editing video again lately. I’m struck by the same feelings I had last time I tried to do this way-too-complex and thankless task.

I appeared on the local cable access show “Paint with Lynn”, with my friend, comedian Lynn Ruth Miller. They gave me a copy of the shows on DVD. I want to edit each 30 minute episode down to something less than ten minutes so I could upload it to YouTube and so viewers wouldn’t have the urge to kill themselves out of boredom.

First, I thought I would use Final Cut Express. Of course, they don’t let you import the .VOB file format that DVDs use (which is just a renamed mpeg-2 file) unless you spend $20 for the Apple MPEG-2 Playback Component. Why Quicktime won’t play back one of the most important file formats out of the box is beyond me. Okay, it’s not really beyond me: it probably has to do with the cost of patents. It’s still frustrating though.

So I used Handbrake to convert to MPEG-4. This take an hour or so. Well, guess what… Final Cut Express would NOT import the MPEG-4 movies produced by Handbrake. Whaaat???

So after some tests, I used Handbrake to convert to AVI. Another hour. Why Apple’s Final Cut Express supports Microsoft’s container and not Apple’s is beyond the hell out of me.

After spending hours figuring out and getting used to Final Cut, I discovered that Handbrake transcoded the audio, and I suppose due to some weird bug, shifted the levels, causing a bunch of pops in the audio. I noticed this only AFTER I had spent hours assembling all the clips.

So I transcoded AGAIN, this time requesting Handbrake to not transcode the audio, but just it pass through. That’s generally better anyway: it takes less time, and it doesn’t involve conversion, which generally causes a loss in quality. Lesson #1: Avoid transcoding whenever possible.

Finally, I had something that Final Cut could read (an AVI file) and did not have audio popping. I had created the clips by settings marks on the large clip. Luckily, I was able to just switch the underlying AVI files, and since all the time offsets were the same in the new file, I didn’t have to recreate the clips. This is the rough equivalent of changing the tablecloth without unsetting and resetting the table. But it worked. Finally something was going right.

I decided that I hate Final Cut. It’s way overkill for someone who just wants to select sub-clips from a large clip. I thought I would try iMovie for the second episode to see if it was any better.

I was ecstatic to find that iMovie claims support of importing MPEG-2 without buying any additional Quicktime components. However, you can’t just import an MPEG-2 file off your disk: it will only import MPEG-2 from cameras. What?? So you have to trick it into thinking the MPEG-2 file is in a camera hierarchy. After poking around the internet a bit, I discovered an easy way is to image the DVD with Disk Utility, then when you mount the image, iMovie figures it’s a safe unprotected DVD created by a camera (never mind that the DVD I got was unprotected in the first place). It was a huge waste of time and temporary disk space, but the trick worked, and was faster and less lossy than transcoding.

But alas, there was still for one problem: there is something up with the first chapter of the episode I was trying to import, and iMovie would not import it. Of course, Apple’s DVD Player and my hardware-based DVD player both play it just fine, so it’s mostly correct. But iMovie is more picky than it needs to be, and it throws an error. Why doesn’t iMovie use the same MPEG-2 code as DVD Player.app? Who knows? I need some way to figure out what’s wrong with the MPEG-2 file and repair it. Offhand, I know of no such utility. Maybe VLC.app will do it. It does a fabulous job reading otherwise sketchy media files. But that will take at least 15 minutes, so I’ll skip that for now.

Then there is the little matter of rendering. Final Cut Express works very slowly with clips in AVI format (using the H.264 video codec), and for some reason just will not play “unrendered” clips. I believe that “rendering” the clips converts them into an internal DV format which, although incredibly huge, is very quick to decompress so it can scroll around in them. This rendering process takes unbelievably long: it seems to be 8x real time (so one minute of video takes eight minutes to render). And this is on a machine that has absolutely no trouble playing real-time. Why would it take so much longer to render than to play live?! And why does it have to be rendered at all?

I believe the most direct process would be to convert from MPEG-2 to DV format, which I assume would not have to be rendered except during transitions. I haven’t been able to find software that will do this though besides MPEG Streamclip, which requires the $20 MPEG-2 component.

Why doesn’t Apple do more code sharing between their various video codec projects (Final Cut, which won’t read MPEG-2 or .mov files; Quicktime, which requires an upgrade to read MPEG-2 files; iMovie, which can’t read some MPEG-2 files that DVD Player has no trouble with). I suspect that legal concerns with the DMCA enter into at least one of these redundant code disasters.

Video is a living hell. Yes, even on the Mac.

I went to the San Francisco Django Meetup last week and met some smart, nice people.

There was some talk about host to deploying Django. There were many good things said about Slicehost. Of course, to my mind, the cheapest and easiest way to deploy is Google App Engine. I say let the good employees at Google deal with the hard work of keeping these thousands of machine online and responsive. If your GAE site goes down at 4 AM, there’s no point in waking up to take a look at what’s going on, because you can’t even log in to those Google machines, much less have root access, so you may as well… keep sleeping. Which is what I prefer to do at 4 AM.

Anyway, I’ve used Dreamhost for years to host both my blog and my personal web site, which is actually a very simple Django app. It’s met my needs perfectly; it’s a very low traffic web site, and at less than $10 a month (including ssh access!) incredibly cheap.

You don’t get root like you do on slicehost.com or other VPS, but I consider that a feature, not a bug. Do I really want to be the one responsible for keeping system software safe from the hacker attack du jour?

If you feel like sending some kickbacks my way, enter my email address as your referrer (him at richardkiss.com) or sign up here.

I expect to release my Django Dreamhost configuration as a github project Real Soon Now™.

Here’s the radio show I did on Sunday. It’s an hour long.

It starts with a three minute audio clip of a funny guy who isn’t me, so don’t be confused by that part.

"What's So Funny" radio show, Dec. 14, 2008

I’ve created a couple more git depots with some rather old code that has been written and open sourced for quite some time… but just never shared.

One is a simple C-based command-line utility to quickly fix line endings for text files. It can read and write text files that have DOS, UNIX or Mac line endings. It’s very simple and quite peppy, and does a simple check for binary files before proceeding, so you can use it with confidence. It’s called “fixle”… very quick to type, fast to use. It replaces files in place. Developed on Mac OS X, it should work on any UNIX.

http://github.com/richardkiss/fixle/tree/

Another is a pair of Core Audio utilities for Mac OS X that provide a sort of “device” for audio: speakerpipe (which lets you dump data to the speaker) and mikepipe (which dumps data from the mike).

http://github.com/richardkiss/speakerpipe-osx/tree

Ideally, the functionality in speakerpipe should be integrated into the Mac OS X build of the very useful command-line utility sox so it can play sounds on the Mac. (Hmm, some browsing of the project seems to indicate that this functionality is coming.)

Both of these were written years ago and just never released into the wild. I release them, with BSD-style licenses, with the hope that they will be useful. No warranties though suckah!

Last Friday, I participated in the Google Code Jam, a programming puzzle contest sponsored by Google. It was the first qualification round, and I was very happy with how I did, coming in 74th in my heat (there were three heats, and mine had almost 3000 participants).

There were three problems, each with two data sets. The last problem was really more of a math problem, which I figured would have given me more of an edge because most of the time when I cheat on my second love, computers, it’s with my first love, math. However, I couldn’t complete it in the time allotted. But I also couldn’t stop thinking about it. I eventually came up with a solution which I’ll share here.

It’s problem C in round 1A (start here), but essentially, you have to find the last three digits before the decimal point for the number (3 + √5)ⁿ where n is a whole number that can be very large (up to two billion).

This means you cannot calculate the whole thing; it would contain several hundred million digits, which would use most of RAM just to hold the representation. So you have to figure out a trick.

Here’s what I came up with (too late to submit). Let A_n = (3 + √5)ⁿ and B_n = (3 – √5)ⁿ. Observe that A_n = X_n + Y_n√5 for some series X₀, X₁, … and Y₀, Y₁, … where each of X_n and Y_n are whole numbers. You can show this easily by induction. You can show a similar thing for B_n; in fact, B_n = X_n – Y_n√5.

This means that A_n+B_n = 2X_n.

Notice that (3 – √5) < 1, so B_n < 1 for n>1, and goes towards 0 very quickly. Since A_n = 2X_n – B_n, we can calculate A_n by calculating 2X_n and subtracting a “small” number… that is, the last three digits of A_n are the same as the last three digits of 2X_n-1.

So all we need to do is figure out X_n!

We know that X₀ = 1, Y₀ = 0. A_n+1 = A_n(3 + √5), so

X_n+1 + Y_n+1√5 = A_n+1 = A_n(3 + √5) = (X_n + Y_n√5)(3 + √5) = (3X_n+5Y_n)+√5(X_n+3Y_n)

so separating rational and irrational parts yields the pretty recurrence relation X_n+1 = 3X_n + 5Y_n and Y_n+1 = X_n+3Y_n.

That means X_n+1 and Y_n+1 depend only upon X_n and Y_n. Since we only care about the last three digits, that means that there are only 1000*1000=a million different combinations of X_n, Y_n, and thus, the series must repeat in fewer than a million iterations. It shouldn’t be too hard to find a repeat.

Here’s the Python code to find the cycle length:

def _a_b_n(n):
    if n == 0:
        return 3,1
    a,b = a_b_n(n-1)
    return ((3*a+5*b) % 1000, (a+3*b) % 1000)

CACHE={}
def a_b_n(n):
    if not CACHE.has_key(n):
    CACHE[n] = _a_b_n(n)
    return CACHE[n]

F={}
for i in xrange(int(1e6)):
    k = (Xn, Yn) = a_b_n(i)
    #print i, a, b, (2*a-1)%1000
    if F.has_key(k):
    #print "repeat: %d, %d" % (i,F[k])
    break
    F[k] = i

cycle_length = i-F[k]
print "cycle length is", cycle_length

When you run this, it takes less than a tenth of a second to figure out that the cycle length is 500, and A₅₀₃, B₅₀₃ = A₃, B₃. So now it’s easy! Calculating the first 503 terms is enough.

Here is the rest of the code:

def do_trial(f):
    n = int(f.readline())
    if n>cycle_length:
        n %= cycle_length
        n += cycle_length
    t = a_b_n(n-1)
    return (2*t[0]-1) % 1000

f = sys.stdin
count = int(f.readline())
for i in xrange(count):
v = do_trial(f)
print "Case #%d: %03d" % (i+1, v)

It runs in pretty much no time at all, thanks to the excessive caching.

Our corporate web finally went live this week. I have been at this company for over six months, joining shortly after its inception.

So what took so long? Well, for one thing, we didn’t have a name until very recently. We were going by the temporary name “Funny Fox Games”, but didn’t want to waste any time branding us by the temporary name. We struggled over a final name for quite a while, and just a few weeks ago settled on BigPark, Inc. I actually think the name is quite good (kind of a relief… I thought some of the ideas were not that great).

So check out our quite pretty (and vague) web site at http://bigpark.com/ and see what you think. We have a few jobs openings, so if you like computers and/or games, take a look!

With a little luck, we will release our first game Real Soon Now™.

An invariant in my personality is an obsession with precision, pedantry, and pedagogy. This perfect storm is responsible for my unusual interest and aptitude for math and computers. But this was not a conscious choice, and with the good fortune of being able to breeze through math course came the curse of nerd-dom ostricization. My tendencies in this direction are too strong to ever hope to not be a nerd. I’ve always refused to “celebrate” the nerd way. Some of it is overcompensation, some of it surprising. For example, I’ve never seen an episode of Star Trek. As I like to say, I don’t trust anyone too much into anything. I’m a nerd, but I’m not a geek. (OK, I have a blog. Sue me.)

This repudiation of the geek lifestyle has caused me to drift away from video games that interested me when I was younger. My current job has brought me back into that world though, because… well, it’s that industry. So the office has XBOX 360, Wii, a giant TV. We got the game “Rock Band” pretty much as soon as it was available.

“Rock Band” comes with a guitar controller (with buttons instead of frets), a microphone, and a drum kit. You play and sing along with real songs that you’ve probably heard on the radio, like Weezer’s “Say It Ain’t So”, and it scores you based on how accurately you follow along to the score that scrolls by. If a tone is assigned to you and you botch it, that note doesn’t play in the song, and the discordance socks a body blow to your musical memory (and makes the virtual crowd more likely to start booing).

It doesn’t take long before you actually start to get the hang of it, and surprisingly, feel like you are contributing to the songs. You really do learn certain musical skills, especially timing.

If the difficulty level is appropriate — not too easy that you get bored, but not too hard that you get frustrated (see also this Wikipedia article) — you really start to get into it, and become one with the music. You begin to understand what it might be like to be a real rock star. It’s a coolness simulator.

These effects are real. After I’ve played the game for a while, I really do feel more at ease. I feel more confident. I am more chatty with strangers.

Of course, the irony is that playing video games is kind of dorky. One might claim this it’s just a fantasy world, where people pretend to be something they’re not. But there’s no denying that it does have an immersive coolness effect on its participants’ mood. So how to reconcile this apparent contradiction?

Who cares? Cool people don’t care what other people think.

Today I got multiple copies of a “pump-and-dump” spam. You know, the kind where they tell you about a stock that is “going to go through the roof” which then does because enough people believe it, so it becomes a self-fullfilling prophecy. The best part is, no one even has to be convinced about the fundamentals of the stock — they just have to believe that enough other people are going to buy. Thus, the pump. Alas, the dump is a tough one. Good luck with the timing on that. But I digress.

Somehow, many copies of this spam made it through Gmail’s normally excellent spam filter. Each was from a different, made-up sender, with first and last names probably independently chosen from some list. What was cool was the name on one of the spams: “Math Jesus”.

How wonderful. I immediately claim ownership of this moniker, since the spammer is probably not aware that this pairing was made. And how fitting. I am very good at math — not the best mathematician the world has ever seen, but definitely way up there. Not a math god. But, yes, dare I say, a Math Jesus.

Thus my new screen name/nickname/band name. Math Jesus.

Gödel showed that we need an infinite number of axioms for a system that can embed the natural numbers to be complete (that is, for every statement to be provably true or false). Something along those lines.

So let me say right now: ten commandments ain’t gonna cut it. That’s just gonna be the tip of the infinite iceberg.

I’ve always been proud about how lazy I am. I often say that I will do an incredible amount of work just so I can be lazy. Something along those lines happened today, and I realize that what it is is that I hate is routine busywork; so much so that I would rather do a certain quantity of creative work to avoid an equal quantity of busywork.

At my company, we have used Apple’s deprecated WebObjects 4.5, which uses Objective-C and WebScript. Years ago, WO4.5 was the most fun web development environment, but since it turned 5.0 and substituted Java for Objective-C, it’s been much less fun and it’s not used very widely outside Apple, and it’s not really admired as much as it used to be. It’s gotten worse (Java over WebScript? Get real) and other environments have gotten better (I like Django a lot right now).

Anyway, we have a specific application that has been bothering us for a long time, and it’s time to port it.

I’ve been looking at “SQLAlchemy”, a Python-based object-relational modeling tool that works with Oracle (which I hate, but that’s a story for another time). It seems using this tool will make the port from WO4.5 to Python a fair bit easier.

The first step seemed to be to create new model files that describe the object-relational mapping. Of course, the syntax for these files (pure Python, it turns out) is quite different from the syntax used in WO’s EOF object-relational mapping layer. We have a lot of objects, so rather than do it by hand, I thought I would write a tool to do it.

EOF uses a plist file format. There are Objective-C routines to read these files, but I couldn’t find any libraries to do so in Python. So I installed pyobjc so I could use one particular Objective-C call from Python. This made parsing very easy, and creating the Python model file was a piece of cake.

It’s not 100% yet, but I was quite amazed not only how quickly I could produce the translation tool, but what great lengths I would go to to be lazy.

I just got back from “Yahoo! Hack Day”, an ultra-nerdy convention of sorts put on at Yahoo! in Sunnyvale. It was sort of reminiscent of the now-defunct MacHack conventions I went to in the early naughties (2000 and 2001 I think) except it was free, more conveniently located here in Silicon Valley instead of Detroit (?!?!? I know there is a perfectly logical story behind why MacHack was in Detroit that I would knowingly nod my head at while I was hearing, but I repeat: ?!?!?), and more focused on web technologies (Yahoo! APIs, specifically).

I went there right after work on Friday, checked in, and put my name on the “looking for teammates” whiteboard. There was free pizza, and then a concert outside by Beck. The concert was fine — there were a lot of hangers-on (hanger-ons?), folks who were there just for the concert — but I was distracted by brainstorming about what I would do for the veritable hack contest that was about to start. By the way, Beck seems to really be into marionettes. I do love a good puppet show.

I met up with a clever young whippersnapper by the name of Sandro who was also interested in using the web development tools that I have been using lately (“Django” — see http://djangoproject.com/) and we went through some ideas and finally settled on what he cleverly called Flick Rel8. It’s sort a license-platey name. It’s a game: we download pointers to a bunch of Flickr images that are labeled with popular tags. Then we show three images with tag A is a row, followed by a stack of four images with tags A, B, C, D in some random order. The user has to guess which of the four images has the same tag as the first three.

The tag is not displayed (although it is available as a hint). So you have to look at the images and figure out what they have in common… and then find a fourth image that has the same thing. It’s like the SAT, Flickr-style.

We spent a lot of time developing and not a lot trying it, so I still don’t know if it ends up being fun. I don’t think it was that fun with the data set we had, but I think you could make it fun, especially if you limited the tag list to a certain class of tags — maybe concrete nouns and adjectives. For example, “2006″ is a pretty lame tag for this purpose.

The conference staff showed us clips from that indicated that every local news channel had a story about the conference.. Yahoo! must have some killer publicists. One dorky reporter disclosed the difference between “hackers” who are talented computer folk who mean no harm and “crackers” who try to break into computers. The irony was that he was the biggest cracker of them all.

Then at 3 PM, our hours of manic work came to an end. The 55-some odd teams took turns displaying their hacks. We were number 32. I started off with a joke that I knew would work with that audience, and indeed, it got a big laugh. It’s interested being able to not appear nervous in front of a crowd and to be able to be confident about getting a laugh.

All the stories had this spin that seemed to try to make the conference seem elite, or cool, or possibly even hip. I think Beck being there added to that sheen. I dunno, I think nerds are by definition not very cool. See Paul Graham’s essay on this. But so what? Why can’t things just be what they are?

All in all, a good time. I am exhausted, and I did not even stay up all night, as some people did (many camped out on the lawn). I met some good people. And I got to hack on computers, a thing I’ve been enjoying a lot more of lately.