Open js-choi opened 2 years ago
I presented a brief update presentation about this issue to the Committee at the October plenary today.
@waldemarhorwat expressed continued confusion over other representatives’ opposition to BigInt sqrt
without specific mathematical use cases. There was talk about specific mathematical use cases possibly being an excessive burden that other BigInt operations like -
or /
were not subjected to.
@bakkot also voiced “strong” support for BigInt sqrt
on the TC39 Delegates Matrix channel during the update.
I tentatively plan to add back BigInt sqrt
and cbrt
back to this proposal before presenting for Stage 2 in a few months, barring signals from other representatives that they would hard block Stage 2 over this issue.
I wrote up an implementation of BigInt sqrt
and cbrt
that computes exact square or cube roots (truncated towards zero to an integer) of BigInts, using O(log(log(n)) BigInt operations. The implementation cost is negligible, taking only a few lines of code.
I'm also enclosing a mathematical proof that this implementation always produces the correct answer.
Those implementations look good, and really fast!
I see this as confirmation of my earlier view that adding BigInt.log2
(or BigInt.bitCount
, where log2 == bitcount-1) would be useful (because engines can do that much faster than userspace: they just read an internal field that exists anyway), whereas BigIntSqrt
and BigIntCbrt
can then easily be implemented in userspace by the few who need them.
whereas
BigIntSqrt
andBigIntCbrt
can then easily be implemented in userspace by the few who need them
I continue to strongly disagree with this point of view. There are many situations where one might want to take a square root of a BigInt but not have the expertise to implement the efficient iterative algorithm correctly. Broadly applicable operations which require expertise to implement are precisely the sort of thing which the language should take care of.
Like, do we think this person is going to come up with the correct implementation independently? (Note that the snippet using Newton's method in the accepted answer is wrong; pass it 4n
.) This is the first result for "javascript bigint sqrt" on google.
There's an argument against putting things like this in the language when it would require a lot of code in an implementation, but that's not the case here. I don't understand the argument against putting this in the language at all.
I'd second @bakkot's reply. People looking to compute roots of BigInts will copy the buggy "javascript bigint sqrt" answer from StackOverflow, which does indeed get √4 wrong and is needlessly slow on large values.
The correct code to compute roots is tiny (just a few lines of JavaScript) but tricky to get right if you're not math-minded. This is why I wrote and included mathematical proofs of correctness on all inputs in the version I linked above. Let me know if you have any questions about any step in the code or the proofs.
Thanks @waldemarhorwat for your work on a reference JavaScript implementation of BigInt sqrt
and cbrt
. (I’ve also removed clz32
as per a conversation with @syg.)
I’ve added back sqrt
to the explainer and spec as per @waldemarhorwat’s requirement (he would block this proposal if it did not have sqrt
). I will add that I forgot my own use case for BigInt sqrt
: standard deviation.
Even if cbrt
’s implementation is simple, I still can’t think of a use case for cbrt
—the closest I can find to applications of cbrt
is in this thread from a forum about HP calculators, where even they say that, “Consensus is that practical applications for the cube root function are limited.” I believe @waldemarhorwat would not block this proposal if it did not have cbrt
. Therefore, I am still excluding cbrt
from this proposal, unless someone has a better idea.
We shouldn't design the language according to who will or will not block a proposal.
If ECMAScript's numerics didn't already have cbrt
, I wouldn't miss it. However, they do and we should respect that. Trying to optimize it out for BigInts introduces a gratuitous divergence. If there were a compelling reason that makes it hard to implement, that would be one thing, but I don't see one. Even if we would have done things differently if we were starting from scratch, the committee should not keep changing its mind about minor APIs in the language over the years — that just sows complexity.
Although I’ve been trying to find compromises that maximize the probability that this functionality will eventually be added to the language, I do agree that introducing BigInt sqrt
but not BigInt cbrt
is a strange and gratuitous divergence, especially given that you have demonstrated that both do not seem difficult to implement or maintain. Let’s talk about this more at the upcoming plenary’s BigInt Math breakout session (if there’s enough time for it).
I’m spinning this out of #13.
@waldemarhorwat:
@jakobkummerow:
@waldemarhorwat:
@js-choi:
@jakobkummerow:
@waldemarhorwat: