BigInt `sqrt` and `cbrt`

[js-choi]

I’m spinning this out of #13.

@waldemarhorwat:

We should keep sqrt and cbrt for BigInts because we have pow. The truncation towards zero behavior is unsurprising (it matches /) and mathematically useful, both directly and in various algorithms.

For example, if you want to compute an arbitrary-precision square root of a BigInt, the truncated square root provides a great first step of the algorithm. You then square the truncated square root, subtract it from the original number, and proceed with the algoritchm.

For another example, if you want to compute a truncated square root of a BigInt to 2 decimal places, multiply your original BigInt by 10000n, take the truncated square root, and you'll get the answer times 100n.

Another example: Suppose you want to compute the square root of a BigInt n rounded to the nearest integer instead of truncated. This is how you'd do it:

roundedSqrt = (Math.sqrt(4n * n) + 1n)/2n

Combining the two examples above, here's how to compute the square root of a BigInt n rounded to nearest to two decimal places:

let t = (Math.sqrt(40000n * n) + 1n)/2n;
let i = t / 100n; // Integral part of result
let f = t % 100n; // 00-99 decimal part of result

sqrt and cbrt are just inverses of the most common cases of pow. It would be as weird to have one and not the other as it would be to have * but not /. They're easy and very lightweight to implement — the implementation cost of including them is trivial enough that it's not worth the effort to conduct developer surveys.

I'm afraid we're getting into analysis paralysis and design-by-voting rather than picking the simplest option, which is including the Math functions that mathematically make sense.

@jakobkummerow:

Suppose you want to compute the square root of a BigInt n rounded to the nearest integer

Then I suggest you do Math.round(Math.sqrt(Number(my_bigint))). In fact, if you're interested in results rounded to integer (or to two decimal places, for that matter), then your entire calculation is probably better off with Numbers.

sqrt and cbrt are just inverses of the most common cases of pow. It would be as weird to have one and not the other

That argument cuts both ways: pow is a legacy function rendered obsolete by the introduction of **, so there's little reason to extend it in any way (for BigInts or otherwise). So if the only reason to have sqrt is that we have pow, but the latter isn't really motivated other than by "because we could", then we might as well have neither of them.

the implementation cost of including them is trivial enough

From that claim, in turn, one could also conclude that it's perfectly fine to leave implementations to user space, especially as long as we know of no use cases.

@js-choi:

sqrt and cbrt are just inverses of the most common cases of pow. It would be as weird to have one and not the other

That argument cuts both ways: pow is a legacy function rendered obsolete by the introduction of **, so there's little reason to extend it in any way (for BigInts or otherwise). So if the only reason to have sqrt is that we have pow, but the latter isn't really motivated other than by "because we could", then we might as well have neither of them.

For what it’s worth, I would like to gently push back against the notion that pow is merely a “legacy function”. pow remains in use today in functional programming as a reducible and partially applicable function object. I would be quite surprised if it weren’t still being used in new JavaScript code today. It’s not like it’s the actually deprecated with statement.

And if pow is still being used in new code today, then it will remain surprising whenever it doesn’t act like **.

In addition, as long as we’re assuming that “BigInt sqrt is useful as long as BigInt pow is in the language”, I would argue that BigInt ** also does count as being “in the language”. Under the previous assumption, BigInt sqrt is useful as long as BigInt ** is in the language. sqrt being an inverse of ** should be just as important as sqrt being an inverse of pow.

@jakobkummerow:

To be accurate, let's keep the distinction between "sqrt is useful" (of which no evidence has been presented) and "it's weird not to have sqrt" (which is an opinion that some individuals have expressed).

@waldemarhorwat:

Then I suggest you do Math.round(Math.sqrt(Number(my_bigint))).

And then you'd sometimes get the wrong answer.

In fact, if you're interested in results rounded to integer (or to two decimal places, for that matter), then your entire calculation is probably better off with Numbers.

Yes, lots of things can be done using Numbers. That doesn't say anything about the cases where you want guaranteed precision and rounding/truncating behavior. I'm not interested in rehashing the debate about the general usefulness of BigInts.

the implementation cost of including them is trivial enough

From that claim, in turn, one could also conclude that it's perfectly fine to leave implementations to user space, especially as long as we know of no use cases.

One could reach an incorrect conclusion. I was referring to the amount of code this would take, which is minuscule — smaller than some of the comments on this thread. However, the knowledge required to do it correctly is quite specialized and not accessible to most users. Also, a user-space implementation would not work as well as a built-in one because it would not be able to take advantage of the internal representation.

[js-choi]

I presented a brief update presentation about this issue to the Committee at the October plenary today.

Meeting notes are available.

@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.

[waldemarhorwat]

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.

[jakobkummerow]

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.

[bakkot]

whereas BigIntSqrt and BigIntCbrt 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.

[waldemarhorwat]

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.

[js-choi]

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.

[waldemarhorwat]

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.

[js-choi]

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).

[js-choi]

(Note: We are now pursuing monomorphic BigInt.sqrt and BigInt.cbrt functions. See #13 (comment).)

Should BigInt.cbrt(-3n) truncate towards 0 (returning -1n) or −∞ (returning -2n)?
My inclination is truncating towards 0.