Wed, 4 Dec 2002 00:05:14 +0000
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=
save on the shifting but the results are generally one limb bigger, this =
assuming that any copying(shifting by a multiple of GMP_NUMB_BITS) can be=
ignored by using some type of rotating storage stack.
As you can see from the timings , for small n (<5 limbs) the varible prec=
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=
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=
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=
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=
method will be.
a 50-digit number that starts with 9876 is not an 11th power the remainin=
digits are irrelevant , so for each power we only test enough bits to tel=
the cases apart.