FORTH GO

My Java bug entry on faster numerics has been summarily closed as unreproducible. There is a short evaluation showing Java to be faster that C at matrix multiplication, but the comparison misses the mark because:

• The C code (not shown) appears to be using nested arrays for matrix storage, which I have never seen in practice for C matrix libraries.
• The Java code is run under the server version of Java, which is fine for a small benchmark but usually not practical for a large (client) app, such as many existing C++ numerics apps are.

Nonetheless, the activity prompted me to rerun my matrix benchmarks. Actually, I had to recreate them since I couldn’t find my Java 1.3 era versions that showed a 15x disadvantage for Java. This time Java fared much better. The tests (C++ Code Java Code) just multiply the same 200×200 matrices over and over with some add operations mixed in for good measure. I tried to make the code fast without working too hard. For instance, I didn’t get GCC to do vectorization, and I didn’t control my environment too well.

I tried two variations of the Java matrix representation and two variations of the Java multiplication code for four total Java variations, of which I took the fastest. The representation variation was whether to use a single array and multiplied indexing or to use nested arrays. The multiply variation was whether to transpose the B matrix or not — transposing it lets the inner loop traverse a one sub-array each from A and B. Arrays of arrays with transposing worked best on my Intel Mac, but flat arrays without transposing was best on the PowerPC Mac. I think the Intel JVM is better about the range check elimination optimization, so it favors the extra arrays with simpler indexing.

2GHz PowerPC Mac

2.33GHz Intel MacBook

On the PowerPC Mac, there was no difference between client and server Java.

So client Java 1.5 is only 3x of C++ and server Java 1.5 is almost the same as C++. Not bad, but not quite what Sun’s evaluation showed. Still need to try Java 6 and turning on GCC vector processing.

Problem 156 at Project Euler is one of the few without a specified limit. That is, most problems might ask for something like the sum of all solutions to an equation that are less than a billion. This one just asked for the sum of all solutions. When I first solved it, I just used the sum of solutions up to a trillion, which was good enough. Later I made some plots to help understand why there are no higher solutions.

Mild spoilers below if you’re thinking about trying the problem.

The problem is to find the solutions to f(x) = x where f(x) is the number of times a given digit, say 4, appears in all the numerals corresponding to the numbers from 1 to x. The equivalent problem is to find where f(x) - x = 0. The plots below show f(x) - x at different scales.

The first scale suggests f(x) - x for the whole range I looked at.

The second scale shows where the function really takes off and why. For each 1e10 range there seems to be about as many 4s as numbers (the function keeps dipping to around 0) until it gets to 4e10 when each new number in the 4e10 to 5e10 range has at least one 4 and sometimes more, so the function really takes off, especially at 4.4e10.

Zooming in more shows a fractal-like nature to the function.

The varying density of the points is because my implementation makes fewer evaluations when further away from the origin.

Comic Steven Wright performed at Durham’s Carolina Theatre last week as part of his When the Leaves Blow Away tour. I’ve been a fan for a long time and saw him perform in Chapel Hill about 20 years ago. His style is still the same, and about half the content was familiar.

This show was about two hours of constant humor, with one short, witty observation after another. A few longer sequences and mini-songs were the only relief for the smile stuck on my face. A couple samples: “the Earth is bipolar” and “what has Jesus ever done for Santa Claus’s birthday?”

After the show I could barely remember any of the jokes, but I know many are still in my brain because they surface into my consciousness when jogged. For instance, yesterday someone was talking about ballet, and I remembered Wright’s observation that the ballet should just get taller ballerinas so they wouldn’t have to dance on their toes.

My only complaint with the performance was that his borderline-mumbling, deadpan delivery sometimes crossed the line and was unintelligible from where I was sitting. If only those other people would stop laughing!