2

Given an integer I would like to produce a unique floating point number in the interval [0,1]. (this number will be used as id). The problem I found with all functions I have thought about, is that they encounter duplicates before running out of integer values. For example if f(a:int):float = 0.a then f(16000) = 0.16 and f(16001) = 0.16001. But since it is floating point, 0.16 and 0.16001 may be represented the same. In other words, I need a function that produce not only unique numbers, but also numbers that are represented uniquely (at least forthe C++ integer domain).

I know the answer is dependent on the size of integer and floating point in a specific environment, but if you can give an example for specific sizes it will still be helpful.

1

6 Answers 6

8

As someone else pointed out you can simply cast an int to a float of the same size to get a unique float (with some post-filtering for NaN and -0 and Inf). However, that will not meet your requirement of being in [0,1]. In fact, you can use that relation to show that there are not enough floats in [0,1] to represent the set of integers. If you use double then the mantissa is easily large enough for a 32-bit int and an expression like I / (double)INT_MAX should be sufficient (obviously allow for unsignedness if you need to).

5
  • 2
    +1 for mentioning double mantissa. People usually forget just how impecise floats really are :)
    – Fiktik
    Jan 1, 2011 at 20:36
  • Just casting to float won't work, for example (float)1000000000 == (Float)1000000001 if both int and float are four byte.
    – sth
    Jan 1, 2011 at 20:43
  • Sorry, by cast I mean *((float *)&some_int) -- reinterpreting the 32 bits of integer as 32 bits of float. Jan 1, 2011 at 20:44
  • 3
    That's called "type-punning".
    – caf
    Jan 2, 2011 at 1:03
  • @Fiktik - Floats are not more imprecise than doubles, ints or Decimals. They are just what they are, and when used, one need to consider their adequateness to the task. For one, floats are 2x more economical than doubles when it comes to storage space.
    – ysap
    Jan 4, 2011 at 16:17
6

If 23 bits are enough, you could build a float from int n like this:

float f;
*((__int32*)&f) = (0x7E<<23) | (n & 0x7FFFFF); // exponent=0x7E-0x7F=-1, fraction=n

It will map integers [0, 2^23-1] into floats [0.5, 1.0) according to the IEEE floating point standard.

If 23 bits are not enough, you have a solution at the link that you cited yourself. There are some other important notes, by the way, be sure to understand all the limitations.

1

use 1/(float)n it's a good function for distribution, and if n is zero set it 0.

4
  • Warning: breaks if n is zero.
    – moinudin
    Jan 1, 2011 at 20:37
  • I assume OP says about Natural numbers Jan 1, 2011 at 20:38
  • 2
    That isn't unique when using floats, for example 1/(float)1000000000 == 1/(float)999999999 for four byte floats.
    – sth
    Jan 1, 2011 at 20:44
  • @sth, Sure it's not unique and you can't suggest any unique answer within [0-1] by float limitation, I just provide a sample with good unique values not best one. Jan 1, 2011 at 20:50
1

This is just like the problem of hashing functions and strings. Given that the size of the floating point precision is smaller than that supported by an int type, you're inevitably going to have collisions.

The mathematically correct way is to go for:

f(x) = 0 where x = 0; f(x) = 1/x where x > 0 and x < limit (limit could be 10000000000, depending on your platform's float sizes)

Otherwise you're trying to fit in more values than you can, which is impossible.

Alternatively, (since you're dealing with graphics), if you want to cater for the whole range of integers, and you could live with rounding 2 close integers to the same value, you could divide the value by 2 (or 3 or by how many you want) to scale down to fit in the whole int range required. Dividing by 2 would double the range supported.

So 16000 and 16001 would both end up with 1/8000.

I guess it depends on your situation, but you can't fit 1million people in a stadium of 500,000 seats, and expect everyone to have a unique seat number.. you'll have collisions.

0

Just cast the integer to a float, assuming they are the same size this will produce an unique float for every integer.

int id = 16;    
float f_id = (float) id;

EDIT: I just read that you'd like the floats to be in [0, 1] range - that would considerably reduce number of possible ids, probably it's best just to use the integer as an id, not the float that is dependent on in-memory representation as you pointed out.

3
  • 5
    your code is equivalent with float f_id = 16 ... and no, it will not produce a unique float for every integer, because 32-bit integer has 32-bit precision, while 32-bit float only has 24-bit precision
    – Fiktik
    Jan 1, 2011 at 20:32
  • Seriously, why two upvotes? This doesn't even fit the clearly stated requirements of the question (between 0 and 1), and the statement that any given int will create a unique float is just plain wrong.
    – EboMike
    Jan 1, 2011 at 21:06
  • @Fiktik - the precision of floats is more than 24-bit. It is actually closer to 32-bit. The only exceptions are NaN's, Inf's and maybe denormals. However, it is not enough for covering the 32 bit integer space anyways.
    – ysap
    Jan 4, 2011 at 16:21
0

When an integer value is represented by 32 bits and a float value is represented by 32 bits, then it is obviously impossible to have every possible integer map to a unique float. The simple solution is to use a double for the ID or a short for the value.

The key is to use a floating point type for which the significand has more bits than the integer type.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.