ni...@lysator.liu.se (Niels Möller) writes: I guess this means: Avoid using functions from libm, and avoid using floating point in critical loops. Right? There's a (non-critical) floating point operation in mpn_perfect_power_p involving some logarithm table. Right. I would actually avoid the latter too, but I am aware of that we have a small number of such things.
> 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. It would make some sense to introduce an mpn_powhi, which computes an approximation of the high n (normalized?) limbs. Would be useful also for mpfr, I guess. It would either have a documented maximum error, or it could return an error bound (I imagine the error bound could be slithly different for plain binary exponentiation and window based exponentiation). It seems better to have an error bound than a surprise error that might be to large and require recomputation. > 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". If I understand this correctly, most bad n ought to be rejected as soon as the precision is xn+1 or larger. I just got a crazy idea. Compute the logarithm of the number (to a few bits of precision, perhaps using table lookup). Multiply this logarithm by k. Exponentiate using the logbase (again using a small table). Conservatively compare to number being investigated. -- Torbjörn _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel