You may have noticed that the knapsack problem in today’s comic has two solutions. I thought that (spoiler alert!) the 1, 0, 0, 2, 0, 1 solution was the only one, but 7, 0, 0, 0, 0, 0 — seven orders of mixed fruit — also works. Why did this happen? Well, I checked my numbers with a short Perl script (written while on vacation, with adorable kids climbing on me). It found the right answer in all my tests but broke when it really mattered. Witness the result of this line of Perl:
perl -e ‘print 2.15*7, “\n”, 15.05, “\n”, (2.15*7 == 15.05) ? “true” : “false”, “\n”;’
15.05
15.05
false
Long story short, it claimed 2.15*7 did not equal 15.05, and so it missed the second answer in the search, though it found the first just fine
I know this sort of thing happens with floating-point math, but I didn’t expect it to break this badly and inconsistently on such a simple task. (edit: at that point, I was actually thinking of this as a weight problem (the variable was $weight), not a monetary problem, so separate cents math wasn’t an obvious choice).
Thank you to Chris Shabsin and Nick Moffitt for helping me pin down the problem.
Should’ve done the math in cents.
To work around floating point math, you could multiply the prices by 100. That way, you work with cents instead of the base currency, so integer math can be used.
Yeah. the way Real Software That Deals With Money does it is to make cents (or tenths of cents, or in rare occasions hundredths of cents) the unit, instead of dollars.
Vorn
Alternatively you could replace your comparisons as follows:
(2.15*7 == 15.05)
becomes
(15.05 – 2.15*7
You may very well know all this already, but the reason 2.15*7 != 15.05 is because 2.15*7 is being calculated, and is therefore stored with a different range of precision. It’s usually bad practice to compare floating point numbers for equality because of this, it turns out.
According to http://docs.sun.com/source/806-3568/ncg_goldberg.html,
q = 3.0/7.0
if q = 3.0/7.0 then print “Equal”:
else print “Not Equal”
prints “Not Equal” with Borland TurboBasic. The same code *works* in Perl, but I think the basic idea is that in any language, comparing floats is fraught with peril.
Incidentally, replacing your numeric equality comparison (==) with string equality comparison (eq) fixes the problem.
gah, it thought that was an html tag. lets try this again
15.05 -2.15*7 \
Ok, by now you’ve probably guessed that’s supposed to be a less than sign… the rest is as follows
=0.001)
Since we’re dealing with cents, the extra will only show up for floating point errors.
$ perl -e ‘printf(“%.21f %.21f %s\n”, 15.05, 2.15*7.0, (2.15*7.0 == 15.05) ? “true” : “false”);’
15.050000000000000710543 15.049999999999998934186 false
Thanks for the opportunity to write my first python script. I’m really glad I happened to decide to multiply everything by 20, calculating in nickels instead of pennies. It would have been really easy to fall into the same trap.
Steve – maybe try < to get <?
I thought the IEEE floating point specification and library included logic to ensure these comparisons came out correctly. Does perl use some other floating point library? Or am I incorrect about IEEE?
OK, now I have to go write a C program. *shakes fist*
I whipped up a script to find the answer in Perl. I almost used floating point numbers, thinking, like you, “bah, what are the chances of things going wrong.” Glad I decided at the last minute to do my math in cents. Also, I found it interesting that it’s a pretty easy problem to brute force. I appreciate that the knapsack problem is supposed to be uncomputably difficult (and thus is used for some cryptographic systems), but apparently for small enough sets of options it’s no big deal. At the absolutely worst case you have to test a mere 7^8 (5,764,801), which is trivial on a modern computer. With some simple optimizations to avoid getting the same order with the appetizers ordered in different orders, it ended up being fast enough that I got the two answers within a second on a 1.6Ghz machine with a really quick-and-dirty script.
never compare floats for equality
as others mentioned above, using cents works well
in ml, floats belong to a class of numbers that don’t have a well-defined equality operator, so the strong typing won’t allow comparison of that variety, although greater than and less than are allowed
worst case for knapsack with all positive weights
suppose n weights, smallest weight is m units, and goal weight is g units
the solution is a string whose alphabet is Zg/m and whose length is n
so a brute force is O((g/m)^n), which is nonpolynomial
subscript markup didn’t work
that Zg/m thing is supposed to refer to the set corresponding to the sequence of natural numbers up to the smallest integer greater than or equal to the ratio of g to m
What is the difference between a tip calculator and a regular one?
FIXED POINT MATH 4 LIFE!
Why not do it with a backtracking engine?
perl -e'$_="no" for $mf,$ff,$ss,$hw,$ms,$sp; ("x" x 1505) =~ /\A((x{215})(?{ local $mf = $mf + 1 }))*((x{275})(?{ local $ff = $ff + 1 }))*((x{335})(?{ local $ss = $ss + 1 }))*((x{355})(?{ local $hw = $hw + 1 }))*((x{420})(?{ local $ms = $ms + 1 }))*((x{580})(?{ local $sp = $sp + 1 }))*\z(?{ print "$mf mixed fruit, $ff french fries, $ss side salad, $hw hot wings, $ms mozarella sticks, $sp sampler plate\n" })(?!)/'And here’s a generic version.
#!/usr/bin/perluse strict;
use warnings;
use re 'eval';
my %menu = (
'mixed fruit' => 215,
'french fries' => 275,
'side salad' => 335,
'hot wings' => 355,
'mozarella sticks' => 420,
'sampler plate' => 580,
);
my $total = 1505;
##########################################
my %order;
my @order_test = (
map qq{
(?:
(?: x{$menu{$_}} ) # consume the given number of units
# worked, so increase the number of orders for this thing;
# `local` makes this temporally scoped
(?{ local \$order{ "\Q$_\E" } = \$order{ "\Q$_\E" } + 1 })
)*
},
keys %menu,
);
my $menu_evaluator_regex = qr{
\A @order_test \z # find a match for these orders
(?{
my $order = join ', ', (
map "$order{$_} $_",
sort { $menu{$a} <=> $menu{$b} }
keys %order
);
print "$order\n";
})
(?!) # fail at last possible moment
# so engine will backtrack for more matches
}x;
my $total_units = "x" x $total;
$total_units =~ m/$menu_evaluator_regex/;
Bah, that’s impossible to read with the botched indentation.
I’ve reposted the code at http://use.perl.org/~Aristotle/journal/33760
Oaf:
Floating Point math 4.0 life!!!!
“Yeah. the way Real Software That Deals With Money does it is to make cents (or tenths of cents, or in rare occasions hundredths of cents) the unit, instead of dollars.”
True. The very concept of a floating point number does not match well with money, as it’s designed with significant digits in mind, while money is always significant to an arbitrarily small quantum. I used to redefine the equals operator to test if abs((a-b)/(a+b))
sigh. that’s abs((a-b)/(a+b)) .lt .00001
Since I know almost exactly nothing about computer coding and stuff: what exactly went wrong?
Surely multiplying with accuracy of .05 should not produce any errors – it’s COMPUTERS we’re talking about. They can do anything, can’t they?
Also, what is floating point math(s)? Please don’t confuse me, that’s what Wikipedia is for.
Strictly speaking the problem presented to the waiter is a subset-sum problem, not a knapsack problem.
(A knapsack has a fixed capacity where any solution below (or equal to) the capacity is valid – for subset-sum the sum of a solution has to be exactly equal to the value given, to be valid).
Just for fun I also reproduced a solution in Prolog with constraints enabled. As everybody has pointed out, comparing floats for equality: -5 points on the assignment. Constraining for equality reproduced your [1,0,0,2,0,1] solution quickly and failed to find [7,0,0,0,0,0]. Constraining for target +/- epsilon instead of equality fixed that..
Alan: It’s been a while since I’ve done this stuff, but I think you can realise another fairly simple optimization by sorting the items smallest to largest… it’s at most seven of any one item, so you can start at the beginning of the list trying increasing numbers of the least expensive item with up to seven of each remaining one, but abort the entire branch of the tree once you pass 15.05, since you know that all the remaining items to try are more expensive than the current one.
Also, if five orders of side salad pushes it over, there’s no need to try any more than four orders of wings. So you can keep a tally of how far each previous level got. Anyhow, yeah.
Just on hearsay, COBOL is widely used for real money applications because it has a native BCD (Binary Coded Decimal) type where a nybble is used to store a single decimal digit. Wouldn’t that fix the roundoff errors commonly encountered when using floating point math, since with BCD floats, you could accurately represent the base 10 numbers used for money.
As for those who think IEEE made a requirement that floating point comparisons like this come out true when they should, I’ve tried 2.15 * 7 in elisp (yes, it’s a weird calculator, but it works) and C++ (gcc), and they both fail. In C++, the output library rounds it to 15.05, so the string comparison mentioned above would also work in C++.
poorsod: no, computers cannot do “anything.†In fact they can do almost nothing. All they can do is count from 0 to 1 and no more – just really, really fast.
In any case, to understand why the problem arises, consider what humans mean whey they say 0.625: this means six 1/10ths, two 1/100ths, and five 1/1000ths. Similarly, a computer stores fractions, like everything else, as powers of 2: 0.625 in decimal is 0.101 in binary, and it means one 1/2th and one 1/8th.
As you see, in binary, this fraction is much simple than in decimal (which, of course, is because I started with the binary notation…). The opposite, case, however, is more common: a simple decimal fraction like 0.5 can be very very long (or even infinite) if you try to express it in binary. (Much like 1/3 is infinite if you try to express it in decimal, and binary 0.000000000001 is very complicated in decimal (namely, it’s 0.000244140625).)
So you write 0.5, but the computer sees a long and complicated binary fraction, and the regular precision of fractional numbers (maximum about 80 bits, mostly) may not even be enough to denote that simple decimal fraction exactly.
…And there I go and don’t read the problem clear enough; in everything visible on the screen from the menu, there is one additional $15.05 order, it’s just not in the bounds of the problem…
That said, 0.5 is perfectly simple in binary, but 0.05 is repeating in binary. .00(0011), I believe.
I wrote a quick and dirty recursive C program, found the two solutions and then thought about the fact that this is more naturally done with scripts … ah well
I had the same problem last night with a Python program I used to solve the program. I ended up replacing the equals operator with a simple function that sees if they are ‘close enough’:
(code is at http://files.cibomahto.com/np.py.txt if it gets garbled during the post)
#!/usr/bin/env python
list = 2.15, 2.75, 3.35, 3.55, 4.20, 5.80
goal = 15.05
max = 8
def floatEquals( arga, argb):
if abs(arga – argb)
sense we are posting the solvers…
I still like the one I did here, if only for it’s conciseness:
menu(Result) :- pick(1505, [215, 275, 335, 355, 420, 580,655], Result).
pick(Total, Prices, [X]) :-
member(X,Prices),
Total = X.
pick(Total, Prices, [X|Xs]) :-
member(X,Prices),
N is Total – X,
N > 0,
pick(N,Prices,Xs).
Was it intentional to allow the $6.55 BBQ Sandwich to match a solution?
This is when I realize most of the xkcd readers actually ARE math majors.
I have no in-depth math or programming background.
James: It might be more a case of selective exposure here…
GriffJon:
I think you mean…
Floating point math 3.99999999999999 life!
Hunter:
No, because 4.0 can be precisely represented by floating point numbers, because it’s a power of two. Other numbers than powers of 2 can be precisely represented, I’m just not an FPU, so I don’t know the precise requirements for a number to be precisely reprehensible.
Reprehensible? You mean representable, surely?
/** By Richard Keeme.
* This solution is a brute force solution of trying all permutations and
* selecting the unique ones.
*/
package np;
import java.util.ArrayList;
import java.util.List;
public final class Np {
public static final String[] names = { “Mixed Fruit”, “French Fries”,
“Side Salad”, “Hot Wings”, “Mozzarella Sticks”, “Sampler Plate” };
public static final int prices[] = { 215, 275, 335, 355, 420, 580 };
public static final int TARGET = 1505;
public static int hits = 0;
public static int permutations = 0;
public static List goodSolutions = new ArrayList();
/**
* @param args
*/
public static void main(String[] args) {
System.out
.println(“Np.main() Solutions to xkcd restaurant problem. R. Keene”);
for (int n = 1; n 0) {
System.out.print(“, “);
}
System.out.print(names[idxs[i]]);
}
System.out.println(“]=” + money(sum));
System.out.print(“prices [");
for (int i = 0; i 0) {
System.out.print(", ");
}
System.out.print("" + money(prices[idxs[i]]));
}
System.out.println(“]=” + money(sum));
}
private static void showSet(Permutator p, int sum) {
int[] idxs = p.getIdxs();
System.out.print(“Testing… prices [");
for (int i = 0; i 0) {
System.out.print(", ");
}
System.out.print("" + money(prices[idxs[i]]));
}
System.out.println(“]=” + money(sum));
}
private static String money(int m) {
String s = “” + m;
if (s.length() == 3) {
return s.substring(0, 1) + “.” + s.substring(1, 3);
}
return s.substring(0, 2) + “.” + s.substring(2, 4);
}
}
/**
* Returns successive permutations of N numbers between 0 and maxVal.
*
*/
final class Permutator {
int[] idxs;
int maxVal;
public Permutator(int n, int maxVal) {
super();
idxs = new int[n];
this.maxVal = maxVal;
}
/**
* is is the same elements maybe in different order.
*
* @param is
* @return
*/
public boolean same(int[] is) {
if (is.length != idxs.length) {
return false;
}
int[] a = is.clone();
for (int i = 0; i
There are two solutions.
Sampler Plate, Hot Wings, Hot Wings, Mixed Fruit
and
Mixed Fruit, Mixed Fruit, Mixed Fruit, Mixed Fruit, Mixed Fruit, Mixed Fruit, Mixed Fruit
Interestingly, my program runs in a blink when you test up to 7 items and all permutations. 8 items is still a blink, 10 items is 5 seconds, 11 items is 25 seconds, and so on. It is order squared. Thus restaurants will not be able to expand the appetizer menu until hardware improves.
ok, I’ll post code too. Here’s the non-genericized version cause it’s shorter and sufficiently illustrative. Note that from/2 is just member/2 with reversed arguments– I needed that to be able to use it as a closure in the apply/2 meta-predicate. Aren’t constraints neat? A first reaction is often “where’s the work being done?”
go :-
P = A0*2.15 + A1*2.75 + A2*3.35 + A3*3.55 + A4*4.20 + A5*5.80,
15.05 >= P – 0.01,
15.05 =
Aaag– my post was truncated
Just out of curiosity:
Are there any optimised algorithms for this? I understand the problem is NP-complete, but there certainly are slower and quicker methods to get a solution…
my solution in java, quite more short than the above
yeouw
I prevented the floating point pitfall from the design step
package be.badcode.fun.knapstack;
public class Resolver {
String menuitems[]={“Mixed fruit”,”French fries”,”Side Salad”,
“Hot wings”,”Mozzarella sticks”,”Sampler plate”,”Barbecue”};
int prices[]={215,275,335,355,420,580,655};
int total=1505;
static int maxlevel=7;
void backtrack(int curlevel, int curtotal, int current[]){
int save=current[curlevel];
int newprice;
newprice=curtotal;
while(newprice
aaargh same
pastebin link here
http://pastebin.com/m4598625a
brilliant to see someone bringing the fun of science back to share with the non-scientists. very refreshing
I’ve gotten all my friends hooked on your site.
have a girlfriend?
haha
Mathematica doesn’t have any of these problems with decimals, because it knows how important decimal calculation could be. Also, I think that they guy in the comic should buy 51 barbecue sandwiches and sell 55 sampler plates at menu price.
All those solutions remind me of a “Coding Horror” post :
http://www.codinghorror.com/blog/archives/000804.html
I mean, most of us just can’t resist solving theoretical problems and discussing them ad libitum, though we only reluctantly work on our everyday tasks. Why is that ?
Well, don’t ask me : as soon as I saw this comic I grabbed a notepad and coded a crappy VBScript (!) solution (it took 4s to run, and 40s when not dismissing previously tested solutions in different orders, and a greedy approximation algorithm gave a 14.95$ order, not bad – I need vacation).
kyzentun:
Anything expressible as a less-than-n-digits binary number multiplied by some power of two is exactly representible as a floating-point number.
n is a bit less than the number of bits in the number, to allow for the exponent.
Well, assuming the exponent can be big enough for your number.
Oddly enough, while 4.0 is uniquely representible, if you keep adding 4.0 to a variable, at some point the variable will stop increasing – because that sum is not representible, and gets rounded back down to the nearest representible number – which is what you just added to.
just remember that representing exsactly 4 in a float will instantly loose you the knowledge that it is exsactly 4, all you will now know is that it is 4+/-epsilon.
Man, none of this makes any sense to me (Hi! Medieval Studies major (dropped out)), but man, it’s kind of hot all the same.