Problems when comparing doubles

  • Thread starter Thread starter Guest
  • Start date Start date
G

Guest

Hello everyone,

I am having some issues with what should be an insanely simple problem.
Basically, I'm working on an implementation of the TSP algorithm (I have a
static set of 5 locations, so I'm just brute forcing my way through it), and
during execution I build a list of 120 potential distances to be travelled,
stored in an array of type double. I then have another function which
traverses this array and locates the position of the minimum value. The
problem is that it doesn't work as it should. Below is my "find minimum"
algorithm:

for(int m=0; m<input.Length; m++)
{
if(input[m] < min)
{
min=input[m];
pos = m;
}
}

with input being the array of doubles. It's fairly obvious what should
happen in theory. In practice, however this causes issues. I generate the
paths to be used in my algorithm randomly, as i kind of precursor to a faster
algorithm I am thinking of implementing, so when I recalculate the route, the
position of the minimum could be different, while the actual value of the
minimum is still the same. However, the code occasionally returns a value
that is greater than the minimum! THe most frequent minimum value it
retreives is 81.4, but it will at times return 83.2, even if 81.4 is still in
the list. At first I thought that this was a problem with the
behind-the-scenes conversion of double-precision numbers, but I compared the
difference against an epsilon and still encountered the problem.

Does anyone have any ideas why this apparently straightforward algorithm is
so frustratingly broken?

Thanks for your time!

Matt Billock
 
<=?Utf-8?B?TWF0dCBCaWxsb2Nr?= <Matt
I am having some issues with what should be an insanely simple problem.
Basically, I'm working on an implementation of the TSP algorithm (I have a
static set of 5 locations, so I'm just brute forcing my way through it), and
during execution I build a list of 120 potential distances to be travelled,
stored in an array of type double. I then have another function which
traverses this array and locates the position of the minimum value. The
problem is that it doesn't work as it should. Below is my "find minimum"
algorithm:

for(int m=0; m<input.Length; m++)
{
if(input[m] < min)
{
min=input[m];
pos = m;
}
}

with input being the array of doubles. It's fairly obvious what should
happen in theory. In practice, however this causes issues. I generate the
paths to be used in my algorithm randomly, as i kind of precursor to a faster
algorithm I am thinking of implementing, so when I recalculate the route, the
position of the minimum could be different, while the actual value of the
minimum is still the same. However, the code occasionally returns a value
that is greater than the minimum! THe most frequent minimum value it
retreives is 81.4, but it will at times return 83.2, even if 81.4 is still in
the list. At first I thought that this was a problem with the
behind-the-scenes conversion of double-precision numbers, but I compared the
difference against an epsilon and still encountered the problem.

Does anyone have any ideas why this apparently straightforward algorithm is
so frustratingly broken?
Click to expand...

Looks fine to me. How sure are you that the minimum is genuinely in the
list?

Could you post a short but complete program which demonstrates the
problem?

See http://www.pobox.com/~skeet/csharp/complete.html for details of
what I mean by that.
 
Jon,

Thanks for the reply! The way I am sure that the minimum is in the list is
that I have a GUI that outputs the minimum to one pane, and the list of
values to another (for debugging purposes), so when the program produces an
errant value I manually scan through the list until I see a value that is
less than the result.

I wrote a short but complete program that represents the situation, but it
does not reproduce the error. In fact, it would appear that the only code
that can produce the error is my project code. My project code connects to
Mappoint web service to obtain values (which can sometimes be slightly
randomized), populating an array with those, then calculating the distances.
One "solution" that i came up with was to sleep the main thread after that
call to Mappoint for like 20 seconds (if I only sleep it for two, then it
produces the wrong result). I noticed this weird thing while watching the
output window in VS 2003 - the wrong value wouldn't occur until "Thread
noname" exited, so I just had my main thread wait a suitable amount of time
for that thread to finish. Is it common for web service calls to spawn
threads?

THanks for the help!

