Ask Your Question
2

Reliable integer root function?

asked 2015-10-31 13:42:58 -0600

Peter Luschny gravatar image

updated 2015-11-01 03:01:10 -0600

Does Sage have an integer_root(x, n) function which reliable (!) returns floor(root(x,n)) for n-th roots? I think that it should be offered as a Sage function if not.

This seems to work:

def integer_root(x, n): return gp('sqrtnint(%d,%d)' %(x,n))

Integer n-th root of x, where x is non-negative integer.

// Related: question 10730.

Edit: The answer of castor below shows a second way to define such a function:

def integer_root(x, n): return ZZ(x).nth_root(n, truncate_mode=1)[0]

Which version will be faster?

edit retag flag offensive close merge delete

Comments

This exists at least for square roots: it is called sqrtrem() and also provides the remainder.

B r u n o gravatar imageB r u n o ( 2015-10-31 14:17:20 -0600 )edit

2 answers

Sort by ยป oldest newest most voted
2

answered 2015-10-31 15:41:24 -0600

castor gravatar image

nth_root(n,truncate_mode=1) does the job, e.g. Integer(124).nth_root(3,truncate_mode=1) is (4,False)

edit flag offensive delete link more

Comments

I cannot say that I like this interface. If you want to assign the floor-integer-root you have to work around all these flags. Compare:

Simple: integer_root(2^20, 21) -> 1

Sage: ZZ(2^20).nth_root(21, truncate_mode=1) -> (1, False)

Peter Luschny gravatar imagePeter Luschny ( 2015-11-01 02:46:08 -0600 )edit
2

answered 2015-11-01 10:54:30 -0600

slelievre gravatar image

updated 2018-10-26 06:54:01 -0600

(Edited to take comment into account.)

For square roots, the function you are looking for is isqrt (for "integer square root").

sage: isqrt(124)
11

Also available as a method of integers:

sage: 124.isqrt()
11

For n-th roots with n other than 2, one can build on @castor's answer and define:

def inthroot(a, n):
    """
    Return the integer `n`-th root of `a`, rounded towards zero.

    EXAMPLES::

        sage: a, b, c, d, e, f = 26, 27, 28, -26, -27, -28
        sage: inthroot(a, 3)
        2
        sage: inthroot(b, 3)
        3
        sage: inthroot(c, 3)
        3
        sage: inthroot(d, 3)
        -2
        sage: inthroot(e, 3)
        -3
        sage: inthroot(f, 3)
        -3
    """
    return a.nth_root(n, truncate_mode=True)[0]

The [0] at the end discards the boolean indicating whether the n-th root extraction was exact.

Alternatively, one could imagine modifying the nth_root method in src/sage/rings/integer.pyx, adding an optional argument to say whether one wants that boolean or not. The call sequence would change from the current

def nth_root(self, int n, bint truncate_mode=0):

to either

def nth_root(self, int n, bint truncate_mode=0, bint return_whether_exact=1):

or

def nth_root(self, int n, bint truncate_mode=0, bint return_whether_exact=0):

depending on whether we decide the default should be to return that boolean or not.

To check the current version of the nth_root method, do this:

sage: a = 2
sage: a.nth_root??

or look at it online, say at GitHub:

edit flag offensive delete link more

Comments

Obviously this is not the function I look for as I asked for n-th roots.

Peter Luschny gravatar imagePeter Luschny ( 2015-11-01 22:09:09 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2015-10-31 13:42:58 -0600

Seen: 1,649 times

Last updated: Oct 26