Replace placeholder implementation of `root` to get exact cases right.

[Roman-Kerimov]

print(Foundation.cbrt(1000.0)) // 10.0
print(Double.pow(1000.0, 1.0/3.0)) // 9.999999999999998

Calculation through "pow" gives a different result.

[stephentyrone]

This is covered by the root function in the API, but the implementation needs to catch up:

Double.root(1000, 3)

This "should" produce 10, but there's currently a placeholder implementation that uses pow(x, 1/n). I'll re-purpose this bug to cover fixing that.

[stephentyrone]

Related to #9

[ocampor]

Hey @stephentyrone, Do you think that the best solution is to implement it from scratch, or do you have something else in mind?

[stephentyrone]

Implementing from scratch is in some ways the simplest option, but also requires the most work (and incurs the most ongoing validation burden--I wrote the system pow for Apple's platforms, so I know exactly how to implement root, but I also definitely know very much how much work maintaining math library functions entails).

C2x should add rootn to the standard C library; ideally we'll simply use that when it's available. But, it remains to be seen just how quickly it becomes available on various platforms that Swift targets.

It's possible to fix-up exact cases (on platforms with a sub-ulp accurate pow) by computing pow(result, n) and comparing to x. This is really simple, but unnecessarily slow, and doesn't work if the host system pow isn't good enough.

We could special-case n=2 and n=3; that would cover 99% of exact use cases on Darwin (but I'm not sure about the quality of cbrt on other platforms), but still leaves the bug in place for the rare 1% of cases.

I think I'll probably end up implementing root directly, but there's other stuff that I'll attend to first, since the error here is tolerable most of the time.

[ocampor]

Thanks for your answer! I was trying to understand to see if I could help.

_{Sent with GitHawk}

[stephentyrone]

Ah. It's a deceptively tricky issue to handle well; if you're interested in a small quick fix, special casing 2 and 3 should be easy. The other steps are all pretty involved =)

[Roman-Kerimov]

@stephentyrone, are there any cases where pow(x, 1/2) returns an inexact result?

[stephentyrone]

@Roman-Kerimov Not on a system with a good-quality math library (because 1/2 is representable, if pow has sub-ulp accuracy then pow(x, 1/2) will get all exact cases right). The problem with pow(x, 1/3) is that 1/3 is not representable in a binary floating-point type.

When a host-system pow does not have sub-ulp accuracy, then pow(x, 1/2) will probably be wrong for some cases as well.