roots

[Jason Moxham]

On Tuesday 03 Dec 2002 10:10 pm, Kevin Ryde wrote:
> Jason Moxham <J.L.Moxham@maths.soton.ac.uk> writes:
> > There is quite a bit of code
>
> Are you sure that level of complexity is needed?  It's probably not
> necessary to squeeze every last bit out of the precisions used and
> stuff, since the real work is done in limb sized chunks anyway.
>

No , I'm not sure . Speed wise I dont think there is much difference , yo=
u=20
save on the shifting but the results are generally one limb bigger, this =
is=20
assuming that any copying(shifting by a multiple of GMP_NUMB_BITS) can be=
=20
ignored by using some type of rotating storage stack.

As you can see from the timings , for small n (<5 limbs) the varible prec=
ision=20
is slower due to all these overheads.

I don't think you save a lot code by doing it on limb boundarys , but I n=
eed=20
to take a closer look at this , could change the macros to fns.



> > perfect_power_testing (definitely)
>
> That stuff could do with a revision.  Some residue tests in
> particular, in a fashion similar to what I recently added to
> mpn/generic/perfsqr.c would be a start.

yeah ,some residue tests of various types would be a start , however good=
=20
improvements will come from replacing the actual calls to mpz_root which=20
calculate a full root , to calls to "nroot"(in my code) which calculate a=
 low=20
precision root . This can also be used for perfsqr , the higher the=20
probability that a non-square will pass the residue tests the better this=
=20
method will be.

eg

a 50-digit number that starts with 9876 is not an 11th power the remainin=
g 46=20
digits are irrelevant , so for each power we only test enough bits to tel=
l=20
the cases apart.