What the U.S. needs is an 18-cent coin(radio-weblogs.com)
radio-weblogs.com
What the U.S. needs is an 18-cent coin
http://radio-weblogs.com/0105910/2003/05/16.html
31 comments
I don't know why you're saying it isn't NP-complete. For an arbitrary set of coins, it's definitely NP-complete. You could easily reduce 0-1 ILP to it, or subset-sum.
If you don't believe me, believe http://graal.ens-lyon.fr/~abenoit/algo09/coins2.pdf
"Optimally making change—representing a given value with the fewest coins from a set of denominations—is in general NP-hard."
If you don't believe me, believe http://graal.ens-lyon.fr/~abenoit/algo09/coins2.pdf
"Optimally making change—representing a given value with the fewest coins from a set of denominations—is in general NP-hard."
> Shallit assumed that every amount of change between 0 and 99 cents is equally likely.
Fail. He could at least have blagged some transaction data from a retailer that actually does a bunch of small cash transactions. Just getting copies of the receipt roles from his local bodega would be better than this.
Fail. He could at least have blagged some transaction data from a retailer that actually does a bunch of small cash transactions. Just getting copies of the receipt roles from his local bodega would be better than this.
Why does it have to be small transactions? Every transaction, regardless of size, has a chance to end in anything from 0 to 99. The more items on your receipt the more chances to have different variations. Plus tax rate varies from area to area. I don't think that his assumption is that far off. But yes, he probably could have done something to get actual data.
It should be small transactions because cash is being used less and less often for medium-to-large transactions.
It's not safe to assume that all cent values from 0 to 99 are equally likely because of the fact that cash transactions tend to be small. The number of items being purchased will also tend to be small. So the fact that most prices for individual items tend to end in 99, 95 or some other multiple of five cents should have a huge impact on the distributions in real life, especially for transactions to which sales tax does not apply.
For example in Oregon, a state with no sales tax, the fewest number of items you'd be able to buy at $0.99 or $0.95 to get a $x.32 total is at least 20. (That's a whole lot of "fun size" bags of potato chips.) The total would come out to $19.32, at which point a lot of people would just pay with plastic, anyway. Perhaps most people would.
It's not safe to assume that all cent values from 0 to 99 are equally likely because of the fact that cash transactions tend to be small. The number of items being purchased will also tend to be small. So the fact that most prices for individual items tend to end in 99, 95 or some other multiple of five cents should have a huge impact on the distributions in real life, especially for transactions to which sales tax does not apply.
For example in Oregon, a state with no sales tax, the fewest number of items you'd be able to buy at $0.99 or $0.95 to get a $x.32 total is at least 20. (That's a whole lot of "fun size" bags of potato chips.) The total would come out to $19.32, at which point a lot of people would just pay with plastic, anyway. Perhaps most people would.
I suppose. I guess I use cash more than others. I would easily toss a $20 at a $19.32 bill.
I stopped reading after this and came here to say this :-)
The assumption that every possible value from 0 to 99 is equally likely doesn't seem like the best idea. In a country where the cost of items usually ends in .99, .97, or the like, and the sales tax is added after the fact (and usually from 0-10%), is it still the best choice? The post (and cited paper) don't seem to mention this.
That said, I don't know where you'd acquire these sorts of statistics.
That said, I don't know where you'd acquire these sorts of statistics.
But taxes vary throughout the areas. And adding more items together. and splitting the dinner bill among friends. and all sort of other things that can make the final total anything from 0 to 99. I don't think it is silly to make the assumption they are equally likely. But I also don't know where you'd acquire these sorts of statistics.
Completely agree: prices are not set arbitrarily or via direct calculation in many cases, but are driven by marketing ($1.99) or optimization (the local pizza shop that works everything out to even $ or 50c).
I also wondered about the random assumption. The thing that made me question the assumption the most is Benford's law.
I don't think Benford's law applies here: it's about the first digit of numbers (that are distribute in a certain way), but in most cases the first digit of a price will be denominating dollars, not cents.
The leading digit of change is tens of cents...
The change may be more than a dollar, so tens of cents is not necessarily the leading digit.
Credit card companies would know, but probably not publish.
People can multiply 1, 5, 10, and 25 with zero difficulty. An average person would likely resent being forced to count multiples of a less round number such as 18. For that reason alone, such a change is unlikely to come about.
No. What the U.S. needs is NO coins.
(Seriously, does ANYONE use coins anymore? It's either bills or a credit card for me.)
(Seriously, does ANYONE use coins anymore? It's either bills or a credit card for me.)
Yes, I still use coins. They're very handy for vending machines, parking meters, highway tolls, stupid magic tricks, decision making, purchasing one taco at taco bell, carnival food, making wishes, receiving change, and so on. I don't think coins will go away as long as paper currency remains, unless we start printing bills worth less than a whole dollar, or we become so rich that we don't concern ourselves with values less than one dollar.
exactly. I've been in singapore the past couple of weeks and they have a S$ 1 coin and it's been awesome.
They also have http://en.wikipedia.org/wiki/Polymer_banknote which is great in terms of durability.
They also have http://en.wikipedia.org/wiki/Polymer_banknote which is great in terms of durability.
I don't use coins not because I use bills instead; I don't use coins because I don't use much cash.
I just came from a 3 week business trip in Europe, and at least the people I was around use the €1 and €2 coins all the time. I wish we'd get rid of our $1 bills and go to a $1 and $2 coin as well; very convenient. From what I understand, it's cheaper for the gov't in the long run too.
I just came from a 3 week business trip in Europe, and at least the people I was around use the €1 and €2 coins all the time. I wish we'd get rid of our $1 bills and go to a $1 and $2 coin as well; very convenient. From what I understand, it's cheaper for the gov't in the long run too.
There's already $1 Billion in minted $1 coins already, but nobody wants them: https://www.npr.org/2011/06/28/137394348/-1-billion-that-nob...
If we got rid of $1 bills, I suspect the demand would go up some ;-)
As a non-American I'm always surprised that people want them to go away. I can't imagine buying anything without using coins. Is every price rounded up instead of the deceiving 99 Cents? Do you buy two items for 50 Cent each instead of one so you can pay with a bill?
I'd say it's banknotes that I don't use any more (here in the UK, which has the advantage of coins that go up to GBP2). For small amounts (vending machine, street food) it's coins; for anything larger it's credit card.
Or, they could get rid of every coin smaller than a quarter. Assuming every amount of change less than a dollar is equally likely, the average number of coins needed to make change now becomes 1.5 - and it's not like anybody really uses anything less than a quarter for anything other than coinstar anyways
[deleted]
Whenever taxation changes it will shift the "average transaction value" by a few cents and invalidate the added usefulness of already minted coins
How do we make change in everyday life? The simple algorithm everyone knows, even if they don't know what an algorithm is, is to start with the largest coin and move down, taking as many of each as you can. Thus to make change for 72 cents we: take 2 quarters, leaving us with 22 cents take 2 dimes, leaving us with 2 cents take no nickels take 2 pennies, leaving us with 0 cents and we're done
This algorithm as it turns out is only optimal so long as each denomination is at least twice as much as the previous one. So what happens if we have an 18 cent coin? Let's make change for 37 cents. With the simple algorithm we end up with {1 quarter, 1 dime, 2 pennies}. That's four coins. However you can do it with three coins: {2 18 cent pieces, 1 penny}.
The algorithm for the case with arbitrary denominations isn't np-complete (it's a fun algorithms question to figure out), but it's way too difficult to be doing in your head all the time.