Joshua Bloch is well-known to any Java programmer. He's been working for Google for years now. I just ran across his 2006 blog post talking about broken binary sorts and mergesorts, but really the problem he's describing is simply an overflow in binary integer addition: adding together two numbers whose sum is larger than the largest value an integer can hold.
Joshua's example is using 32 bit integers, which very roughly can hold values between -2 billion and + 2 billion. So, for example, if you tried to add 1.5 billion to 1.6 billion, the result (3.1 billion) is larger than an integer can hold, and the result is invalid. That's an overflow.
I was amused to see him write about overflow as though it were a rare and exotic phenomenon. To those of us who “grew up” with 8 bit microcomputers, overflow is an old “friend” we know very well. Why? Well, simply because the largest number an 8 bit integer can hold is quite small (specifically, -128 to +127), so you'll frequently run into overflow in common sorts of problems. Oh, yes, I know overflow very well. And I suspect that early experience has made me much more sensitive to the possibility of overflow. Everywhere I've ever worked, I've run into (and fixed) examples of possible overflow – they're more common than I suspect Joshua knows.
Most recently I found an example in a signum function, where one integer was subtracted from another, and the sign of the result was tested to see if it was positive or negative. The original code was naively written, making the assumption that no overflow was possible (technically with subtraction the problem is called underflow, but it's really the same thing in the end). Here's a simple example in 8 bit integers: let's say you were comparing +100 to -100. The signum function subtracted the second number from the first number (+100 minus -100). The result you'd expect would be 200 – but that's too large a value to hold in an 8 bit integer. Overflow is the result.
Here's where a “feature” of Java (and many other languages) gets in the way: Java has no test for overflow, and doesn't produce any exceptions. In the example above, the result of (+100 minus -100) is a negative number – definitely not the expected value, and not even the right sign. In a signum function, that means it gives results exactly backward from the intent. It's certainly possible to write Java code that detects overflows, but it's a bit of a pain, and outside the experience and knowledge of most Java programmers. In fact, the very possibility of an overflow seems to catch many Java programmers by surprise, which is probably why these problems are so common.
I've recently been programming a PIC microcontroller, one of the very low-end models in the line. This very primitive little computer is an 8 bit machine, much like the machines I worked on in the '70s. But unlike them, and to my great surprise, the little PIC doesn't even have overflow detection in hardware. Overflow detection is trivial for hardware, so I suspect its omission is more oversight than intent. But in any case, the code I wrote had to look for overflow exactly as you'd have to do in Java...
Wednesday, February 17, 2010
On Bayh's Departure...
The WSJ has a couple of excellent commentary pieces on the meaning of Evan Bayh's departure...
Labels:
Politics
Phobos, Close Up...
The Mars Express robotic explorer has started making a series of close flybys of the Martian moon Phobos. On the closest pass, the surface of Phobos will be just 31 miles (50 km) from the satellite. In addition to collecting science data, the satellite will also map possible landing sites for Russian robotic mission that plans to land on the surface of Phobos next year.The Mars Express mission, over its entire lifetime, plus the Russian Mars mission, cost less than 1/5 of the new “picture window” on the space station. Oh, and the robotic missions are returning huge amounts of actual science data, while the picture window is returning...nothing at all.
Labels:
Mars,
Space,
Technology
Tuesday, February 16, 2010
What Would You Do?
Me? I'm pretty sure you couldn't depend on my normally friendly manner. In fact, I think I'd be thinking quite intensely about my shotgun and how it could best be employed to set this situation right...
Obama Announces Reactor Financing...
Obama is now supporting power generation by nuclear power plants. Not said in this article (though it's certainly implied by the jobs timetable): whether he's also going to direct his Department of Energy to fast-track the plant's licensing. This is quite a turnaround in Obama's green positioning, and it's sure to piss off some of this greenie friends...
Labels:
Environment,
Power,
Technology
Hot Tamales! Mullah Abdul Ghani Baradar is in the Hoosegow!
Mullah Abdul Ghani Baradar captured by a joint U.S.-Pakistani operation. Oh, more of this, please!
Labels:
Afghanistan,
Taliban,
War On Terror
Synthetic Holograms...
Software computes the exposure patterns to create completely synthetic holograms from nothing more than a computer model and a piece of film. Awesome!
Labels:
Holograms,
Software,
Technology
Homemade CPUs...
Here's a nice post (with photos) of some made-from-scratch CPUs (including one made entirely from relays!). I've often thought of doing something like this myself, just for fun. I can add one to the list: back in the mid '70s, I worked with Don Tarbell, one of the microcomputer pioneers. He's most well-known for the Tarbell cassette interface and the Tarbell floppy controller. I wrote a Basic interpreter for him, which he distributed with the floppy controller and as a standalone product. Don had an all-TTL homebrew CPU in his offices, something he built in the early '70s just for fun. At the time, I couldn't imagine anything more intriguing than a project like that...I spent hours with him just poring over the details. He greatly enjoyed having an interested person to talk about it with...
Labels:
History,
Technology
ClimateGate: Mainstream at Last...
There's a nice piece in the WSJ today. The lead:
It has been a bad—make that dreadful—few weeks for what used to be called the "settled science" of global warming, and especially for the U.N. Intergovernmental Panel on Climate Change that is supposed to be its gold standard.It sure is nice to see this sort of thing in the American press. It would be even nicer to see more of it...
First it turns out that the Himalayan glaciers are not going to melt anytime soon, notwithstanding dire U.N. predictions. Next came news that an IPCC claim that global warming could destroy 40% of the Amazon was based on a report by an environmental pressure group. Other IPCC sources of scholarly note have included a mountaineering magazine and a student paper.
Since the climategate email story broke in November, the standard defense is that while the scandal may have revealed some all-too-human behavior by a handful of leading climatologists, it made no difference to the underlying science. We think the science is still disputable. But there's no doubt that climategate has spurred at least some reporters to scrutinize the IPCC's headline-grabbing claims in a way they had rarely done previously.
Labels:
Anthropogenic Global Warming,
ClimateGate
Bye, Bye, Missile...
The Air Force's Airborn Laser Testbed (ALT) took out a missile in a successful test. Think about how much technology has changed warfare between Vietnam and Afghanistan – then try to imagine what things like energy weapons, unmanned aircraft, and pervasive networking are going to do in the next few decades...
Labels:
Technology,
War
Potential Lighting Revolution...
The efficiency of CFL with the light quality of incandescant. Sounds great!
Labels:
Technology
Monday, February 15, 2010
Estonia (and the Other Baltics) Do It Right...
Little Estonia, which I've visited many times, has learned its capitalist lessons better than most.
Better than the clowns in Washington, for sure. Said clowns should be ashamed of themselves, though I see no evidence of that...
Better than the clowns in Washington, for sure. Said clowns should be ashamed of themselves, though I see no evidence of that...
Patterns...
Michael Yon has posted another in his series of outstanding on-the-front-lines reports on the war on terror. Today he's in Afghanistan with the troops fighting our largest battle to date in that land...
He's doing this wonderful work self-funded. Please do as I did, and hit his tip jar – we need more of his fine reporting, and we don't get anything even remotely like it from the lamestream media...
He's doing this wonderful work self-funded. Please do as I did, and hit his tip jar – we need more of his fine reporting, and we don't get anything even remotely like it from the lamestream media...
Labels:
Yon
Bayh Retiring...
Democratic Senator Evan Bayh is retiring from the Senate, and there's a very good chance that his seat will be filled by a Republican. He joins a veritable parade of Democratic incumbents who are retiring from both the House and the Senate. While some have motives unrelated to politics, certainly many of these retirements are motivated by dim prospects in the upcoming elections. Bayh, for instance, faced a very tough battle this November against Republican Dan Coats in a Republican-leaning state, in the year of Scott Brown. It seems doubtful that the Democrats will find a candidate who can successfully oppose the very popular and widely recognized Coats.
Even though I've lived through such things before, I'm still somewhat stunned by the rapid turnaround in the fortunes of the Democrats in general and the Obama administration in particular. At this point, I'd say Obama is going to be lucky to be perceived as well as Jimmy Carter...
Even though I've lived through such things before, I'm still somewhat stunned by the rapid turnaround in the fortunes of the Democrats in general and the Obama administration in particular. At this point, I'd say Obama is going to be lucky to be perceived as well as Jimmy Carter...
Labels:
Politics
America's Cup: USA Wins!
USA 17 (the beautiful hydroplaning trimaran at right, click to enlarge), sponsored by Oracle, has won the America's cup. Congratulations to all involved!
Labels:
Sport
America, Please Don't Go Here...
The United Kingdom has become the land of politically correct. Tragic incidents like this one appear in the news there almost daily. In this case a little girl trapped underwater in a car is left there for almost two hours, even though potential rescuers were on the scene. Why? Because safety regulations forbade anyone other than a specialist rescue team from entering the water. Nobody on the scene even tried to enter the water.
They'd all been emasculated by the pervasive political correctness in the U.K. today.
I'd really hate to see America go this route.
Since the story linked above was posted, the little girl has died...
They'd all been emasculated by the pervasive political correctness in the U.K. today.
I'd really hate to see America go this route.
Since the story linked above was posted, the little girl has died...
Labels:
Political Correctness
Quote of the Day...
Says Nikki Dowling, who has recently started dating other women:
Hats off to you guys who make picking roses look easy.Prior to reading this, it never occurred to me that a woman in a relationship with another woman might experience something closely akin to what a heterosexual man does. Read it...
Labels:
Gender
Could Israel Attack Iran on Her Own?
Retired Israeli General Dan Halutz has some doubts...
Labels:
Iran,
Israel,
Middle East
Women Cause Big Government...
Read it and think about it. Does it match your own experience, no matter how uncomfortable being so politically incorrect makes you feel?
It matches my experience in the aggregate, for sure. By that I mean that if you took all the women whose political tendencies I'm aware of, and ranked them on a one-dimensional scale from leftish to rightish, the average would be well to the left of center. Do that with the men whose political tendencies I'm aware of, and the opposite is true. I can think of plenty of counter-examples on both sides (Anne Coulter, Michelle Malkin, Sarah Palin; Barney Frank, Harry Reid, Paul Krugman), but still...the overall gender difference is there, and fairly obvious.
So here's the obvious question raised: should repealing women's suffrage be an objective of the libertarian, conservative or tea parties?
Just sayin'...
It matches my experience in the aggregate, for sure. By that I mean that if you took all the women whose political tendencies I'm aware of, and ranked them on a one-dimensional scale from leftish to rightish, the average would be well to the left of center. Do that with the men whose political tendencies I'm aware of, and the opposite is true. I can think of plenty of counter-examples on both sides (Anne Coulter, Michelle Malkin, Sarah Palin; Barney Frank, Harry Reid, Paul Krugman), but still...the overall gender difference is there, and fairly obvious.
So here's the obvious question raised: should repealing women's suffrage be an objective of the libertarian, conservative or tea parties?
Just sayin'...
Tea Party Report...
Glenn Reynolds (aka InstaPundit) has a nice WSJ piece about the tea party convention. He's a very sober voice in the generally bizarre lamestream media reporting on the event...
Labels:
Tea Parties
Subscribe to:
Posts (Atom)