103 replies to this topic

[Nils Pipenbrinck]

Hi iMalc,

Do a search for MinMax polynomials. These give you the best approximation.

This stuff here is a must read as well: http://www.research....-functions.html

[Nick]

iMalc said:

It might be interesting to see if an even better approximation of a 4th degree polynomial can be obtained by either brute force trying of combinations, or by using a genetic algorithm of some kind.

I once tried that, but the gains are very minimal. Furthermore, in the case of sine and cosine it's faster to use a parabola and the square of -the same- parabola than to use a generic 4'th degree polynomial. Basically it puts a small restriction on the 'shape' of the polynomial, making it faster to compute. It also happens to make it efficient to compute the [-pi, 0] part and makes things perfectly symmetrical.

For other situations the more generic minimax algorithm can give excellent results. If you want a Real Challenge™ though try finding a fast approximation for pow and then share it with me. ;)

You might also be interested in this thread: Approximate Math Library.

[shat0821]

Exact value for Q when minimizing the absolute error:

Q = (3150/(pi^3)) - (30240/(pi^5)) - 2

[roosp]

How did you find this "exact" value for Q? I used it with Scilab to print the error, and it seems not to be the best value for minimum absolute error. In Scilab the minimum error is achieved with P=0.224 and thus Q=0.776. This corresponds also to the value of P=0.224008178776 (and thus Q=0.775991821224) which I found in an Internet publication. (error 0.0919%)
(Your Q=0.775160898644)

[yashez]

How do you get P?

[roosp]

P+Q=1 -> P=1-Q

Please check out the original formula from Nick (first post on page 1). BTW, the external images of his post do not work anymore. Too sad...

[Nick]

roosp said:

BTW, the external images of his post do not work anymore.

Thanks for noticing. I still have the images, but no place to host them. :surrender

[yashez]

roosp said:

P+Q=1 -> P=1-Q

Please check out the original formula from Nick (first post on page 1). BTW, the external images of his post do not work anymore. Too sad...

Yeah, I know that. I think I didn't express myself correctly.

I want to know how to find (with maths) P (or Q) that minimizes the absolute error and the relative one.

[yashez]

Nick said:

Thanks for noticing. I still have the images, but no place to host them. :surrender

I can host the images if you want.

[Nick]

yashez said:

I can host the images if you want.

Thanks a lot for the offer, but it seems like I can't edit the original post anyway. I've PM'ed our webmaster to see whether he could host the images on-site...

[roosp]

yashez said:

Yeah, I know that. I think I didn't express myself correctly.

I want to know how to find (with maths) P (or Q) that minimizes the absolute error and the relative one.

I got the values from this website http://fastsine.tripod.com


Error plots and some code. Excellent list with references.

[Dia]

FYI, the images have been fixed.

[cjhopman]

Ah, I have a couple more formulas for you to ponder.

Originally I calculated values for a generic degree 4 polynomial, but I like symmetry, so all the formulas that follow are symmetric around pi/2.

Starting with minimizing absolute error we get
~ 0.985893x + 0.052042 x^2 - 0.232915 x^3 + 0.037069 x^4

minimizing relative error
~ 0.983251 x + 0.056247 x^2 - 0.235056 x^3 + 0.037410 x^4

minimizing maximum error
~ 0.988023 x + 0.048651 x^2 - 0.231188 x^3 + 0.036795 x^4


And a graph of the errors over the range [0, pi]
green - min absolute error
blue - min maximum error
magenta - min relative error
red - nick's formula




Then I also calculated some more... so another graph

green, blue, magenta, red - same as above
black - min absolute error of the derivatives
yellow - min sum of absolute error and absolute error of the derivatives
cyan - min square of the error



And, an interesting note, nick's formula intersects sin(x) at pi/6 and 5*pi/6.

[cjhopman]

And i clearly did relative error wrong.

EDIT: corrected.

[evarobotics]

Hi Nick,

I know this is an old post but I just wanted you to know it has really saved my bacon. I've been struggling with a high speed motor control loop and needed a fast sincos().

I'm running on a Luminary Micro at 50MHz. The gcc sincos (presumably taylor series) ran in 104uS. Your polynomial approximation ran at 19.2uS.

Believe it or not this was still too long. So I implemented it in fixed point and got the sincos down to 2.3uS.

Now that's a spicy meatball!

[Sol_HSA]

I wonder why this hasn't been submitted to game programming gems.. =)

[v71]

Becasue it didn't encounter Nick 's likenings

[Nick]

evarobotics said:

I know this is an old post but I just wanted you to know it has really saved my bacon. I've been struggling with a high speed motor control loop and needed a fast sincos().
I'm running on a Luminary Micro at 50MHz. The gcc sincos (presumably taylor series) ran in 104uS. Your polynomial approximation ran at 19.2uS.
Believe it or not this was still too long. So I implemented it in fixed point and got the sincos down to 2.3uS.

That's an impressive result! I'm happy this approximation was of use to you. Recently someone also told me he succesfully used it on an AVR microprocessor.

Sol_HSA said:

I wonder why this hasn't been submitted to game programming gems.. =)

On this site it's accessible to anyone. Besides, an entire book could be dedicated to tricks like this. ;)

v71 said:

Becasue it didn't encounter Nick 's likenings

What do you mean?

[Sol_HSA]

Nick said:

On this site it's accessible to anyone. Besides, an entire book could be dedicated to tricks like this. ;)

Posting it in the book would make it accessible to a larger amount of people, and the GPG books are filled with nuggets like these, so it would definitely fit in. And would look nice in your CV. =)

[Andy201]

Groove said:

We could also used Taylor series for exp function.

I did it for my math library(http://glm.g-truc.net) and they are quiet efficient but low precision. My functions are build to use an "half precision".



I also tryed with the log function but the result was good, VC7.1 is really fastest.

It's also work well with asin, acos, atan and tan functions:








I have try with SSE instructions and I didn't kown this "optimisation" so I very interested :p

I've used Nick's Sin, Cosine stuff for an Iphone project that I am working on... those functions work a treat. Thanks Nick.

The reason I've resurrected this thread is that I need a fast way to compute the ACOS function. The one in the quotes is impractical on an ARM cpu with a VFP. All those multiplications will stall the VFP baddly, so realizing that there are far better people at working out math than me, is there a nice cheap fast way to do this that will give reasonably results.

Thanks for any help.