Re: integer n-roots like sqrtint()

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Bill Allombert [2008-02-04 15:45]:
> On Mon, Feb 04, 2008 at 12:20:27PM +0100, Jeroen Demeyer wrote:
> > Hello list,
> > 
> > I am wondering if there is an analogous function to sqrtint, but for 
> > n-th roots?  With this I mean to compute floor(sqrtn(x,n)) exactly for 
> > integers x and n.
> > Unfortunately the obvious "floor(sqrtn(x,n))" does not work:
> > 
> > gp> \p100
> >    realprecision = 105 significant digits (100 digits displayed)
> > gp> floor(sqrtn(6^3,3))
> > %33 = 5
> 
> Using round would be significantly more reliable...

But wouldn't answer the original query ( a function sqrtnint which would
return floor(x^(1/n)) )

> If x is a perfect n-power, you can use ispower(x,n,&z);z

Yes, since perfect powers are the bad case, you could use

  if (!ispower(x, n, &z), z = floor(sqrtn(x, n)));
  z;

The correct answer of course is to implement a simple Newton iteration
analogous to the one in sqrtint(); sqrtn is acually implemented as
exp(log(x)/n), which is optimal for n huge but certainly not for
n = 3, 4, ...

Cheers,

    K.B.
--
Karim Belabas                  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`