20 replies to this topic

[poita]

I'm doing a computing competition at my university and I'm having a little trouble with casting floats to ints with accuracy. For example, one question essentially asks us to calculate the distance between two co-ordinates then divide it by 0.1 and round down to the nearest integer. Seems simple enough but casting the floats to ints loses some precision. Consider this code:

float dis = calc_distance(a,b);

int answer = (int)(dis * 10);

std::cout << dis << ", " << answer << std::endl;

Now this code seems fine but occasionally gives output similar to the following:

2.1, 20

Obviously the 20 should be 21 and this is the problem. I've tried chaging the code to:

float dis = calc_distance(a,b);

int answer = (int)(dis * 10.0000001);

std::cout << dis << ", " << answer << std::endl;

This allows for a small amount of rounding error for the floats and solves almost all the problems but I still get the rare case where it doesn't work.

The competition requires that your answers are perfect so a difference in 1 in the answer will result in a mark of 0. Does anyone have any concrete ways of converting floats to ints accurately?

Thanks in advance

[juhnu]

Wouldn't it be considered as cheating if you asked solutions here?

However.. (int) does truncate a float instead of rounding it to nearest.

[poita]

juhnu said:

Wouldn't it be considered as cheating if you asked solutions here?

However.. (int) does truncate a float instead of rounding it to nearest.

The competition isn't for a couple of weeks. This was just one of the practice questions that I couldn't do because of this floating point precision. The actual question was to do with finding minimum spanning trees in a graph, this was just a presentation part which I thought would be rather trivial compared to the 'actual' problem.

Consider this code:

float f;

cin >> f;

cout << (int)(f*10) << endl;

Try entering 2.1 as f. You'll notice that the output is 20 and not 21. I know it's because the result of f*10 will end up as something like 20.9999999 instead of 21 but the question is; how can I get this to output 21?

[Reedbeta]

Try adding 0.5 to the floating point number before converting to int. The truncation will cause it to be rounded to the correct value. For instance your 20.9 will become 21.4 and be truncated down to 21. This is a pretty standard trick :yes:

[poita]

Reedbeta said:

Try adding 0.5 to the floating point number before converting to int. The truncation will cause it to be rounded to the correct value. For instance your 20.9 will become 21.4 and be truncated down to 21. This is a pretty standard trick :yes:

The question requires it to be rounded down not rounded. Truncating is what I want, it's just that floating point math doesn't give me the right number to truncate. So if the actual value is (should be) 20.9 then I want 20 as the output. The problem is that when you do 2.1 * 10 it comes out as 20.99999 instead of 21 and then the truncation will give me 20 instead of 21.

The problem I guess is not the rounding/truncating more the floating point math being a little off causing the truncation to be wrong.

btw, I knew about the 0.5 trick :happy:

[Reedbeta]

Hmm. I think the problem as you have stated it is a bit ill-conditioned. At what point do you want there to be a cutoff? Floating point math isn't going to be exact, so how much of a margin of error do you want to allow? I would suggest adding some epsilon to the numbers. Or, you could write a rational number class for exact math within the range of integer numerators and denominators.

[poita]

Reedbeta said:

Hmm. I think the problem as you have stated it is a bit ill-conditioned. At what point do you want there to be a cutoff? Floating point math isn't going to be exact, so how much of a margin of error do you want to allow? I would suggest adding some epsilon to the numbers. Or, you could write a rational number class for exact math within the range of integer numerators and denominators.

Well the problem you see is that we don't know how precise they need to be. I'll try and summarise that paricular question:

You're given a list of decimal coordinates from and input text file. The task is to find the minimum spanning tree between those points with the weight of each edge equal to the distance between the points. Your ouput is to be a single number giving the total length of the tree in units of 0.1 with each edge length rounded down.

So an input file could look like this:
1.0 2.0
1.5 1.5
2.3 3.6

We're not actually shown the input file(s) but instead just shown some sample data that was like the one above. In the actual file there could be an arbitrary number of digits after the decimal point so you see we don't actually know how precise it must be. In any case, once you use Pythagoras' theorem to find the distances you'll probably end up with some nasty irrational numbers.

I tried multiplying the numbers by 10.000001 in an effort to try and stop the numbers from going just under and it worked for most cases except there was one case were it didn't work. I tried different epsilons but they either made it worse or just the same.

I considered making a fraction data type as you suggested but once I get the square root it will just become irrational so it wouldn't help.

:surrender

[Bad Sector]

poita said:

float dis = calc_distance(a,b);

int answer = (int)(dis * 10);

std::cout << dis << ", " << answer << std::endl;

Shouldn't the second line be:

int answer = (int)(dis * 10.0f);

instead, so both operands are floats?

I'm not sure when the compiler converts a float to an int (personally, for clarity and just for being on the safe side i always use floats for floating point operations and the ".0f" postfix for floating point numbers :-)). However your example makes me think that the compiler converts the "dis" to an integer and then it multiplies it with 10 (using a plain "10" in C++ implies "int" - you need to use the dot and "f" for float, or dot without "f" for double).

Again, i'm not sure. I never formally read any C++ book or reference. I just empirically learned the language....

[poita]

I'm pretty sure that when you use two different data types like that eg. int*float or float*double etc. then it converts them to the highest precision type, so the int will get converted to a float and a float would get converted to a double.

In any case, it still doesn't work :)

[.oisyn]

Bad Sector said:

