Friday Jan 20, 2006

Cosine redux

It's been quite a while since my last blog entry: I had a bit of a technology meltdown that I'm not quite done with yet :-(

I was doing some recreational hacking over the holidays that involved evaluating cosines. I ended up doing (once again!) an implementation of cosine (don't ask why). Given the confused flamage that my previous posts on cosine generated, I figure that showing some code would be useful. I would never have thought that cosine would generate so much email traffic. Yes, I know about Taylor series. No I wasn't trying to insult centuries of standard mathematical practice. Performance is often the art of cheating carefully.

So, here's my implementation of cosine, with its argument in turns (1 turn == 360 degrees):

public static float cost(float f) {
    int bits = Float.floatToRawIntBits(f);
    int mantissa = (bits&0x7FFFFF)|(1<<23);
    int shift = (bits<<1>>>24)-127+9; // exponent, unbiased, with shift
    if(shift>=32 || shift<=-32) return 1;
    int fractionBits = shift>=0 ? mantissa<<shift : mantissa>>-shift;
    int tableIndex = (fractionBits>>>(30-resultPrecision))&tableSizeMask;
    switch(fractionBits>>>30) { // Quadrant is top two bits
        case 0: return cosTable[tableIndex];
        case 1: return -cosTable[tableSizeMask-tableIndex];
        case 2: return -cosTable[tableIndex];
        default/\*case 3\*/: return cosTable[tableSizeMask-tableIndex];
    }
}
Lets go through this slowly:
  1. int bits = Float.floatToRawIntBits(f);
    Get the IEEE 754 bits
  2. int mantissa = (bits&0x7FFFFF)|(1<<23);
    The mantissa is the bottom 23 bits - to which the hidden bit must be prepended.
  3. int shift = (bits<<1>>>24)-127+9;
    Extract the exponent, correct for the exponent bias, then add a bias to move the binary point to the top of the word.
  4. if(shift>=32 || shift<=-32) return 1;
    If the shift is too large, the fraction bits would be zero, therefore the result is 1.
  5. int fractionBits = shift>=0 ? mantissa<<shirt : mantissa>>-shift;
    Shift the mantissa so that it's a fixed point number with the binary point at the top of the 32 bit int. The magic is in what's not here: because the argument is in turns, I get to ignore all of the integer bits (range reduction made trivial); and because it's the cosine function, which is symmetric about the origin, I get to ignore the sign.
  6. int tableIndex = (fractionBits>>>(30-resultPrecision))&tableSizeMask;
    The top two bits are the quadrant... extract the bits below that to derive a table index.
  7. switch(fractionBits>>>30) {
    One case for each quadrant. This switch could be eliminated by making the table 4 times larger.
  8. case 0: return cosTable[tableIndex];
    Yes! It's just a table lookup! Truly trivial.
  9. case 1: return -cosTable[tableSizeMask-tableIndex];
    ...
Since this is just a table lookup, the resulting approximation can be pretty jagged if the table is small. But it's easy to tune the table size depending on accuracy needs. The smaller the table is, the higher the cache hit rate will be, and the more likely it is that the whole table will fit in cache.

Table lookups are a very common way to implement mathematical functions, particularly the periodic ones like cosine. There are all kinds of elaborations. One of the most common for improving accuracy is to do some sort of interpolation between table elements (linear or cubic, usually).

Friday Sep 09, 2005

Back at work again

Having taken a chunk of time off in August to hang out with family (including one very active 90-year-old aunt's birthday party) I'm back at work. This week I've been visiting customers and participating in developer events. I spent Monday in Zurich visiting developers. The rest of the week I've spent in St Petersburg (not Florida). We did a big developer event on Thursday and ended up with hugely more folks attending than we had expected. We had people sitting in the aisles in the theatre.

Besides having cornered the world market in over-the-top palaces, St Petersburg has a large population of talented software developers. Sun has an engineering center here where we do a lot of work on JavaSE and JavaME and C/C++/Fortran(!) optimizing compilers.

Next week: JavaChina

(Fri Sep 09 21:33:25 PDT 2005)

Friday Jul 01, 2005

T Shirt Contest Trivia

I made up some cheesy certificates to give to the winners of the TSHC contest. I was trying to come up with a catchy slogan to put at the top of the certificate, but everything I could think of was boring. But it occurred to me that boring stuff sounds cool if it's in Latin. But I don't know Latin, so I asked Guy Steele (who knows Latin) if he could come up with anything. Here's his reply:

Yeah, I studied Latin for six years. The principal difficulty is that the right word for "hurler" is "jaculator", which is uncomfortably close to English "ejaculator" (which, of course, is etymologically no coincidence). Also, if your winner is a female, it ought to be "jaculatrix", which is a legitimate Latin word for "female hurler" or "spearwoman", but thanks to the one-time co-opting of Latin for sexual euphemism, I fear that "jaculatrix" will be misinterpreted by most moderns as some sort of transgendered dominatrix or something.

How about something like "athleta tunicis fortissimus", which translates as "strongest winner of a prize with tunics"? (I figured "tunic" is about as close as we can hope to get to "T-shirt".) The word "athleta" meant "winner of a prize", which has evolved into the modern "athlete". Or, for real flavor,

ATHLETA TVNICIS FORTISSIMVS

in nice, classic, chiseled Roman lettering. (By the way, "athleta", a borrowing from Greek, is considered to be a masculine noun in Latin, despite the "-a" ending, so the "-us" ending on "fortissimus" really does match it properly. The "-is" on "tunicis" indicates the ablative case.)

(Fri Jul 01 15:49:26 PDT 2005)

Thursday Jun 30, 2005

The T-Shirt Hurling Contest

Get the e-newsletter: Sign up now for the On Demand Business e-newsletter. On Demand Business is helping smaller companies like yours win big. Learn how.
(Thu Jun 30 13:59:09 PDT 2005)

Tuesday Jun 28, 2005

T-Shirt hurling contest: day 2

Peter Moore and his mates from Cenqua in Australia were the second contestants in the T-Shirt contest. Their entry was a contraption (I don't know a better word: Rube Goldberg would have been thrilled) that used centrifugal force to propel the shirts, and a pile of electronics to figure out when to let go. If you'd like to get a better look, they have a large collection of photos up on the web. The release mechanism involved infrared sensors on the spinning wheel that operated the solinoids that released the shirts. The sensors were used to receive trigger information from the computer and a funky wire-wrapped board.

The early prototypes were pretty straightforward. No electronics. Real reliable. What they ended up with was a total victory for creeping featurism.

They managed to launch a reasonable number of shirts, and got great range, but the vast majority of the shirts were randomly spewed all over the stage and backdrop. The infrared sensors were their undoing, and an interesting case study in just how hard testing is.

They had done a lot of testing, in lots of circumstances. They had had problems the night before with the stage lights having enough IR to trigger the device prematurely. They had tuned and corrected for that. But it was the large, professional-grade photographic flashes that did it. No one had fired off one of those in the vicinity of the launcher during any test runs.

Just as in every branch of engineering, "shit happens", and it's incredibly hard to predict.

(Tue Jun 28 13:31:01 PDT 2005)

Monday Jun 27, 2005

Monday's JavaOne keynote

Lots and lots of cool stuff... Not nearly enough time to write about it all. The thrills started even before the keynote: the jazz group that provided the opening music including one of my all time favorite musicians: Paul Horn. A real treat.

Then there was all the stuff about open sourcing of our app server, a project internally named GlassFish. It's all out there at glassfish.dev.java.net. We've been pricing the binaries at $0 for quite a while, now all of the source is out there for anyone to grab and play with. It'll be the place where we do our work on the evolution of Java EE.

IBM being there was wonderful: the contract negotiations had gone on for quite a while, and resolved to everyone's satisfaction. They've been great supporters for years and I'm very happy to have all the details clear once again.

One of the sleeper activities that has been going on is the definition of the blu-ray next generation DVD standard. Java (a relative of the J2ME spec) is how dynamic behavior is defined on a DVD disk: every DVD player will have a Java VM and a network connection. There are huge possibilities...

Then there was the new stuff in Java Studio Creator... Particularly the support for AJAX.

(Mon Jun 27 17:17:44 PDT 2005)

Friday Jun 24, 2005

JavaOne sponsors

I was just looking through the JavaOne sponsors list. It's pretty impressive this year. It's great to see IBM, Oracle, Nokia and BEA as Platinum sponsors. They've all been huge pillars of the Java community and it's great to see them at the show again.
(Fri Jun 24 09:28:39 PDT 2005)

Tuesday Jun 21, 2005

Real Time != Real Fast

Since I've been involved in real time programming and the Real Time Specification for Java (JSR1) work, I've had a lot of people ask me about where real time can be used. There's more than a little confusion: many folks who've asked for "real time" actually want "real fast" (throughput computing). In real time computing, meeting a very precise deadline is of paramount importance. In throughput computing, the goal is to get as much done as possible as soon as possible.

I hate to use sports analogies, but this a a situation where one works well. Consider baseball: how fast you swing the bat is less important than that the bat be in the right place at the right time in order to connect with the ball. Real time programming is kind of like being a batter where the pitcher throws the balls continuously. And instead of a catcher behind the home plane you have a sleeping troll who will eat you if a ball gets through and hits him.

A good way to think of throughput computing is the old Sharpen the Axe principle:

If I had eight hours to chop down a tree, I'd spend six sharpening my axe. -- Abraham Lincoln

Many activities done in standard programming can be thought of this way: they're things you do now that are not directly useful, but later on they make life better. This is everything from JIT compilers and garbage collectors down to simple things like hash tables. (Hash tables? Yes! That "re-hashing" phase that happens when tables overflow adds a bump of cpu cost; hashtables that chain instead of rehashing have non-linear [unpredictable] lookup costs).

The number of developers who truly need to do realtime is very small. But the stuff they do affects us all. Planes, trains and automobiles: all need realtime.

(Tue Jun 21 16:23:01 PDT 2005)

Sunday Jun 19, 2005

A BlogEd feature I hadn't realized existed...

I can publish my blog to two sites at the same time! Both blogs.sun.com and today.java.net. Bonus!
(Sun Jun 19 16:37:45 PDT 2005)

Friday Jun 17, 2005

1+1 = i

I need to stop talking to reporters. It's so easy for what results to get misunderstood. I was not trying to say that all open source projects are chaotic: there is a spectrum. Apache is at the very high end of the scale, on average exhibiting excellent behaviour. Their governence rules are very effective. Apache and the Linux kernel set the Gold Standard. But they aren't all of the open source universe, and there's some decidedly oddball behaviour that goes on. The problem is that it's often the crazy behavior that becomes publicly visible and it tarnishes everything. When I made the comment that got so misunderstood I was talking about the perception of the open source community by outsiders.

Even at the Gold Standard end of the scale there are problems. Take a recent event: the blowup between Linus and the Bitkeeper folks: while I'd bet real money that Linus did the Right Thing, the way it played out in the press looked pretty bad. It may have been impossible to play it out at any lower flame temperature, but somehow the community needs to come to grips with how it is percieved

(Sat May 28 22:07:50 PDT 2005)
About

jag

Search

Categories
Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today