Search code examples
javascriptieee-754

Getting the significant half of a Number

I'm trying to break a number with value less than or equal to Number.MAX_SAFE_INTEGER into two 32 bit uint values.

My first thought on getting the high value was simply value >>> 32 but this first converts value into a 32b uint and thus the result is 0.

Another thought was to

var high = Number(BigInt(value) >> 32n);

however, going BigInt is relatively slow and I'd like to avoid that if possible

Then I tried Math.floor(value / 2 ** 32) which is way quicker than BigInt and seems accurate but I need a guarantee that it is accurate. Is there any chance of inaccuracy there if the value is between 2 ** 32 and Number.MAX_SAFE_INTEGER? It is a floating point calculation so I am suspicious.

Any other quick ways to get the high value of a 53b integer?

EDIT: If you have a REALLY fast computer, the third approach can be tested

for (let v = 0, high = 0; high <= 2 ** 21; high++) {
    for (let low = 0; low < 2 ** 32; low++) {
        if (Math.trunc(v++ / 2 ** 32) != high) throw "Error at " + v;
    }
}

On my laptop this would take 6 and half years.

Solution

  • Extracting the Bits

    Given that value is an integer not exceeding Number.MAX_SAFE_INTEGER (253−1) in magnitude, then the low 32 bits of the binary numeral for value can be obtained with:

    value % 4294967296

    and the high bits can be obtained with:

    Math.trunc(value / 4294967296)

    (4,294,967,296 is 232. As I do not use JavaScript much, I am not expressing an opinion on the best way to write this in source code. Certainly 4294967296 is correct, but it does not connote the fact that it is 232. (1<<32) might be an option.)

    Note that the results obtained this way will be positive (or zero) if value is positive and negative if value is negative. If something different is wanted when value is negative, some adjustment must be made.

    Justification

    JavaScript is an implementation of ECMAScript. For references here, I use the 2020 specification of ECMA-262.

    The % operator on the Number type provides the Number::remainder operation (6.1.6, Table 2), which is specified in 6.1.6.1.6. For the cases at hand (finite dividend and divisor, with divisor non-zero):

    … the floating-point remainder r from a dividend n and a divisor d is defined by the mathematical relation r = n - (d × q) where q is an integer that is negative only if n/d is negative and positive only if n/d is positive, and whose magnitude is as large as possible without exceeding the magnitude of the true mathematical quotient of n and d. r is computed and rounded to the nearest representable value using IEEE 754-2019 roundTiesToEven mode.

    The text about rounding is superfluous for the remainder operation. Since r cannot be larger in magnitude than the smaller of n or d, it is represented in the Number format at least as finely as each, so the Number format is capable of representing r exactly.

    So value % 4294967296 gives us the low 32 bits of value exactly.

    In Math.trunc(value / 4294967296), the division is by a power of two. In the Number format, value is represented as f•2e, for some significand f (here including the sign) and some exponent e. Then the mathematical result of value / 4294967296 is f•2e−32. Since value is an integer, e is far from the lower exponent bound of the Number format (−1022), and e−32 is also far from it, so no underflow occurs. That means f•2e−32 is exactly representable, so there is no rounding error in computing value / 4294967296. Then Math.trunc takes the integer portion of this, yielding the high bits of value with no error.