Anomaly in mpn_sqrtrem and mpn_rootrem

[bodrato at mail.dm.unipi.it]

Ciao,

Il Lun, 6 Luglio 2015 11:28 pm, Torbjörn Granlund ha scritto:
> bodrato at mail.dm.unipi.it writes:
>
>   ... yes, I know, we really need to improve also odd sizes...
>
> Perhaps one could simply wrap the current function in code which appends
> a zero limbs, calls the current code, and then right-shift the root by
> half the limb bitcount?

This is a description of the patch I pushed yesterday:
https://gmplib.org/repo/gmp/rev/87ba695c8878
But I do not really like it. We alloc-copy-shift to add a dummy limb, then
we call a code that allocs-copies-shifts to (virtually) add two more dummy
limbs...

Anyway, in general the code for sqrt (no-remainder) is faster now than it
was before. With code from revision 16716 (3 weeks ago) we got
time tests/devel/try mpn_sqrt
[...]
user	0m25.299s

Now we get:
time tests/devel/try mpn_sqrt
[...]
user	0m23.300s

> (One would possibly need to suppress such code for operands below a
> certain size, to avoid slowdowns.)

There are some slowdown only for sizes 15,16,31,32, i.e. when the size is
near a small power of 2.

Now, for small sizes, computing the 4th root with mpn_rootrem is slower
than calling mpn_sqrtrem twice. Maybe we should improve mpn_rootrem for
small sizes in general...

Regards,
m

-- 
http://bodrato.it/papers/