3 ms·
That representation's even nicer – the logarithmic complexity is immediately evident: 1/(1 + x) = 1 - x + x^2 - x^3 ... = (1 - x) (1 + x^2)
by perihelions 3y ago
That representation's even nicer – the logarithmic complexity is immediately evident:
1/(1 + x) = 1 - x + x^2 - x^3 ...
= (1 - x) (1 + x^2) (1 + x^4) (1 + x^8) ...
late edit: I've tested and confirmed that the naive implementation does in fact work. This C snippet is within at most 1 ULP for most double floats in the range (0.5, 1.0]: I tested a few billion and found no counterexamples.
double recip(double y) {
long double x = ((long double) y) - 1.0;
long double u = 1.0 - x;
long double v = x;
for (int j=1; j<=5; ++j) {
v = v * v; // v = x^(2^j)
u = u * (1.0 + v);
}
return (double)u; // approx. 1.0/y
}