Using a float in Javascript in a hash function

1

I Have a hash function like this.

class Hash {
  static rotate (x, b) {
    return (x << b) ^ (x >> (32-b));
  }
  static pcg (a) {
    let b = a;
    for (let i = 0; i < 3; i++) {
      a = Hash.rotate((a^0xcafebabe) + (b^0xfaceb00c), 23);
      b = Hash.rotate((a^0xdeadbeef) + (b^0x8badf00d), 5);
    }
    return a^b;
  }
}
// source Adam Smith: https://groups.google.com/forum/#!msg/proceduralcontent/AuvxuA1xqmE/T8t88r2rfUcJ

I use it like this.

console.log(Hash.pcg(116)); // Output: -191955715

As long as I send an integer in, I get an integer out. Now here comes the problem. If I have a floating number as input, rounding will happen. The number Hash.pcg(1.1) and Hash.pcg(1.2) will yield the same. I want different inputs to yield different results. A possible solution could be to multiply the input so the decimal is not rounded down, but is there a more elegant and flexible solution to this?

Is there a way to convert a floating point number to a unique integer? Each floating point number would result in a different integer number.

Performance is important.

javascript
floating-point
type-conversion
integer
hash-function

1 Answer

1

This isn't quite an answer, but I was running out of room to make it a comment. :)

You'll hit a problem with integers outside of the 32-bit range as well as with non-integer values.

JavaScript handles all numbers as 64-bit floating point. This gives you exact integers over the range -9007199254740991 to 9007199254740991 (±(2^53 - 1)), but the bit-wise operators used in your hash algorithm (^, <<, >>) only work in a 32-bit range.

Since there are far more non-integer numbers possible than integers, no one-to-one mapping is possible with ordinary numbers. You could work something out with BigInts, but that will likely lead to comparatively much slower performance.

If you're willing to deal with the performance hit, your can use JavaScript buffer functions to get at the actual bits of a floating point number. (I'd say more now about how to do that, but I've got to run!)

Edit... back from dinner...

You can convert JavaScript's standard number type, which is 64-bit floating point, to a BigInt like this:

let dv = new DataView(new ArrayBuffer(8));
dv.setFloat64(0, Math.PI);
console.log(dv.getFloat64(0), dv.getBigInt64(0), dv.getBigInt64(0).toString(16).toUpperCase())

The output from this is:

3.141592653589793 4614256656552045848n "400921FB54442D18"

The first item shows that the number was properly stored as byte array, the second shows the BigInt created from the same bits, and the last is the same BigInt over again, but in hex to better show the floating point data format.

Once you've converted a number like this to a BigInt (which is not the same numeric value, but it is the same string of bits) every possible value of number will be uniquely represented.

The same bit-wise operators you used in your algorithm above will work with BigInts, but without the 32-bit limitation. I'm guessing that for best results you'd want to change the 32 in your code to 64, and use 16-digit (instead of 8-digit) hex constants as hash keys.

answered on Stack Overflow Jul 20, 2019 by kshetline • edited Jul 21, 2019 by kshetline

User contributions licensed under CC BY-SA 3.0