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

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

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