Binary floating-point math is inherently flawed. 0.110 is the same as 0.0001100110011001100110011001100110011001100110011...2, which is truncated to 53 bits (the size of a typical floating-point register), which then translates back as 0.100000000000000005551115123125782702118158340454101562510. It's the same problem as trying to represent one-third in base ten; any limit to the number of threes after the decimal makes it fundamentally a different number. (Note that in base 3, one-third is very cleanly represented as 0.13.)
You may then think, "forget that! I'll do floating-point with text strings so that I have perfect accuracy!" But even text strings are limited -- consider the aforementioned representation of one-third, which would have an infinite number of threes. Even adding a mechanism to designate repeating digits will not handle irrational numbers such as sqrt(2).
So we're stuck in an imperfect world. The best anyone can do is try to recapture the original value by rounding. There are many algorithms for rounding, despite what you remember from elementary school math. The one everyone knows is called "round half away from zero". That is, half (0.5) is always rounded up on positive numbers and down on negative numbers. 1.5 becomes 2, 2.5 becomes 3, and -3.5 becomes -4. However, the accounting world uses a different one called "round half up", where half (0.5) is always rounded up regardless if it's positive or negative.
Both of these introduce bias, which is math-speak for "long-term error". Imagine a long set of uniformly distributed random fractional numbers -- all the fractional parts under 0.5 that are rounded down will, in the long run, be balanced out by all the fractional parts above 0.5 that are rounded up, so there's zero long-term error there. But, with "round half up", every occurrence of 0.5 in the number set introduces a rounding error of 0.5 that is not balanced out by anything else. With "round half away from zero", that problem is addressed, but only if the numbers are half positive and half negative.
The gold standard for rounding in practical computer science is called "round half to even" (or sometimes "banker's rounding", among other colorful names). The idea is to round 0.5 to the closest even number, e.g. 5.5 and 6.5 both round to 6. This addresses the bias problem with separate sets of positive numbers and negative numbers, but only if the range of numbers is itself an even number. That is, applying this to numbers between 0 and 2 works great (0.5 rounding down is balanced by 1.5 rounding up), but not to numbers between 0 and 3 (because 2.5 rounds down and there's no corresponding half-point that rounds up).
Thursday, October 15, 2009
Wednesday, May 27, 2009
full circle
This morning's San Jose Mercury News had a dismaying and perplexing image on its front page. With the defeat of the repeal of Prop 8, gay marriage has been certifiably defeated in California. The image on the newspaper was of a smug black guy (Chauncey Killens) relishing that the word of god had been followed, with some exasperated woman trying, vainly, to argue about it.
Notwithstanding the merits of the larger issue, isn't there something troublingly ironic about a black guy reveling in a court decision to restrict the civil rights of a minority?
Does it ever cross his mind that without level-headed people interjecting on blacks' behalf against bible-toting slaveowners, he himself would be a trampled minority? Does he recognize the connection to the gay marriage issue?
I don't understand social conservatives. They're usually self-contradictory, but this example's especially egregious.
Notwithstanding the merits of the larger issue, isn't there something troublingly ironic about a black guy reveling in a court decision to restrict the civil rights of a minority?
Does it ever cross his mind that without level-headed people interjecting on blacks' behalf against bible-toting slaveowners, he himself would be a trampled minority? Does he recognize the connection to the gay marriage issue?
I don't understand social conservatives. They're usually self-contradictory, but this example's especially egregious.
Monday, March 9, 2009
the disillusioning inevitability of swing votes
You're familiar with a swing vote: it's the single vote that breaks a voting tie. I hate them. A swing vote is the very antithesis of democracy. It places the power of a decision entirely on a single person, making all other votes irrelevant.
I was discussing this with the mayor of Los Gatos yesterday. He and his wife Kim also don't like the swing vote situation. (We got on this topic because we were talking about the recent California budget resolution that passed by a single republican vote. Even though there were at least three republicans who voted for the resolution, the last one (the swing vote) is getting tons of heat from the party for being a turncoat.)
My first thought was that maybe this is why some resolutions require two-thirds majority to pass instead of just simple majority. But even that can have a swing vote as well -- if 66 have voted for and 33 against, that next vote decides the issue. Even unanimous votes can have them -- with 99 in favor, that last vote decides whether it passes or not.
How disillusioning that the democratic ideal of "majority rule" can still degenerate into occasional autocracy.
I had a thought for how to prevent that, which is to make resolutions scalable: they always pass if anyone votes for them, but they're scaled down to the percentage of affirmative votes. For example, if there's a bill to spend $1,000 on a library but it only gets 4 of the 10 votes, then the library get $400. However, that doesn't work when the issue is binary, such as declaring war. ("Yes Mr. President, you may declare war for 57/100ths of each day. The rest of the day you cannot be at war.") It also doesn't work when politicians get selfish, because they can propose a bill that their district gets a bajillion dollars, and when the results come back at 1 vote for and 99 against, their district would still get 1/100th of a bajillion dollars.
Why does it seem that discussions about government never result in immutably correct answers?
I was discussing this with the mayor of Los Gatos yesterday. He and his wife Kim also don't like the swing vote situation. (We got on this topic because we were talking about the recent California budget resolution that passed by a single republican vote. Even though there were at least three republicans who voted for the resolution, the last one (the swing vote) is getting tons of heat from the party for being a turncoat.)
My first thought was that maybe this is why some resolutions require two-thirds majority to pass instead of just simple majority. But even that can have a swing vote as well -- if 66 have voted for and 33 against, that next vote decides the issue. Even unanimous votes can have them -- with 99 in favor, that last vote decides whether it passes or not.
How disillusioning that the democratic ideal of "majority rule" can still degenerate into occasional autocracy.
I had a thought for how to prevent that, which is to make resolutions scalable: they always pass if anyone votes for them, but they're scaled down to the percentage of affirmative votes. For example, if there's a bill to spend $1,000 on a library but it only gets 4 of the 10 votes, then the library get $400. However, that doesn't work when the issue is binary, such as declaring war. ("Yes Mr. President, you may declare war for 57/100ths of each day. The rest of the day you cannot be at war.") It also doesn't work when politicians get selfish, because they can propose a bill that their district gets a bajillion dollars, and when the results come back at 1 vote for and 99 against, their district would still get 1/100th of a bajillion dollars.
Why does it seem that discussions about government never result in immutably correct answers?
Wednesday, March 4, 2009
fundraising with copper
For my community-service group, I recently looked into the effectiveness of a suggested fundraiser: a penny drive. Pennies are easy donations because they're virtually worthless, so no one thinks twice about unloading them.
However, the particular idea here was not to deposit the pennies into the bank, but rather to melt them down for their high-value copper. Copper is becoming rare, so its value has been steadily increasing (which is why you hear about people pilfering copper wire and copper pipes from construction sites and other unguarded buildings).
My first question to ask was, how much is the copper in a penny actually worth?
The answer isn't straightforward because pennies have changed over the years. When pennies were introduced in 1793, they were pure copper. Here's the history of the metal makeup by mass:
1793–1857: 100% copper
1857–1864: 88% copper, 12% nickel
1864–1942: bronze (95% copper, 5% tin and zinc)
1943: zinc-coated steel (steel is iron and carbon)
1944–1946: brass (95% copper, 5% zinc)
1946–1962: bronze (95% copper, 5% tin and zinc)
1962–1982: brass (95% copper, 5% zinc)
1982 on: 97.5% zinc core, 2.5% copper plating
As you can see, the pennies in 1982 and beyond have a trivial (and unextractable) amount of copper in them, so the first step of the fundraiser would be to separate the pennies into "pre-1982" and "post-1982" bins. The ones in the "post-1982" bins would be deposited in the bank directly. (Though, actually, when the value of zinc increases enough, it would be worth it to melt them down for that.)
Before 1982, pennies had a mass of 3.11 grams, so the amount of copper in them was 95% of that: 2.9545 grams. A first-order search for the current value of copper gave me around $1.70 per pound. 2.9545 grams of copper is then worth 1.1 cents.
A 10% return on investment isn't bad (especially when the principle is donated!), but the next consideration is volume. To raise an appreciable amount of money (say, $1,000), we would need to collect over 90,000 pre-1982 pennies. That's 623 pounds of pennies. Nobody is about to carry that around. Worse, pre-1982 pennies are less common than post-1982 pennies, so we would have to collect more than twice that number.
At this point, this fundraising idea started to look not very feasible.
But then I found the real killjoy to this fundraising idea: it's actually illegal to melt down coinage now. The U.S. Mint anticipated people would try this again and made regulations to prohibit it.
Oh, well. Onto the next idea.
However, the particular idea here was not to deposit the pennies into the bank, but rather to melt them down for their high-value copper. Copper is becoming rare, so its value has been steadily increasing (which is why you hear about people pilfering copper wire and copper pipes from construction sites and other unguarded buildings).
My first question to ask was, how much is the copper in a penny actually worth?
The answer isn't straightforward because pennies have changed over the years. When pennies were introduced in 1793, they were pure copper. Here's the history of the metal makeup by mass:
1793–1857: 100% copper
1857–1864: 88% copper, 12% nickel
1864–1942: bronze (95% copper, 5% tin and zinc)
1943: zinc-coated steel (steel is iron and carbon)
1944–1946: brass (95% copper, 5% zinc)
1946–1962: bronze (95% copper, 5% tin and zinc)
1962–1982: brass (95% copper, 5% zinc)
1982 on: 97.5% zinc core, 2.5% copper plating
As you can see, the pennies in 1982 and beyond have a trivial (and unextractable) amount of copper in them, so the first step of the fundraiser would be to separate the pennies into "pre-1982" and "post-1982" bins. The ones in the "post-1982" bins would be deposited in the bank directly. (Though, actually, when the value of zinc increases enough, it would be worth it to melt them down for that.)
Before 1982, pennies had a mass of 3.11 grams, so the amount of copper in them was 95% of that: 2.9545 grams. A first-order search for the current value of copper gave me around $1.70 per pound. 2.9545 grams of copper is then worth 1.1 cents.
A 10% return on investment isn't bad (especially when the principle is donated!), but the next consideration is volume. To raise an appreciable amount of money (say, $1,000), we would need to collect over 90,000 pre-1982 pennies. That's 623 pounds of pennies. Nobody is about to carry that around. Worse, pre-1982 pennies are less common than post-1982 pennies, so we would have to collect more than twice that number.
At this point, this fundraising idea started to look not very feasible.
But then I found the real killjoy to this fundraising idea: it's actually illegal to melt down coinage now. The U.S. Mint anticipated people would try this again and made regulations to prohibit it.
Oh, well. Onto the next idea.
Tuesday, March 3, 2009
Hello, world
I must begin with the requisite inanities that give blogs their reputation:
8:02am: the alarm went off and I got up. I thought I hit "dismiss", but I found out ten minutes later that I had actually hit "snooze".
8:07am: had some coffee.
8:14am: started making an omelet.
8:29am: munched the omelet. It was yummy.
8:37am: got in the shower. It was nice and warm.
8:51am: got dressed. Fun, fun.
9:03am: logged into work from home to check email. Nothing important going on.
9:57am: went to Costco to pick up some stuff.
11:34am: left Costco and went to work.
....okay, enough of that, I can't stand it any more. I'm sure there's some excellent humor to be extracted from heckling stereotypical blog posts, but in the effort to convey vapid insignificance I am boring myself to death.
8:02am: the alarm went off and I got up. I thought I hit "dismiss", but I found out ten minutes later that I had actually hit "snooze".
8:07am: had some coffee.
8:14am: started making an omelet.
8:29am: munched the omelet. It was yummy.
8:37am: got in the shower. It was nice and warm.
8:51am: got dressed. Fun, fun.
9:03am: logged into work from home to check email. Nothing important going on.
9:57am: went to Costco to pick up some stuff.
11:34am: left Costco and went to work.
....okay, enough of that, I can't stand it any more. I'm sure there's some excellent humor to be extracted from heckling stereotypical blog posts, but in the effort to convey vapid insignificance I am boring myself to death.
Subscribe to:
Comments (Atom)
