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.
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 amount of coin change is the remainder left over after dividing the total change by a dollar. Thus although the total change may or may not obey Benford's Law, the coin change certainly doesn't.
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).
You seem to be confusing change with sticker prices. Have you ever bought stuff at the supermarket as opposed to, say, shopping for merely single items? You'll find that it is incredibly rare to have the total come out at x dollars and 99 cents or some other marketing sticker price.
An interesting wrinkle to this is that an 18 cent coin would make it much harder to make change with the fewest coins for certain values.
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.
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.
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.
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.
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.
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.
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.
> 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.
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.
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
31 comments
[ 3.4 ms ] story [ 83.8 ms ] threadThat said, I don't know where you'd acquire these sorts of statistics.
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.
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."
(Seriously, does ANYONE use coins anymore? It's either bills or a credit card for me.)
They also have http://en.wikipedia.org/wiki/Polymer_banknote which is great in terms of durability.
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.
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.
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.