# Fast and accurate sine/cosine

103 replies to this topic

### #41Nils Pipenbrinck

Senior Member

• Members
• 597 posts

Posted 07 August 2007 - 09:26 AM

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
My music: http://myspace.com/planetarchh <-- my music

My stuff: torus.untergrund.net <-- some diy electronic stuff and more.

### #42Nick

Senior Member

• Members
• 1227 posts
• LocationOttawa, Ontario, Canada

Posted 07 August 2007 - 12:03 PM

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.

### #43shat0821

New Member

• Members
• 1 posts

Posted 13 November 2007 - 05:20 PM

Exact value for Q when minimizing the absolute error:

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

### #44roosp

New Member

• Members
• 3 posts

Posted 22 November 2007 - 11:59 AM

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%)

### #45yashez

New Member

• Members
• 4 posts

Posted 29 November 2007 - 11:05 AM

How do you get P?

### #46roosp

New Member

• Members
• 3 posts

Posted 29 November 2007 - 02:34 PM

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...

### #47Nick

Senior Member

• Members
• 1227 posts
• LocationOttawa, Ontario, Canada

Posted 29 November 2007 - 03:55 PM

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

### #48yashez

New Member

• Members
• 4 posts

Posted 30 November 2007 - 10:14 AM

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.

### #49yashez

New Member

• Members
• 4 posts

Posted 30 November 2007 - 10:15 AM

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.

### #50Nick

Senior Member

• Members
• 1227 posts
• LocationOttawa, Ontario, Canada

Posted 30 November 2007 - 10:27 AM

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...

### #51roosp

New Member

• Members
• 3 posts

Posted 30 November 2007 - 01:37 PM

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.

### #52Dia

DevMaster Staff

• 1120 posts

Posted 02 December 2007 - 09:16 PM

FYI, the images have been fixed.

### #53cjhopman

New Member

• Members
• 2 posts

Posted 16 December 2007 - 05:35 PM

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.

### #54cjhopman

New Member

• Members
• 2 posts

Posted 16 December 2007 - 06:51 PM

And i clearly did relative error wrong.

EDIT: corrected.

### #55evarobotics

New Member

• Members
• 1 posts

Posted 26 January 2009 - 07:22 AM

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!

### #56Sol_HSA

Senior Member

• Members
• 513 posts
• LocationNowhere whenever

Posted 26 January 2009 - 10:58 AM

I wonder why this hasn't been submitted to game programming gems.. =)
http://iki.fi/sol - my schtuphh

### #57v71

Valued Member

• Members
• 355 posts

Posted 26 January 2009 - 11:47 AM

Becasue it didn't encounter Nick 's likenings

### #58Nick

Senior Member

• Members
• 1227 posts
• LocationOttawa, Ontario, Canada

Posted 27 January 2009 - 01:34 PM

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?

### #59Sol_HSA

Senior Member

• Members
• 513 posts
• LocationNowhere whenever

Posted 27 January 2009 - 04:02 PM

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. =)
http://iki.fi/sol - my schtuphh

### #60Andy201

New Member

• Members
• 3 posts

Posted 29 January 2009 - 04:04 PM

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.

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users