ni...@lysator.liu.se (Niels Möller) writes:
> Sounds right. Such convolution type sum-of-products might want a
> separate function, returning 3 limbs.
But I'm not talking about a convolution, but about the complete
powering. If x is a candidate nth root, and x^n is of size s bits, I
want to compute a decent approximation of floor (x^n / 2^{s -
GMP_NUMB_BITS}) (a single limb value), and compare that to the input
number which x is supposedly a root of. Simplest way would be to use the
binary powering algorithm, and represent all intermediates as a
normalized limb sized mantissa and a shift count. To use it, one needs a
strict bound on the error, which I guess would depend on n, but I don't
think the error analysis is very difficult. One might even consider
using the floating point hardware.
I misthought... I was someplace in a mid-product limb land, where a
convolution-type thing would be the centre of a binary powering
algorithm.
I would like to avoid fp hardware in the portable parts of GMP. Looping
around umul_ppmm, keeping the msb = 1 should give a few correct bits.
The error will depend on the limb size and on n. For the ASL patch
(artificially small limbs) we might not be able to make this work.
I think that's going to be a lot faster than computing any middle limbs,
and that it's going to rule out almost all numbers which aren't
perfect n-powers.
It seem very reasonably.
I need to look into the present algorithn to get completely convinced,
though. I was under the impression that it in practice rejected bad n
values after a b-adic run at few-word "precision".
--
Torbjörn
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
http://gmplib.org/mailman/listinfo/gmp-devel
