Rename Number.prototype.clz to Math.clz
So we discussed all that when we made that decision. I understand that you disagree but is there any new data that should cause us to reopen an issue that was already discussed and decided at a TC39 meeting?
What if we add a uint64 type, we'd just have Math.clz64 (which is better than have X.clz returning something depending on a type, so you always have to check the type first)
This is a judgment call, I'm with Jason, I think we should revisit. I'm putting it on the TC39 meeting agenda.
To me this sounds as a good idea, I was actually under the impression that it would be under Math until I saw the first ES6 draft featuring clz.
Having it under Math not only seems more consistent to me, but also lets
you do nice things like numbers.map(Math.clz).
On Wed, Jan 15, 2014 at 1:26 PM, Allen Wirfs-Brock <allen at wirfs-brock.com> wrote:
So we discussed all that when we made that decision. I understand that you disagree but is there any new data that should cause us to reopen an issue that was already discussed and decided at a TC39 meeting?
Well, here's one data point. This function, like most Math functions, is particularly useful for systems that compile to JS, like Emscripten. See bugzilla.mozilla.org/show_bug.cgi?id=925123.
Emscripten emits code (roughly) like this:
function program() {
var sin = Math.sin;
... lots of functions that call sin() ...
return main;
}
This kind of code has nice tamper-resistant semantics and (not coincidentally) it will scream on existing JS engines.
If clz is a Math function, Emscripten can just
var clz = Math.clz;
If it's a method, it would have to emit something like:
var clz = Function.prototype.call.bind(Number.prototype.clz);
and hope the JS engines all optimize away the bound method call.
At the risk of putting too many nails in the board...
The rationale seems to propose that (0).clz() === 32, but the hypothetical uint64(0).clz() would return 64. That seems like a bad idea though. It's weird for two zero values to get such different behavior from the same method. It's weird for floating-point numbers to have a clz() method in the first place.
Since these are two different mathematical functions, they should have different names: Math.clz32(zero) would be 32 no matter what type of zero you pass it; the hypothetical Math.clz64(zero) would of course be 64. That way users can focus on the mathematical function being computed, rather than runtime types.
Or maybe: flip the function around so that it returns the number of bits in the binary expansion of the value: Math.bitlen(15) === 4. This is just (32 - CLZ), so it effectively computes the same thing as clz. The advantage is that it extends naturally to integers of any size.
+1. I like this flipping idea by far the best. It can be explained in terms of the number being denoted, without referring to the internal limitations of any particular representation. With this change, I agree it should be a static on Math.
With this flipped idea, let's think through what the proper .bitlen answers are for fractions, negative numbers, NaN, +/- Infinity, and -0.0.
Would Math.bitlen(Number.MAX_SAFE_INTEGER) return 53 or 32?
(If 53, environments trying to emulate 32-bit ints on top of Number could toss in yet another |0 or >>>0)
On 2014/01/16, at 17:40, Jason Orendorff <jason.orendorff at gmail.com> wrote:
At the risk of putting too many nails in the board...
The rationale seems to propose that (0).clz() === 32, but the hypothetical uint64(0).clz() would return 64. That seems like a bad idea though. It's weird for two zero values to get such different behavior from the same method. It's weird for floating-point numbers to have a clz() method in the first place.
Since these are two different mathematical functions, they should have different names: Math.clz32(zero) would be 32 no matter what type of zero you pass it; the hypothetical Math.clz64(zero) would of course be 64. That way users can focus on the mathematical function being computed, rather than runtime types.
Or maybe: flip the function around so that it returns the number of bits in the binary expansion of the value: Math.bitlen(15) === 4. This is just (32 - CLZ), so it effectively computes the same thing as clz. The advantage is that it extends naturally to integers of any size.
What is Math.bitlen(-1) then? Isn’t this just the same problem as before, except it happens for negative numbers instead of positive?
On Thu, Jan 16, 2014 at 12:09 PM, Joshua Bell <jsbell at google.com> wrote:
Would Math.bitlen(Number.MAX_SAFE_INTEGER) return 53 or 32?
Since the point is to make the answer have a mathematical relationship to the number denoted, rather than the limits of a particular representation, 53.
(If 53, environments trying to emulate 32-bit ints on top of Number could toss in yet another |0 or >>>0)
yes.
On Thu, Jan 16, 2014 at 1:12 PM, Jens Nockert <jens at nockert.se> wrote:
What is Math.bitlen(-1) then? Isn’t this just the same problem as before, except it happens for negative numbers instead of positive?
Good question. I don't yet have an opinion. But for a baseline, for all the problem cases (fractions, negative numbers, NaN, +/- Infinity, and -0.0), what would .clz have done?
On Thu, Jan 16, 2014 at 1:12 PM, Jens Nockert <jens at nockert.se> wrote:
What is Math.bitlen(-1) then? Isn’t this just the same problem as before, except it happens for negative numbers instead of positive?
FWIW: Common Lisp has rigorously transparent (that is, you cannot observe the machine word size) bigints and quite a few binary operations defined on them, so it's where I personally would look for precedent on such questions. It doesn't have clz or bitlen per se, but it has these two functions which contain positions on the issue:
integer-length Returns the number of bits needed to represent 'integer' in binary two's-complement format. (Comment: This is equivalent to bitlen + 1 in order to count the sign bit, and is well-defined for negative numbers.)
logcount
Computes and returns the number of bits in the two's-complement binary
representation of 'integer' that are on' orset'. If 'integer' is
negative, the 0 bits are counted; otherwise, the 1 bits are counted.
(If I had guessed without actually reading the docs, though, I would have had logcount rejecting negative numbers.)
Name aside, integer-length seems very sensible. For JS, I propose that it be extended to the remaining problem cases as follows:
f(-0.0) = f(0.0) = 0 f(-Infinity) = f(Infinity) = Infinity f(NaN) = NaN
Why is logcount called "logcount"? As the doc on integer-length makes clear, it has a strong relation to the log-base-2 of the number. logcount does not.
What is logcount used for?
Kevin Reid wrote:
FWIW: Common Lisp has rigorously transparent (that is, you cannot observe the machine word size) bigints and quite a few binary operations defined on them, so it's where I personally would look for precedent on such questions.
(a) we don't have a bignum type yet; (b) we want to JIT to concrete machine types where possible. (b) does not require clz32 vs. clz64 in my view, because of type inference or AOT type-checking (asm.js). But we don't want to require bignums.
On Thu, Jan 16, 2014 at 3:56 PM, Mark S. Miller <erights at google.com> wrote:
What is logcount used for?
I think that's the same thing as "population count", which has a few applications:
On Thu, Jan 16, 2014 at 1:58 PM, Brendan Eich <brendan at mozilla.com> wrote:
(a) we don't have a bignum type yet; (b) we want to JIT to concrete machine types where possible. (b) does not require clz32 vs. clz64 in my view, because of type inference or AOT type-checking (asm.js). But we don't want to require bignums.
Yes, but choices which work for bignum also work for "I am working on 32-bit (or 8-bit or whatever) values which happen to be stored in a larger (53- or 64-bit) field, and the length of the larger field is irrelevant to the task".
On Thu, Jan 16, 2014 at 1:56 PM, Mark S. Miller <erights at google.com> wrote:
Why is logcount called "logcount"? As the doc on integer-length makes clear, it has a strong relation to the log-base-2 of the number. logcount does not.
Common Lisp calls most bitwise functions of integers log<something>,
that's all.
Kevin Reid wrote:
Yes, but choices which work for bignum also work for "I am working on 32-bit (or 8-bit or whatever) values which happen to be stored in a larger (53- or 64-bit) field, and the length of the larger field is irrelevant to the task".
Agreed, for integral types.
I remember the Harbison & Steele C book, lots of Common Lispy names, like population_count() ;-).
On Thu, Jan 16, 2014 at 3:12 PM, Jens Nockert <jens at nockert.se> wrote:
What is Math.bitlen(-1) then? Isn’t this just the same problem as before, except it happens for negative numbers instead of positive?
No opinion.
For the use cases I know of, speed matters: it is desired that this operation compile down to a CLZ or equivalent machine instruction, when the argument is in the range of uint32. I slightly prefer Math.clz32 to Math.bitlen for this reason. It's exactly what it says on the label. People searching for a JS equivalent of CLZ or __builtin_clz() are likely to find it. The specification can start with ToUint32 which already tells us how corner cases should behave.
Jason Orendorff wrote:
No opinion.
Not sure it matters. We could return -1 for any negative number, 0 for 0, and > 0 for positive integral values.
would -0 return -1 too ? I could not resist asking for this, sorry!
On 2014/01/17, at 4:20, Brendan Eich <brendan at mozilla.com> wrote:
Not sure it matters. We could return -1 for any negative number, 0 for 0, and > 0 for positive integral values.
It does matter, this specific issue makes the x86 instruction BSR a lot less useful than it could be. There they set a zero-flag instead of returning a defined value. This is enough of an issue that AMD introduced the LZCNT instruction that instead returns the input size, to mirror what other platforms do1.
When I needed this function the last time (implementing audio codecs in JS) I would have needed that it worked essentially like the bitwise operators, and defined on the resulting 32-bit signed int. We already leak the 32-bitness of those operators, so leaking a 32-bitness on a few related functions wouldn’t be a big issue imho.
On Fri, Jan 17, 2014 at 6:12 AM, Jens Nockert <jens at nockert.se> wrote:
When I needed this function the last time (implementing audio codecs in JS) I would have needed that it worked essentially like the bitwise operators, and defined on the resulting 32-bit signed int.
Then you could write: Math.bitlen(x >>> 0)
That would return 32 if x is a negative 32-bit signed int, because ">>> 0" converts ToUint32.
Yeah, but when would I need to calculate it on a floating-point number?
Allowing that is just confusing when all other bit-oriented operation implicitly does ToInt32.
On Fri, Jan 17, 2014 at 7:07 AM, Jens Nockert <jens at nockert.se> wrote:
Yeah, but when would I need to calculate it on a floating-point number?
No one cares about fractions here; the question is about integer values beyond 0xffffffff. These exist in the "safe integer" range of JS numbers and will exist in future uint64 and bigint types. (Note that the whole point of settling on bitlen, as opposed to clz32, would be future compatibility with such types.)
If you go with a representation-independent 'bitlen', I would suggest returning NaN for any negative number.
This is consistent with a simple mathematical definition:
bitlen(n) := ceil(log_2(n + 1))
(Or, in js: Math.ceil(Math.log(n + 1) / Math.LN2), which potentially has rounding errors, but works for integers up to 2^48.)
Second best preference for me would be to return bitlen(Math.abs(n)).
None of this applies if you opt for a representation-dependent (clz-style) bitlen,
Nick
On Fri, Jan 17, 2014 at 1:12 PM, Nick Krempel <ndkrempel at google.com> wrote:
bitlen(n) := ceil(log_2(n + 1))
Except I think we want bitlen(0) === 0 for consistency with clz.
On H26/01/17, at 20:12, Nick Krempel <ndkrempel at google.com> wrote:
If you go with a representation-independent 'bitlen', I would suggest returning NaN for any negative number.
infinity would make sense for a signed two's complement representation.
On 18 January 2014 06:25, Jason Orendorff <jason.orendorff at gmail.com> wrote:
Except I think we want bitlen(0) === 0 for consistency with clz.
Just noting that this actually works: Math.ceil(Math.log(0 + 1) / Math.LN2) === 0
However: Math.ceil(Math.log(-1 + 1) / Math.LN2) === -Infinity
Not sure how that affects a Negative NaN-cy option :)
Adam Ahmed wrote:
Just noting that this actually works: Math.ceil(Math.log(0 + 1) / Math.LN2) === 0
However: Math.ceil(Math.log(-1 + 1) / Math.LN2) === -Infinity
That's pretty sweet, but then try -2 or -3 or below and you get NaN.
Not sure how that affects a Negative NaN-cy option :)
Heh.
I think we should make sure (per Jason and Jens) that, given type inference or asm.js-style type-checking, we can select a single common machine instruction. After that, we should consider more abstract "prettiness" properties such as the one you show for -1. And given the -Infinity then NaN inconsistency, perhaps NaN wins. But Jens' point about Infinity (bit length in two's complement infinite precision of any negative number) is strangely compelling.
Need to hear from type-inference and asm.js gurus. Cc'ing a few. The issue is, given
Math.bitlen(x)
where x has inferred type int32, what do we need in the way of a guard for negative values? We need something, we cannot use BSR directly without getting 32 for -1.
Whether log(0) is -Infinity or NaN should depend in some sense on what side you approach 0 from (I arbitrarily claim to be approaching it from the left in my formula, to give a NaN result there too).
I feel Math.log(-0) should be NaN in js for that reason, but it is defined to be -Infinity in the standard. Maybe there are industry standards pertaining to floating point transcendental functions that mandate this? Similarly, Math.sqrt(-0) is -0 rather than NaN. Perhaps using the more correct NaN values in these cases have caused more problems than they have solved in practice?
Nick
On 17 January 2014 19:25, Jens Nockert <jens at nockert.se> wrote:
infinity would make sense for a signed two's complement representation.
Yes! You win! +Infinity (not -Infinity) is now my top choice. (The mathematical version of what you said is the 2-adic expansion. For example the 2-adic expansion of -1 is ...1111111 - carrying on infinitely to the left. First google hit: www.cut-the-knot.org/blue/p-adicExpansion.shtml)
Nick Krempel wrote:
Whether log(0) is -Infinity or NaN should depend in some sense on what side you approach 0 from (I arbitrarily claim to be approaching it from the left in my formula, to give a NaN result there too).
I feel Math.log(-0) should be NaN in js for that reason, but it is defined to be -Infinity in the standard. Maybe there are industry standards pertaining to floating point transcendental functions that mandate this? Similarly, Math.sqrt(-0) is -0 rather than NaN. Perhaps using the more correct NaN values in these cases have caused more problems than they have solved in practice?
These cases (log(-0), sqrt(-0)) conform to IEEE 754. See
stackoverflow.com/questions/19232157/square-root-of-negative-zero
msdn.microsoft.com/en-us/library/windows/desktop/cc308050(v=vs.85).aspx
and many others.
The "Signed Zero" section of
docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
is worth reading.
Further reading from Prof. Wm. Kahan:
www.cs.berkeley.edu/~wkahan, www.cs.berkeley.edu/~wkahan/ieee754status
On 18 January 2014 18:16, Brendan Eich <brendan at mozilla.com> wrote:
Nick Krempel wrote:
Whether log(0) is -Infinity or NaN should depend in some sense on what side you approach 0 from (I arbitrarily claim to be approaching it from the left in my formula, to give a NaN result there too).
I feel Math.log(-0) should be NaN in js for that reason, but it is defined to be -Infinity in the standard. Maybe there are industry standards pertaining to floating point transcendental functions that mandate this? Similarly, Math.sqrt(-0) is -0 rather than NaN. Perhaps using the more correct NaN values in these cases have caused more problems than they have solved in practice?
These cases (log(-0), sqrt(-0)) conform to IEEE 754. See
Thanks. Didn't know it covered log.
The "Signed Zero" section of
docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
is worth reading.
Yes, and it supports my case:
"Another example of the use of signed zero concerns underflow and functions that have a discontinuity at 0, such as log. In IEEE arithmetic, it is natural to define log 0 = -∞and log x to be a NaN when x < 0. Suppose that x represents a small negative number that has underflowed to zero. Thanks to signed zero, x will be negative, so log can return a NaN. However, if there were no signed zero, the log function could not distinguish an underflowed negative number from 0, and would therefore have to return -∞."
Further reading from Prof. Wm. Kahan:
www.cs.berkeley.edu/~wkahan, www.cs.berkeley.edu/~wkahan/ieee754status
Also good links. Think I've read most of it already. Kahan's paper on the
correct definitions of transcendental functions along branch cuts mostly relates to the complex-valued versions, but IIRC has sqrt(-0+0i) = +0, not -0 in any case.
Nick
It seems to me that we must have Math.clz perform ToUint32() on its input. Otherwise (if ToInt32() is used), even if the expression is written Math.clz(x >>> 0), asm.js/type-inference won't be able to optimize away the <0 branch since the ToInt32() in the semantics of Math.clz will convert a large unsigned integer argument into a negative integer.
Secondly, I think clz(0) should be 32, not 0:
- for x86's
bsr, since the result is undefined if the input is zero, we need a branch or cmov anyway to deal with zero. - to make up for
bsr's shortcomings, newer x86 chips havelzcnt(which JITs can emit after testing the right cpuid bit), which definesclz(0) == 32. - ARM's
clzalso definesclz(0) == 32.
The only reason not to do this I could imagine is if there was a de facto standard among all x86 chips (such that the JIT could rely on it) to have bsr(0) == 0, but I couldn't find any evidence of this.
Thanks, I just presented this pretty much verbatim, and Math.clz32 it is, by TC39 consensus. ToUint32
Would Math.clz32 still throw a TypeError if the argument is not a number, nor an object with the [[NumberData]] internal slot? Currently all math functions perform ToNumber on their arguments, unlike what Number.prototype.clz is currently specified to do.
Qantas 94 Heavy wrote:
Would Math.clz32 still throw a TypeError if the argument is not a number, nor an object with the [[NumberData]] internal slot? Currently all math functions perform ToNumber on their arguments, unlike what Number.prototype.clz is currently specified to do.
ToUint32 does ToNumber in its first step (people.mozilla.org/~jorendorff/es6-draft.html#sec-touint32).
My bad, should have replied to all. Thanks for clarifying though.
ES6 adds a clz function, but it's a method of Number.prototype.clz rather than Math.clz.
The rationale for this decision is here (search for clz in the page): esdiscuss.org/notes/2013-07-25
Can we reverse this, for users' sake? The pattern in ES1-5 is quite strong: math functions go on the Math object.
The rationale (What if we add a uint64 type?) doesn't seem compelling enough to justify the weirdness of the result: we'll have a single mathematical operation available only as a Number method, and all others available only as Math functions.