Various projects that I’ve worked on rely on building efficient hash tables for looking up, well, all sorts of stuff (wow, that was vague). Say, storing transposition table entries in my checkers program. Cuckoo hashing is a way of resolving hash table collisions.
Here are some references:
My Biased Coin: Cuckoo Hashing, Theory and Practice : Part 1
Wikipedia entry on Cuckoo Hashing
I’ve bitched before about CSI and their use of “video enhancement” to read displays and the like using low resolution security cameras reflecting off objects. It’s interesting to see what is actually possible using this basic idea though. Link courtesy of Bruce Schneier’s security blog:
Schneier on Security: Spying on Computer Monitors Off Reflective Objects
While trying to find out if Python included some built-in capabilities for dealing with BCD numbers (it appears not) I encountered this rather interesting page about decimal arithmetic.
I do like programming “for fun”, and this includes writing programs that, well, have been written hundreds of times before, but which I never have bothered doing. Often, this is just an exercise: freely available libraries often exist for many tasks which are considerably better than anything that I write. Nevertheless, I don’t consider it pointless. There are situations where having simple, self-contained code that is free from any particular licensing issues.
For instance, I’ve never really bothered coding up an FFT implementation. (Actually, this isn’t entirely true: I helped work on an i860 based assembly language version twenty years ago when I was at Princeton, but I must admit that I didn’t do much of the heavy lifting.) When forced to use one, I typically just fire up FFTW and use it. It’s a fast, relatively simple and flexible FFT library, and well worth using. But there are some circumstances where it seems like overkill. So, I sat down and implemented a basic radix-2 in-place FFT in C using the algorithm from Crandall and Pomerance’s Prime Numbers. Running it on my MacBook, for an 8192 length complex forward transform, I get a time of about 3.95 ms per transform. The same size transform running with FFTW is almost a factor of ten faster: about .413ms per transform. Of course, my code is a big stomping 43 comfortable, loafing lines long.
But this got me thinking about how it might be possible to speed it up. I have a couple of books on my shelf at work that will probably useful (I looted them from people who were more knowledgeable than me at DSP who, for some reason, decided to give them away, but I haven’t read them). Even doubling the speed of this “naive” implementation would make it significantly more useful. And, it seems like it could be a reasonably fun thing to tinker with.
It’s too late today to make any significant progress, but I did dig up a useful link.
Efficient FFT Algorithm and Programming Tricks
Addendum: Updating the so-called “twiddle factors” in the inner loop was being done in a stupid way in my code before. It really only requires a complex multiply in the inner loop, which speeds it up considerably. Now, my 8192 element FFT takes a mere 1.16ms on my MacBook, a speedup of nearly 4x, and now it’s within a factor of 3 of the speed of FFTW. I don’t like the way it really looks yet, but it’s better than most. I’ll tidy it up soon and archive it here for future consumption.
Addendum: Now that it’s basically working, I’m left wondering about numerical accuracy. Accuracy of the discrete Fourier transform and the fast Fourier transform would appear to be relevent. It appears that my choice of recurrence relationship for the twiddle factors probably results in rather significant errors (although I also suspect that it’s more than entirely adequate for the normal audio tasks which I use these things for typically).
Well, my excursion into FFT multiplication the other day left me with some more interesting questions, including trying to find out more information about the integer version of the FFT called the NTT (number theoretic transform). Instead of computing the transform to an orthogonal basis consisting of the complex roots of unity, the NTT transforms to a basic formed by discrete vectors over an orthogonal basis consisting of the primitive roots of some prime power. Any of that make any sense to you? Yeah, it’s pretty hard going for me too, requiring me to dust off some of my number theory knowledge that has been dormant for quite some time. But while digging, I found this link:
Jörg’s useful and ugly FXT page
Jörg Arndt is working on a textbook which appears chocked full of good stuff that actually has to do with computing things (as opposed to the stylish modern trend of merely using gigaflops of compute power to wait for mouse clicks). Very neat stuff: I suspect that if I read the chapter on the NTT a few more times, I’ll have it figured out.
Tom Duff recommended this blog for my perusal, and I filed it away. Today I discovered that it was linking back to one of my more popular posts: the one in which Tom Duff talks a little bit about Duff’s device. But there’s a lot of good reasons to check it out. I found this post about Unix viruses, which contained a link to one of Tom’s papers that I never read, although Tom and I have discussed at various times. Very neat. Lots of other good things in there too! Worth reading.
It’s 8:22AM, and I’m just waking up, checking my email and surveying my usual blogs with Google Reader. I don’t have time to explain why this link seems interesting, but if you are interested in random walks, computability or cellular automata, check out the following link. I haven’t had time to absorb it yet (and probably won’t until tonight, given that I should be on the road shortly) but it seems very interesting.
To me, anyway.
This week I’m busy at work trying to complete dozens of SIGGRAPH sketch reviews, so it seems like an opportune time to present the usual link to online copies of the SIGGRAPH 2006 Papers that have been accepted. I haven’t had a chance to review these yet, but there is usually something good in this pile.
[tags]SIGGRAPH,Computer Graphics[/tags]
There is a new security update for WordPress, which I’ve already installed without any serious mishap/problems. If you run WordPress, you might think about giving it an upgrade.
[tags]Wordpress,Blogging,Security[/tags]
Addendum: I’ve been having minor problems with the Dashboard in this release not displaying correctly. I’m still trying to figure it out.
You might have noticed if you are a long time reader of this blog that I’m fascinated by codes and ciphers, particularly the kind that were developed before computers really came on the scene.  That’s why I’m finding the M4 Message Breaking Project interesting: they are attempting to break three two as yet unbroken code intercepts that presumably use the Nazi 4-Rotor Naval Enigma machine.
Years ago when Simon Singh’s The Code Book came out, he ran a cipher challenge that invited readers to compete for a $10,000 prize by being the first to break 10 codes. Â I broke 7 out of the 10 (all the ones I thought I had a shot) including a 3 rotor Enigma encrypt. Â Breaking the 4 rotor variant with a much shorter message is a significant challenge, and they’ve managed to break one of the three already.
I’ve got their distributed client running on my machine. Â We shall see how it goes. 🙂
[tags]Enigma Machine,Cryptanalysis,Codes,Ciphers,Distributed Computing[/tags]
Josh over at tinyscreenfuls is digging some of the fancy “pencil sketch” effects that the Mac can do with its internal camera. Back in 1998, I experimented with writing some filters that did much the same, with some examples that I generated shown on the right.  Macintosh? I don’t need no steekin’ Macintosh. 🙂
And now, for your next project, render an entire feature length film. Â Beneath your desk, you’ll find a pencil, a yellow pad, and a C compiler…
This is just completely nuts, an 8 bit computer constructed entirely from 12 volt relays. It consumes 12 amps at 13.5 volts (160 watts). Hilarious.
[tags]Retrocomputing,Hacks[/tags]
Last night we had a screening of Hoodwinked, the new animated feature by director Cory Edwards and co-directed by Todd Edwards. It’s a retelling of the classic story of Little Red Riding Hood, and features the vocal talents of Glenn Close as Granny, Ann Hathaway as Red, James Belushi as the Woodsman, veteran voice over master Patrick Warburton as the Wolf, David Ogden Stiers as Flippers, a suave investigating frog, and Andy Dick as Boingo the rabbit. The plotline is a fractured fairly tale: the story you know isn’t the real story…
I’ll get the negatives out of the way right off the bat, because I’m not really sure how to be nice about this. In terms of visual effects and art design, this movie is not exactly going to knock your socks off. The characters have a very wooden look to them: the characters have an extremely limited range of facial motion and the animation on the whole appears rather stiff. The net result of this is that the entire movie reminds you of some of the old stop-motion Rankin-Bass features you’d see around christmas. The lighting overall is, well, as near as I can tell, there was no lighting. It really bothered me for the first ten or fifteen minutes, especially when I realized that the highlight in Red’s eyes was actually painted on, and stuck to her eye as she looked around. Bleh. There was a couple of times when Granny was center stage and you could literally see some strange polygonal effects around her mouth. Double bleh. And you should never have a roller coaster like scene without motion blur. Yuck.
Oh, and the music? Mostly terrible, although the villain’s song (mercifully, the last in the movie) was somewhat better, and didn’t seem contrived.
Okay, it’s not the prettiest movie, what’s to like?
The vocal performances were on the whole quite good, although I couldn’t really understand what accent Jim Belushi was trying for. Stiers does an amazing job as Flippers, I never would have recognized him as the urbane frog if he hadn’t been listed in the credits. Andy Dick and Glenn close also do well, as does rapper Xzibit as Chief Grizzly.
The story is actually pretty good. Early in the movie I thought it was going to be dreadful, but I think that may have been more of a reaction to the problems I had with the visual look of the film, and that’s probably something that’s fairly unique to people like me who work in the industry. Once I sort of got around that, I began to find quite a bit to like about the story, and by the end, I thought it was actually pretty fun. If you spent $10 to see it, you might feel a bit cheated, but if you got in on a cheap matinee, I would think you might be pretty allright with that.
I stuck around at the end to watch the credits, and it’s pretty clear that they didn’t spend the kind of money that studios like Pixar and PDI spend: their credits are remarkably short. For them to release a movie like this at all and get a national distribution deal is a credit to them.
Overall, I’m going to give the movie a B-, but I’m probably being mean because I stare at computer generated images all day long. Read some user reviews on Yahoo! or whatever if you’d like to get a glimpse at a more well-rounded view. It’s rated PG: some very young children at our screening found the growling wolf pretty intense, they did not like him at all but I suspect most kids over the age of eight will be fine.
[tags]Movies,Movie Review,Hoodwinked[/tags]
Well, Steve is still up there, but the big news (as yet unreflected on the Apple website) is the announcement of a new Intel based iMac. It will apparently come in the same sizes and prices as previous G5 iMacs, but will use Intel’s new CoreDuo processor that was plugged by Intel so heavily at CES last week.
There is also some nice improvements to their existing iLife suite, including the addition of the (somewhat predictably name) iWeb: a web authoring suite that includes the ability to create and publish rich media websites using premade Apple templates. Notable for podcasters, GarageBand will also include a Podcast Suite: a set of features designed to make the creation of podcasts simple and easy.
Addendum: Two new laptop models will be available in February: the MacBook Pro, also with the Core Duo Processor, $1999 and $2499. It will include the iSight camera, Front Row, all that kind of stuff. Neat!
[tags]Apple,Podcasting,MacWorld,iMac,Intel[/tags]
Okay, I know this is an atrocity, but you might still find Recolored to be an interesting program for adding color to black and white images. You basically scribble hints into the image, and it propagates the color to nearby pixels that it determines should be the same color. At right, you can click and get my version of It’s a Wonderful Life, appropriate for the holiday season, if somewhat garish overall.
Okay, I’ve goofed around enough this morning. Off to Christmas shop.