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