Matt Billock



Jon Skeet said:
<=?Utf-8?B?TWF0dCBCaWxsb2Nr?= <Matt
I am having some issues with what should be an insanely simple problem.
Basically, I'm working on an implementation of the TSP algorithm (I have a
static set of 5 locations, so I'm just brute forcing my way through it), and
during execution I build a list of 120 potential distances to be travelled,
stored in an array of type double. I then have another function which
traverses this array and locates the position of the minimum value. The
problem is that it doesn't work as it should. Below is my "find minimum"
algorithm:

for(int m=0; m<input.Length; m++)
{
if(input[m] < min)
{
min=input[m];
pos = m;
}
}

with input being the array of doubles. It's fairly obvious what should
happen in theory. In practice, however this causes issues. I generate the
paths to be used in my algorithm randomly, as i kind of precursor to a faster
algorithm I am thinking of implementing, so when I recalculate the route, the
position of the minimum could be different, while the actual value of the
minimum is still the same. However, the code occasionally returns a value
that is greater than the minimum! THe most frequent minimum value it
retreives is 81.4, but it will at times return 83.2, even if 81.4 is still in
the list. At first I thought that this was a problem with the
behind-the-scenes conversion of double-precision numbers, but I compared the
difference against an epsilon and still encountered the problem.

Does anyone have any ideas why this apparently straightforward algorithm is
so frustratingly broken?
Click to expand...

Looks fine to me. How sure are you that the minimum is genuinely in the
list?

Could you post a short but complete program which demonstrates the
problem?

See http://www.pobox.com/~skeet/csharp/complete.html for details of
what I mean by that.
Click to expand...
 
Matt Billock said:
Thanks for the reply! The way I am sure that the minimum is in the list is
that I have a GUI that outputs the minimum to one pane, and the list of
values to another (for debugging purposes), so when the program produces an
errant value I manually scan through the list until I see a value that is
less than the result.

I wrote a short but complete program that represents the situation, but it
does not reproduce the error. In fact, it would appear that the only code
that can produce the error is my project code. My project code connects to
Mappoint web service to obtain values (which can sometimes be slightly
randomized), populating an array with those, then calculating the distances.
One "solution" that i came up with was to sleep the main thread after that
call to Mappoint for like 20 seconds (if I only sleep it for two, then it
produces the wrong result). I noticed this weird thing while watching the
output window in VS 2003 - the wrong value wouldn't occur until "Thread
noname" exited, so I just had my main thread wait a suitable amount of time
for that thread to finish.
Click to expand...

Ah - perhaps you were somehow going through the list before it had
finished being populated?
Is it common for web service calls to spawn threads?
Click to expand...

Sort of. Web services usually use HTTP, which ends up using the thread
pool, so it may well be a thread pool thread you're seeing. (I'm not
quite sure under what circumstances you see it in the debugger.)

Are you using the web service synchronously or asynchronously?

Does your short program also use MapPoint? Is it possible to easily use
MapPoint from a little program, or does it take a lot of setting up?
 
Are you using the web service synchronously or asynchronously?

I was using it synchronously - I ported it over ot asynchronous and it
helped to clear things up a bit, as well. THanks also for the info on web
services and threads!
Does your short program also use MapPoint? Is it possible to easily use
MapPoint from a little program, or does it take a lot of setting up?
Click to expand...

My short program does not use mappoint. Mappoint requires 20-40 lines of set
up code, and since I am only able to use the staging site at this point it
also has a significant amount of latency (I'm implementing the TSP, but most
of my running time comes from mappoint :-) )

Thanks again!

Matt Billock



Jon Skeet said:
Ah - perhaps you were somehow going through the list before it had
finished being populated?


Sort of. Web services usually use HTTP, which ends up using the thread
pool, so it may well be a thread pool thread you're seeing. (I'm not
quite sure under what circumstances you see it in the debugger.)
Click to expand...
 
Back
Top