A perfect power, and then?
Niels Möller
nisse at lysator.liu.se
Sat Oct 27 21:59:19 CEST 2012
nisse at lysator.liu.se (Niels Möller) writes:
>> broot.c: mpn_broot and your mpn_xxx that computes a^{1/n-1},
>> perhaps call the latter mpn_brootinvm1
>
> I'll start with this one, then.
Here's an initial patch, integrating my code from a few months ago. Some
TODO items:
0. Support in speed, for benchmarking.
1. Wraparound optimizations.
2. Consider rearranging the iteration slightly. Now it is
r' <-- r - r * (a^{k-1} r^k - 1) / n (A)
(converging to a^{1/n - 1}). Rewrite the powering as
r' <-- r - r * ((a r)^{k-1} r - 1) / n (B)
Then we get rid of the (invariant, if we compute it at full precicion
up front) power a^{k-1}, at the cost of an extra mullo (of various
smaller sizes) in the loop. It makes some sense because a * r can be
computed using wraparound (the low half is the same as in the
previous iteration), and a * r = a^{1/n}, so this is the number we'd
really like to compute, so if we do this we should merge mpn_broot
and mpn_broot_invm1 back into a single function. (I vaguely to recall
similar issues in other newton iterations, where it might be
advantageous to, e.g., write an iteration to 1/sqrt(x) and get
sqrt(x) almost for free).
Or possibly
r' <-- r - r * ((a^2 r^2)^{(k-1)/2} r - 1) / n (C)
This has the potential advantage that the computation of a^2 r^2 is
one invariant sqrlo (the a^2), one plain squaring (the r^2), and one
balanced mullo (or mulmod_bnm1). In contrast, r^k (in A) needs powlo
with larger output than input, and a * r (in B) is a 2x1 unbalanced
mullo.
3. Write special code for the iteration increasing from one two two
limbs of precision.
Regards,
/Niels
-------------- next part --------------
A non-text attachment was scrubbed...
Name: broot.diff
Type: text/x-patch
Size: 9676 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20121027/85ded4ab/attachment.bin>
-------------- next part --------------
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list