Re: Faster div or 1/sqrt approximations

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:

Wikipedia has something on that, also literature; Moroz et al.
https://arxiv.org/abs/1603.04483 seem to give the optimum quasi-NR
method to do this, with one or two steps.

>
Impressive amounts of math here, unfortunately they completely miss the
point!
>
What they derive is the exact optimal value for the magic constant,
using zero, one or two text-book NR iterations.
>
However, if you are willing to take that first NR iteration
>
  halfnumber = 0.5f*x
  ...
  i = R-(i>>1);
  ...
  x = x*(1.5f-halfnumber*x*x);
>
and then make both the 0.5f and 1.5f constants free variables, you can
in fact get 1.5 more bits than what they show in this paper.

Wikipedia also has something about that...

In fact, using slightly different values for R (the magic constant)
results in very marginal changes in max rel error, while optimizing all
three constants improves that max error from the stated 1.75e-3 to about
0.6e-3!

Looks like https://web.archive.org/web/20180709021629/http://rrrola.wz.cz/inv_sqrt.html
who reports 6.50196699E−4 as the maximum error (also from the
Wikipedia article).

That's 10.5 bits of accuracy, not bad at all.

However... assume you want to do another NR step.  In that case,
you might be better off not loading different constants from memory,
so having the same constants might actually be an advantage
(whch does not mean that they have to be the original Newton steps).

>

 
I've also looked a little bit at simplifying exp(-1/x) directly, and
it seems an unpleasent function to implement; at least there is no
argument reduction which comes to mind.  With exp2(x), you can split
off the integer part and do an appoximation on the rest over a finite
interval, but if there is a fast approximation of the integer part
of 1/x without dividing, I am not aware of one :-)

>
:-(
>
Fast is probably what you get from a pure lookup table, but with no
obvious NR iteration to improve it.

I stronlgy suspect you're fight, but it is too late in the evening
to calculate this :-)