Again, i'm not sure. I never formally read any C++ book or reference. I just empirically learned the language....

Then maybe you shouldn't give such advice as you're just plain wrong . As poita pointed out, primitives will get convered using the following chain: int -> long -> float -> double. Char and short types will first be promoted to int before doing any calculations.

Note that this isn't necessarily the "highest precision type" as a typical 32 bits int holds more precision than a single precision float (which has only 24 bits of precision) . Same goes for a 64 bits long (or long long) vs. double.

[tbp]

Bad Sector said:

I'm not sure when the compiler converts a float to an int (personally, for clarity and just for being on the safe side i always use floats for floating point operations and the ".0f" postfix for floating point numbers :-)).

As other said, it's a matter of knowing about promotion rules.
Plus that '0' is redundant in your postfix, e.g. '1.f', '.1f'.
And a single precision IEEE754 fp can exactly represent any integer up to 1<<24, and then powers of 2.
On the other hand, it's really a bad idea to use .1f or multiples as, say, an increment as it cannot be exactly represented.

Back to the original question, when i see "The competition requires that your answers are perfect" and fp in the same sentence my advice would be to stop coding, get a lawyer, sue them and claim the prize. In that case, the lawyer doesn't even have to be good.

[poita]

tbp said:

my advice would be to stop coding, get a lawyer, sue them and claim the prize. In that case, the lawyer doesn't even have to be good.

Hahaha, my thoughts exactly. I did complain very loudly when my program was tested with hundreds of different inputs only to find that my answer was off by 1 in one of the questions. Clearly my minimum spanning tree algorithm was correct and the stupid @#&#$! floats were costing me the mark. The most annoying thing is that you either get 100% or 0% so because of a very small rounding error I got no credit. :angry:

[juhnu]

Well, why do you think it's an error? If they say you must truncate results, then something like 0.9999999999999 truncated down to zero is _the correct_ answer. If this is not what they want, they have certainly ill-defined the problem as reedbeta said.

[dave_]

'ceil' and 'floor' do rounding up and down
'precision' will allow you to set the precision of the cout stream you could do precision(2) to get the corrent number of digits

[.oisyn]

juhnu said:

Well, why do you think it's an error? If they say you must truncate results, then something like 0.9999999999999 truncated down to zero is _the correct_ answer. If this is not what they want, they have certainly ill-defined the problem as reedbeta said.

The point is that 0.9999999999999 wasn't the correct answer in the first place. It should have been 1.000000000000

[poita]

juhnu said:

Well, why do you think it's an error? If they say you must truncate results, then something like 0.9999999999999 truncated down to zero is _the correct_ answer. If this is not what they want, they have certainly ill-defined the problem as reedbeta said.

As .oisyn said, 0.99999 isn't the correct input, it should've been 1.00000 and then the correct answer should be 1.

To illustrate the point:

float f=2.1;

cout << (int)(f*10) << endl; // Prints 20!

If you can find any way of making this print 21 instead of 20 then let me know (Don't you dare say "cout << 21 << endl;")

[bramz]

My guess:

1. write float to stringstream with one digit after the dot
2. get rid of the dot in the string
3. read integer from stringstream
4. ...
5. profit

Aftermath: i know it's terrible =)

[juhnu]

.oisyn said:

The point is that 0.9999999999999 wasn't the correct answer in the first place. It should have been 1.000000000000 :)

And should 0.9 be 1.0 too? You can't really tell if it's an infinite series or not so one should decide wanted precision at first. 0.99999 can be rounded to 1.0 only when significant decimal count is known.

1. Decide how many decimals you need/want. (eg. 2)
2. Round the value according to decided decimal count. ( 0.999 -> 1.00)
3. truncate it :) (1.00 -> 1)

I guess this could be done by using the maximum precision by using some bit-trickery and getting out the exponent of the floating point representation of a value and adding 1eExponent to that value then.

[.oisyn]

I don't think the approach should be to work with rounded numbers, but rather with exact numbers. The input are digits from text so you have finite precision, perfectly representable by rational numbers. The problem was square roots were hard to do on rational numbers. But converting it to float will not be a problem if the square root is the last calculation you'll do, as whole numbers can be represented exactly by floats and doubles (well, as long as their precision is within respectively 24 and 53 bits) - you'll throw away the bits after the decimal dot anyway.

trunc(sqrt(x) / 0.1) = trunc(sqrt(x) / sqrt(0.01)) = trunc(sqrt(x / 0.01))

In your example, if the 2.1 was the result of squarerooting 4.41 (also unrepresentable by float), you would avoid the problem if you have 4.41 represented as a rational number: 441/100. Dividing by 0.01 gives the rational number 441. The square root of 441.f is 21.f. Truncating will reveal 21.

You'll never get into trouble because the bordercase lies on the whole number. But if the result of a squareroot is a whole number, it's square is also a whole number and thus representable by a float or double.

[tbp]

poita said:

float f=2.1;
cout << (int)(f*10) << endl; // Prints 20!

If you can find any way of making this print 21 instead of 20 then let me know (Don't you dare say "cout << 21 << endl;")

Abracadabra!

struct evil_t {
	float f;
	evil_t(const float a): f(a) {}
	float operator *(const evil_t rhs) const { return f*rhs.f + .5f; }
};
#define float evil_t

float f=2.1; 
std::cout << (int)(f*10) << std::endl; // Prints 20!

Me? A cheater?
Anyway the right anwser was and always is, 42.