Anomaly in mpn_sqrtrem and mpn_rootrem

bodrato at bodrato at
Tue Jul 7 08:28:45 UTC 2015


Il Lun, 6 Luglio 2015 11:28 pm, Torbjörn Granlund ha scritto:
> bodrato at 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:
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

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...



More information about the gmp-devel mailing list