classification
Title: Add nroot function to math
Type: enhancement Stage: resolved
Components: Library (Lib) Versions: Python 3.6
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: belopolsky, iritkatriel, mark.dickinson, rhettinger, serhiy.storchaka, skrah, steven.daprano, tim.peters
Priority: normal Keywords:

Created on 2016-06-20 00:22 by steven.daprano, last changed 2021-08-20 10:31 by mark.dickinson. This issue is now closed.

Messages (11)
msg268875 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2016-06-20 00:22
For Issue27181 (add geometric mean to statistics module), I need a function to calculate nth roots that is more accurate than pow(x, 1/n). E.g. math.pow(1000, 1/3) returns 9.999999999999998 instead of 10.0.

I have a pure-Python implementation of nroot which I believe is satisfactory, and I could use that, but I'm uncomfortable about making it a public function in statistics. It's not really a statistics function, its more general, and I think it would be generally useful enough that it should go into math.

To recap the options:

- leave nroot in statistics as a private function;
- leave it in statistics, but make it public;
- add it to math

I'm willing to do the first if there is no other alternative, reluctant to do the second, and think that the third is the most useful, but I don't have the ability to write a pure C version. If the math library was written in Python that would be the obvious place for it.
msg268911 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-06-20 17:04
Looking at issue27181, nroot() wouldn't help too much to implement geometric mean (msg267990).
msg268916 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2016-06-20 17:47
I suggested on python-ideas that the math module be given a pure-Python front end. Guido wasn't too keen on that idea, so I won't push for it.

He did agree that having nroot in math was a reasonable idea. If I attach a pure Python implementation and tests, is anyone interested in porting it to C? I'm afraid that "Hello World" is about the level of my C skills.

As far as the geometric mean goes, Serhiy refers to a comment about the naive calculation likely overflowing. That's true, but I don't intend to do a naive calculation. In any case, even if I don't end up use nroot for geometric mean, it will still be useful as a more explicit and more accurate alternative to pow(x, 1/n).
msg268917 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-06-20 17:57
For general use I think it would be more useful to make pow() supporting fractions (using as_integer_ration()).

>>> math.pow(1000, fractions.Fraction(2, 3))
100.0
>>> math.pow(100000, decimal.Decimal('0.4'))
100.0
msg268926 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-06-20 20:19
If this ends up going forward (and I'm don't believe a good case has been made), I would prefer the function to be called "nth_root" which is unequivocal and readable (it is also close to what Matlab uses: http://www.mathworks.com/help/matlab/ref/nthroot.html )

It seems that Matlab's reason for inclusion doesn't have anything to do with precision; instead, they say "While power is a more efficient function for computing the roots of numbers, in cases where both real and complex roots exist, power returns only the complex roots. In these cases, use nthroot to obtain the real roots."   Mathematica uses Surd[n, x] for that purpose.

Outside of Matlab and Mathematica, I'm not seeing this function elsewhere (on my calculator, in Java math, etc.).  This suggests that the need is minimal.

As an alternative, we could follow the model used in the itertools module and include "recipes" for functions that don't meet that bar for inclusion in the standard library.   Here's one recipe I found after a few seconds of googling:

    from decimal import Decimal, getcontext
     
    def nthroot (n, A, precision):
        getcontext().prec = precision
     
        n = Decimal(n)
        x_0 = A / n #step 1: make a while guess.
        x_1 = 1     #need it to exist before step 2
        while True:
            #step 2:
            x_0, x_1 = x_1, (1 / n)*((n - 1)*x_0 + (A / (x_0 ** (n - 1))))
            if x_0 == x_1:
                return x_1

Out of Steven's original suggestions, I most prefer "leave nth_root in statistics as a private function".
msg268933 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2016-06-20 21:02
Note that the very popular TI graphics calculators have had a distinct nth-root function at least since the TI-83.  It's a minor convenience there.

I'm +0 on adding it to Python's math module, which means not enough to do any work ;-)

Note that if it is added to `math`, it should also be added to `cmath`.

Short of that, a private function in `statistics` seems best to me.
msg269008 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-06-21 16:27
[Raymond, quoting Matlab]

> in cases where both real and complex roots exist, power returns only the complex roots.

Yes, this would be the main motivation for me, too, if only to be able to answer the many StackOverflow questions like this one: http://stackoverflow.com/questions/30923838/how-to-get-the-real-cube-root-of-a-negative-number-in-python3

+1 for a private function in the statistics module for now.
msg269009 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-06-21 16:33
[Serhiy]
> ... nroot() wouldn't help too much to implement geometric mean

It's fine, so long as it's only being called once or twice at the end of the calculation (it's even helpful to have the last operation be an nth root call, since that's a contracting operation that tends to reduce relative error). It's calling it on every single item in the input list and *then* multiplying that would be bad.
msg269230 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2016-06-25 11:36
On Mon, Jun 20, 2016 at 09:02:09PM +0000, Tim Peters wrote:
> Note that the very popular TI graphics calculators have had a distinct 
> nth-root function at least since the TI-83.  It's a minor convenience 
> there.

Likewise HP calculators ("xroot") and at least one Javascript library. 
But it does seem to be uncommon among programming languages. Which 
surprises me, because it is not just a convenience, it can be more 
accurate than using the generic pow(x, 1/n).

But seeing as there isn't that much interest, I'll stick with a private 
function in statistics.
msg399954 - (view) Author: Irit Katriel (iritkatriel) * (Python committer) Date: 2021-08-20 10:16
Is this still needed? It was requested for issue27181, which has been resolved by now.
msg399957 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-08-20 10:31
[Irit]

> Is this still needed?

It's not needed for geometric_mean. It's still a reasonable feature request, but it would be non-trivial effort to put a good quality implementation together - C doesn't have this function, so we can't simply wrap it like we did for cbrt. But at least IEEE 754 does specify a "rootn" function, so we know what the behaviour should be in all the various special cases.

cbrt probably covers a good proportion of use-cases for rootn (those that weren't already satisfied by sqrt).

NumPy seems to have survived without needing a rootn function so far, which seems like an indication that it's not a really pressing need.

Let's close, and re-open or open a new issue if someone discovers another good use-case.
History
Date User Action Args
2021-08-20 10:31:43mark.dickinsonsetstatus: open -> closed
resolution: rejected
messages: + msg399957

stage: resolved
2021-08-20 10:16:57iritkatrielsetnosy: + iritkatriel
messages: + msg399954
2016-06-25 11:36:37steven.dapranosetmessages: + msg269230
2016-06-21 16:33:59mark.dickinsonsetmessages: + msg269009
2016-06-21 16:27:23mark.dickinsonsetmessages: + msg269008
2016-06-20 21:02:08tim.peterssetmessages: + msg268933
2016-06-20 20:19:58rhettingersetnosy: + rhettinger, skrah
messages: + msg268926
2016-06-20 17:57:46serhiy.storchakasetmessages: + msg268917
2016-06-20 17:47:32steven.dapranosetmessages: + msg268916
2016-06-20 17:04:45serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg268911
2016-06-20 16:28:32rhettingersetnosy: + tim.peters, mark.dickinson
2016-06-20 16:27:06belopolskysetnosy: + belopolsky
2016-06-20 00:22:40steven.dapranocreate