Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add nroot function to math #71540

Closed
stevendaprano opened this issue Jun 20, 2016 · 11 comments
Closed

Add nroot function to math #71540

stevendaprano opened this issue Jun 20, 2016 · 11 comments
Labels
stdlib Python modules in the Lib dir type-feature A feature request or enhancement

Comments

@stevendaprano
Copy link
Member

BPO 27353
Nosy @tim-one, @rhettinger, @mdickinson, @abalkin, @stevendaprano, @skrah, @serhiy-storchaka, @iritkatriel

Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2021-08-20.10:31:43.900>
created_at = <Date 2016-06-20.00:22:40.281>
labels = ['type-feature', 'library']
title = 'Add nroot function to math'
updated_at = <Date 2021-08-20.10:31:43.899>
user = 'https://github.com/stevendaprano'

bugs.python.org fields:

activity = <Date 2021-08-20.10:31:43.899>
actor = 'mark.dickinson'
assignee = 'none'
closed = True
closed_date = <Date 2021-08-20.10:31:43.900>
closer = 'mark.dickinson'
components = ['Library (Lib)']
creation = <Date 2016-06-20.00:22:40.281>
creator = 'steven.daprano'
dependencies = []
files = []
hgrepos = []
issue_num = 27353
keywords = []
message_count = 11.0
messages = ['268875', '268911', '268916', '268917', '268926', '268933', '269008', '269009', '269230', '399954', '399957']
nosy_count = 8.0
nosy_names = ['tim.peters', 'rhettinger', 'mark.dickinson', 'belopolsky', 'steven.daprano', 'skrah', 'serhiy.storchaka', 'iritkatriel']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue27353'
versions = ['Python 3.6']

@stevendaprano
Copy link
Member Author

For bpo-27181 (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.

@stevendaprano stevendaprano added stdlib Python modules in the Lib dir type-feature A feature request or enhancement labels Jun 20, 2016
@serhiy-storchaka
Copy link
Member

Looking at bpo-27181, nroot() wouldn't help too much to implement geometric mean (msg267990).

@stevendaprano
Copy link
Member Author

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

@serhiy-storchaka
Copy link
Member

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

@rhettinger
Copy link
Contributor

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

@tim-one
Copy link
Member

tim-one commented Jun 20, 2016

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.

@mdickinson
Copy link
Member

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

@mdickinson
Copy link
Member

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

@stevendaprano
Copy link
Member Author

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.

@iritkatriel
Copy link
Member

Is this still needed? It was requested for bpo-27181, which has been resolved by now.

@mdickinson
Copy link
Member

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

@ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
@encukou encukou closed this as not planned Won't fix, can't repro, duplicate, stale Aug 24, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
stdlib Python modules in the Lib dir type-feature A feature request or enhancement
Projects
None yet
Development

No branches or pull requests

7 participants