A perfect power, and then?

[Niels Möller]

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.