My b^x approximation

[Z1202]

Is it ("phenomenon") just that taking n times sqrt() from 2^x (or multiplying x with 1/2^2n) before approximation makes it easier to approximate ... as triple sqrt() makes the response of original function ( 2^x in this case) close to straight line? Are there any drawbacks in doing this way?

Of course taking sqrt makes it easier to approximate, because the function is closer to the straight line and repeated squaring of the result is evening out the errors of your approximation to an extent. That said, as I mentioned eariler, I tried to "properly" do this trick, by applying Remez algorithm for optimizing f^2(x)=F(x) rather than f(x)=F(x) (where F (x) is the target function f is the constructed approximation function). This resulted in a comparable error for the same order of the polynomial in f. Considering that squaring is an additional source of precision loss in least significant digits, I'm not sure if this approach is worth it. I mean to make it worth it, you need to have a significant benefit compared to f(x)=F(x), right? So, only if you want to stay within the domain of simple approximation tricks, such as Taylor, this is probably justified.

Or maybe I missed something, and one can really build better approximations that way?

[mystran]

Or maybe I missed something, and one can really build better approximations that way?

I doubt it. There's no need to even "try" this, because by definition(!) no other polynomial of the same degree will give you a smaller maximum error than the min-max polynomial, so you cannot possibly improve the approximation without either increasing the degree or changing the optimality criteria.

[juha_p]

Thanks for the comments regarding my queries so far. I'm in learning mode.

Another matter I don't fully understand is why this tweaked Taylor polynomial works as expected (desmos plot) only in range 0...Ln(2)/2 when brought to C++ code ...

Code: Select all

float taylor2_exp(float x){
	return 1.0f + x * (1.0f + 0.5f * x);
}

float taylor2_exp_tweaked(float x){
	float k1 = 0.5f;
	float k2 = 2.6f;
	float v1 = 1.0006f;
	float v2 = 1.946f;
	float l1 = 2.017f;
	return v1 + k1 * x * (v2 + k2 * x/l1);
}

when desmos plot looks OK for whole range 0...0.5?
Original Taylor polynomial also has a slight dip in accuracy at same location so maybe it's related to polynomial degree ... but why desmos shows it differently?

https://www.desmos.com/calculator/gkiaufsabj

What should be done to get it work in full range 0...0.5?

EDIT: Found the reason for this "issue". When functions were called direcly (normal way) they returned right values but when called from a function which handles integer part separately both gave wrong answer when approaching value of ln(2)/2 and after that point. Case solved.

[Z1202]

Or maybe I missed something, and one can really build better approximations that way?

I doubt it. There's no need to even "try" this, because by definition(!) no other polynomial of the same degree will give you a smaller maximum error than the min-max polynomial, so you cannot possibly improve the approximation without either increasing the degree or changing the optimality criteria.

Doesn't sound to me as a convincing proof, because the set of polynomials of order 2N which are squares of polynomials of order N doesn't match the set of polynomials of order N. I mean I'd compare 2N to N because it doesn't make sense to compare 2N to 2N, as the number of operations differs by two times

[juha_p]

Or maybe I missed something, and one can really build better approximations that way?

I doubt it. There's no need to even "try" this, because by definition(!) no other polynomial of the same degree will give you a smaller maximum error than the min-max polynomial, so you cannot possibly improve the approximation without either increasing the degree or changing the optimality criteria.

Doesn't sound to me as a convincing proof, because the set of polynomials of order 2N which are squares of polynomials of order N doesn't match the set of polynomials of order N. I mean I'd compare 2N to N because it doesn't make sense to compare 2N to 2N, as the number of operations differs by two times

If you take the additional multiply/multiplies as increase of degree then you'd get worse approximation compared to equal degree polynomial but otherwise, f=sqrt(exp(x)) (or exp(x/2) has less error than f=exp(x) when approximated using Sollya's p=remez(f,3,[-0.5,0.5])^2 function call in my example plot below (actually, same result with most of those other methods/software I've tried so far). But, (as I wondered in my previous post) does desmos show it right ...?

https://www.desmos.com/calculator/tb5brainnb

[mystran]

Doesn't sound to me as a convincing proof, because the set of polynomials of order 2N which are squares of polynomials of order N doesn't match the set of polynomials of order N. I mean I'd compare 2N to N because it doesn't make sense to compare 2N to 2N, as the number of operations differs by two times

Oh, I thought we were talking about correcting Taylor polynomials with separate approximation polynomials of some transcendentals. That's guaranteed to be unprofitable, by definition.

I'm sorry, I should have more carefully read which part you'd quoted.

[juha_p]

Here's another "low degree" approximation of exp(x/4) in range [-ln(2)/2...ln(2)/2]:



Plot: https://tinyurl.com/y4lutca7 (WolframAlpha link)

After some rolling, if all went well, final function could be something like:

Code: Select all

float expapproxD2F_x4(float x){
	float p = 0.99982300966f + x * (0.25f + x * 0.03125f);
	p*=p; // ^2
	return p*p*1.000708274727f;
}

[juha_p]

Sorry bumping an old thread but, here is a non-SSE/AVX exp approximation for range [-0.5,0.5]:

Code: Select all

float exp_jp(float x)
{   //[-0.5,0.5] e^x approx polynomial, error < ±2e-07

    return (-120.0f+x*(-60.0f+(-12.0f-x)*x))/
                (-120.0f+x*(60.0f+x*(-12.0f+x)));
}

and SSE version of it:

Code: Select all

__m128 exp_jp_sse(const __m128& x)
{   //[-0.5,0.5] e^x approx polynomial, error < ±2e-07
    const __m128 c0 = _mm_set1_ps(-120.0f);
    const __m128 c1 = _mm_set1_ps(- 60.0f);
    const __m128 c2 = _mm_set1_ps( -12.0f);
    
    __m128 P = _mm_add_ps(c0,_mm_mul_ps(x,_mm_add_ps(c1,_mm_mul_ps(x,_mm_sub_ps(c2,x)))));
    __m128 Q = _mm_add_ps(c0,_mm_mul_ps(x,_mm_add_ps(-c1,_mm_mul_ps(x,_mm_add_ps(c2,x)))));
    
    return _mm_div_ps(P,Q);
}

Speed test (2DaT's routines):

Code: Select all

Approx. rdtsc/val... (datasize: 524288)
std::exp       exp_jp      exp_jp_sse
----------------------------------------------
18.72511    2.72589     2.72531

https://godbolt.org/z/vb8f3v4rx
https://www.desmos.com/calculator/3ydm7usljm

Here is one more approximation implemented in three different ways:

https://godbolt.org/z/YcKs1vehY