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

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

Please log in or register to post a reply.

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

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

@juhnu

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

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

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

@poita

`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….

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 :)

@Bad Sector

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
:lol:. 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.

@Bad Sector

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.

@tbp

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:

‘precision’ will allow you to set the precision of the cout stream you
could do precision(2) to get the corrent number of digits

@juhnu

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

@juhnu

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;”)

My guess:

- write float to stringstream with one digit after the dot
- get rid of the dot in the string
- read integer from stringstream
- …
- profit

Aftermath: i know it’s terrible =)

@.oisyn

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.

- Decide how many decimals you need/want. (eg. 2)
- Round the value according to decided decimal count. ( 0.999 -> 1.00)
- 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.

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.

@poita

`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.

@.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.

Nice :yes: I didn’t think about that last thing you said about the
bordercase. I just discarded rational numbers as a solution because of
the squareroot but as you said, in the cases where I’m having trouble
the squareroot *will* be rational.

I think I’ll right a rational number class before the competition just in case I need it.

Thanks everyone for your input.

- Upcoming Multiplatform Game Program...
- Our first game - looking for feedbacks
- Network Emulation Tool
- Trouble with accessing GLSL array
- Fiction
- Game Programming Patterns: Bytecode
- Interactive WebGL Water Demo
- Skeletal Animation Tutorial with GP...
- Unreal Engine 4
- Microsoft xbox one selling poorly

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:

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:

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