[patrick.pelissier@gmail.com: Fwd: Optimizing 1/x]
Paul Zimmermann
Paul.Zimmermann at loria.fr
Tue Sep 13 09:14:07 CEST 2005
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
More information about the gmp-discuss
mailing list