Optimizing 1/x
Ashod Nakashian
saghmos at xter.net
Sun Sep 11 11:18:23 CEST 2005
Hi,
Since GMP is highly optimized for the most common (and sometimes not so
common) calculations, I assumed that there would be an optimized
function for calculating the multiplicative inverse of a real (1/'mpf_t').
I don't seem to find such a function, so I assumed that mpf_ui_div might
have a specialized path for values of 1 (i.e. inversion), but there
seems to be no such path.
As I understand it, the code currently creates an mpf_t from the 'ui'
value. This value is normalized such that the division is done using the
mpf divisor as is and corrected by the exponent of the divisor.
This seems like a very simplistic approach that is sound (and probably
optimal) for arbitrary numerators. But the dire question is:
Why not use the Newton Iterations to computer 1/x?
And if it's not worth it (i.e. it won't be faster), why not simply
optimize the current algorithm using the fact that the numerator is a
simple 1.
It is hard to imagine that the GMP user base (in deed the developers as
well) didn't come across the need of a faster inversion calculation.
Am I missing something? Is it assumed since Newton's iterative method is
fairly easy to implement, one will do just that? (That still doesn't
sound like th GMP philosophy to me.)
So what do/did you guys do when you need(ed) to find 1/x quite rapidly?
-Ash
More information about the gmp-discuss
mailing list