[patrick.pelissier@gmail.com: Fwd: Optimizing 1/x]

[Paul Zimmermann]

   Well, I assume then that the benefits of such a method does *at least* 
   pay-off. The next question would be how slower is the next fastest 
   non-patented algorithm compared to HP's? Also, although I'm anything but 
   a lawyer, I'd be surprised if law forbids using a patented algorithm for 
   educational/non-profit purposes. So I assume that one could argue that 
   making patch (with the said HP algorithm) available would benefit many 
   and the burden of following the patent laws would be on the user, not 
   the provider of the code.

Sorry, the HP patent only concerns division (y/x), not inversion (1/x).
For division, I expect the next fastest non-patented algorithm to be
about 10% to 20% slower. Also, it will use more memory.

   Have you considered making contributions with your implementation to GMP 
   or seperate from GMP in form of patches to GMP?

When it will be finished, I'll submit my implementation to GMP.

   Out of curiosity, how much faster is the HP algorithm compared to the 
   current GMP division implementation. I assume it's sub linear (or is it 
   not?), but in practice is it close to log2(n) + C? Its complexity is 
   probably a function in the multiplication algorithm's complexity.

   -Ash

The current GMP division uses a recursive algorithm for large operands,
with complexity O(M(n) log(n)), whereas Newton's division has complexity
O(M(n)), so we can expect a more-than-constant speedup once Newton's division
is in GMP.

Paul