number/toUInt and number/toUInt32 behavior

[millermedeiros]

number/toUInt and number/toUInt32 behavior

Note: The algorithm below produces incorrect results for negative floats. I have posted an updated implementation that corrects this error.

Here's an implementation of the ToUint32 algorithm directly from the spec. The accompanying tests reveal that, for all positive values, ToUint32 and the >>> operator produce equivalent results.

function ToUint32(value) {
  // Coerce the value to a number.
  value = +value;
  // Return `+0` if the numeric value is `NaN`, `Infinity`, `-Infinity`, `+0`, or `-0`.
  if (!isFinite(value) || !value) {
    return 0;
  }
  // The algorithm in the spec determines the sign of the number, and multiplies it by the floored
  // absolute value. This is equivalent to simply flooring the original value.
  return modulo(Math.floor(value), Math.pow(2, 32));
}

// The `%` operator and the `modulo` function are not equivalent. The former returns the left-hand
// side of the expression if it is negative (e.g., `-1 % 10` is `-1`; `modulo(-1, 10)` is `9`).
function modulo(left, right) {
  return left - right * Math.floor(left / right);
}

console.assert(ToUint32(15.625) === 15.625 >>> 0);
console.assert(ToUint32(10) === 10 >>> 0);
console.assert(ToUint32(5.5) === 5.5 >>> 0);
console.assert(ToUint32(0) === 0 >>> 0);
console.assert(ToUint32(-5) === -5 >>> 0);
console.assert(ToUint32(-10) === -10 >>> 0);
console.assert(ToUint32(-1e3) === -1e3 >>> 0);

The implementations only differ with respect to negative floats: ToUint32(-1.5) == Math.pow(2, 32) - 2, while -1.5 >>> 0 == Math.pow(2, 32) - 1. Likewise, ToUint32(-15.625) == Math.pow(2, 32) - 16, while -15.625 >>> 0 == Math.pow(2, 32) - 15.

Edit: I believe that this is due to the truncation that occurs when using floats with bitwise operators: whereas Math.floor floors a value, bitwise operations simply truncate it. This is why, for example, the ~~ optimization for flooring numbers produces inconsistent results when used with negative floats: ~~-2.1 == -2, but Math.floor(-2.1) == -3. See this Stack Overflow answer for additional details.

[millermedeiros]

also should the toUInt module be renamed to toUInt31? (since it is "31-bit")

[millermedeiros]

thx, so from now on I will start using the >>> (since it is closer to what most implementations that I could find do)...

~~ works like Math.floor for positives and Math.ceil for negatives, usually that's the behavior that I would expect (I usually just want to truncate the value).

[jdalton]

@kitcambridge I didn't see the formula for modulo defined.

The notation “x modulo y” (y must be finite and nonzero) computes a value k of the same sign as y (or zero) such that abs(k) < abs(y) and x−k = q × y for some integer q.

The mathematical function floor(x) yields the largest integer (closest to positive infinity) that is not larger than x.

Curious how you got left - right * Math.floor(left / right); out of that.

[].slice.call({ length: -4294967294.625 }).length; // 2 in v8, opera 12, ff8
-4294967294.625 >>> 0; // 2
ToUint32(-4294967294.625); // 1

@jdalton It's the definition of the modulo operation. dividend - divisor * int(quotient).

Edit: I just realized that, in Java and C++, explicitly casting a value to an integer truncates it. If the quotient is truncated, rather than floored, ToUint32 will produce results consistent with the >>> operator.

[jdalton]

@kitcambridge I think you took the

In some compilers, the modulo operation is implemented as mod(a, n) = a - n * floor(a / n). For example, mod(7, 3) = 7 - 3 * floor(7 / 3) = 7 - 3 * floor(2.33) = 7 - 3 * 2 = 7 - 6 = 1.

part. Anyway the formula and result don't line up with browser implementations so something is up.

@jdalton Yes; we also covered it in class. I tried applying the Java algorithm that we formulated to JavaScript, but Java uses truncation, not flooring: a - n * (int) (a / n). My JavaScript implementation is incorrect.

The following implementation corrects my conflation of truncation and flooring. The tests reveal that the >>> operator produces results identical to ToUint32 for negative and positive floats. I apologize for my egregious error.

function ToUint32(value) {
  // Coerce the value to a number.
  value = +value;
  // Return `+0` if the numeric value is `NaN`, `Infinity`, `-Infinity`, `+0`, or `-0`.
  if (!isFinite(value) || !value) {
    return 0;
  }
  // The `floor` function in the specification differs from `Math.floor` in that the former rounds
  // toward zero (alternatively known as truncation). In the spec, the routine is
  // `sign * floor(abs(value))`; this implementation avoids the intermediate step of determining the
  // sign and truncating the absolute value by delegating to a `modulo` function that computes the
  // remainder using standard remainder division, rather than truncating division. The following
  // line could be rewritten as follows for consistency with the spec:
  //   return modulo((value < 0 ? -1 : 1) * Math.floor(Math.abs(value)), Math.pow(2, 32));
  return modulo(Math[value < 0 ? "ceil" : "floor"](value), Math.pow(2, 32));
}

// The `modulo` function is a modified implementation of the `%` operator. This algorithm uses the
// formula `remainder = dividend - divisor * quotient`; the `%` operator uses a truncating division.
// See section 11.5.3.
function modulo(dividend, divisor) {
  return dividend - divisor * Math.floor(dividend / divisor);
}

console.assert(ToUint32(15.625) == 15.625 >>> 0);
console.assert(ToUint32(10) == 10 >>> 0);
console.assert(ToUint32(5.5) == 5.5 >>> 0);
console.assert(ToUint32(0) == 0 >>> 0);
console.assert(ToUint32(-1.5) == -1.5 >>> 0);
console.assert(ToUint32(-5) == -5 >>> 0);
console.assert(ToUint32(-10) == -10 >>> 0);
console.assert(ToUint32(-15.625) == -15.625 >>> 0);
console.assert(ToUint32(-1e3) == -1e3 >>> 0);

[jdalton]

@kitcambridge + @millermedeiros Wow, seriously thank you for digging into this (on a holiday even!). I will try to digest this more after the weekend 🍺 👍