mpn_invert implementing ApproximateReciprocal.

[Torbjorn Granlund]

Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:

  it would be good to understand where this discrepancy between mpn_invert and
  mpn_binvert comes from. Marco, I suggest you disable the while-correction-loop
  in mpn_invert to see the difference (if any) it makes with speed (of course
  the result will no longer be correct, but this is just to get an idea of the
  slowdown due to the corrections).
  
Oh, I had not realised that  DEBUG was enabled.  Sorry about that.

Things look really great with it disabled:

          mpn_binvert    mpn_invert
1        #0.000000003   0.000000009
2        #0.000000004   0.000000013
4        #0.000000007   0.000000022
8        #0.000000017   0.000000043
16       #0.000000056   0.000000113
32       #0.000000192   0.000000362
64       #0.000000672   0.000001076
128      #0.000002453   0.000003193
256      #0.000007628   0.000009004
512      #0.000023650   0.000025329
1024     #0.000068015   0.000068232
2048     #0.000172617   0.000172637
4096      0.000425522  #0.000422483
8192      0.001026843  #0.001011517
16384     0.015231000  #0.015171000
32768     0.037683000  #0.036840000
65536     0.083932000  #0.081554000
131072    0.200767000  #0.180834000
262144    0.435655000  #0.391770000
524288    0.978450000  #0.934971000

Here we see the power of mulmod_bnm1; binvert still uses "old-fashioned"
FFT wrapping and is therefore beaten for larger operands.

Marco, I would commit this code if I were you.

-- 
Torbjörn