FORTH GO

Overheard from the table behind me at Brixx (great pizza, btw):

“Tomorrow I’ll take you to Raleigh, because that’s our biiiiig city. So what’s France like?”

Bonnie and I attended the North Carolina Science Blogging Conference last week-end, and this photo shows WillR and me at the pre-conference dinner. I was really impressed with the variety of attendees and the work everyone was doing. Many of the bloggers are sponsored at ScienceBlogs, which I’ve been perusing since the conference, but so far it’s been hard to separate the science from the commentary.

Nonetheless, there was a lot of great content at the conference. Each session had a good bit of audience participation, and I thought the following observation from a middle school teacher was enlightening: students work harder when they know their reports will be posted on a school website for others students to see. Apparently, they’re more interested in impressing other students than their teachers. Or at least, more embarrassed at the prospect of publishing shoddy work to classmates.

Shortly after Java 6 came out last year, there were a number of Java 7 wish lists floating around (example). Most wishes are for syntax improvements. I don’t use Java as much as I used to, and I only have one wish list item: static analysis optimizations. That is, optimizations made possible with the help of static (not run-time) optimizations.

I’ve written before on the promising range check elimination optimization which strives to eliminate array bounds checking when provably unnecessary. But that optimization doesn’t quite live up to its potential because any nontrivial array usage is beyond the scope of a run-time proof. So the idea of static analysis optimization is for a compile-time (or post-compile-time) process to do an in-depth analysis of array usage and other potential optimizations and insert the suggested optimization and finished proof into the byte-code. Then the JVM only needs to verify the proof at run-time rather that construct a proof from scratch. And for that matter, the JVM could never generate a proof, since it could assume that if there is no proof provided already, there’s no use looking for one at run-time.

My motivation is scientific computing (especially linear algebra), which still seems to be unnecessarily handicapped in Java.

Project Euler hosts a growing collection of math programming problems that I started participating in earlier this year while it was on the mathschallenge.net web site. Typically, you have to write a program to solve a math problem and then enter your solution to get credit for it. It took me a couple of months to solve all the existing problems, and since then I’ve been solving new problems as they come out, every few weeks.

There are about 50 participants who solve all the problems as they come out and maintain their status as “100% genius” at the site. Among those, there are about a dozen who compete to solve new problems as quickly as possible since ties in the rankings are broken by time of submission of the solution. New problems always come out on Fridays at 1pm (EST) so I usually don’t get to work on them until the evening, which typically results in a “ranking” of around #15.

This week I was off work for the holidays and delayed our trip up to Hyco Lake for a few hours so I could take a crack at the new problems coming out. There were two new problems this time, involving finding solutions to the same Diophantine equation for certain values of n. In the first problem n was bounded to 1 million, and a simple brute force search worked fine. The second problem allowed n to go to 50 million. I started a similar brute force search running just in case it finished, though I knew there must be a simpler solution (all problems are designed to take less than a minute to execute). Being in a hurry, I only did a little analysis and then studied the first hundred or so brute force solutions to find a pattern and guessed that the pattern held for the whole range. It worked, and I ended up in first place on the scores list, at least until the next problem comes out.

Later, I let the brute force attack complete, which took about an hour. I also took the time to figure out why the pattern I observed held.