I think you are remembering wrong. I don't think there is an iterative algorithm that doubles the digits for each iteration for sine. I studied numerical analysis at graduate level, and did not come across such an algorithm. Perhaps you are conflating it with square root or reciprocal, for which Newton iteration does converge that way. Newton iteration does not work for sine or cosine since the derivatives of sine and cosine are cosine and sine, so applying Newtons formula leaves you with something more difficult than the original problem.

Bob

 

This maybe?
https://math.stackexchange.com/ques...based-sine-approximation-work/4055812#4055812

 

This maybe?
https://math.stackexchange.com/ques...based-sine-approximation-work/4055812#4055812

Yes thank you, however i was already aware of that one that uses the 'identity':
sin(x)=3*sin(x/3)-4*sin(x/3)^3

and i have incorporated that into an algorithm and it's not too bad and i may end up using that one if i cant find the one i am looking for.

There is also one that uses a half angle identity i think it is 2*sin(x/2)*cos(x/2) and this uses multiplication rather than subtraction and also an identity for cos(x/2). It does converge slower but i would have to see if it is less computation intensive than the third angle approach to see if i can be faster overall even though it takes more iterations.
I start both off with a Taylor's of order 9 or 11 to get the starting value then 4 iterations of the third angle formula gets me 32 digits while 9 iterations of the half angle formula gets me about the same.

They are both still interesting to me though.

 

I think you are remembering wrong. I don't think there is an iterative algorithm that doubles the digits for each iteration for sine. I studied numerical analysis at graduate level, and did not come across such an algorithm. Perhaps you are conflating it with square root or reciprocal, for which Newton iteration does converge that way. Newton iteration does not work for sine or cosine since the derivatives of sine and cosine are cosine and sine, so applying Newtons formula leaves you with something more difficult than the original problem.

Bob

Well then without looking it up, do you know offhand the best algorithm for calculating the value of 'pi' ?
Maybe you do but that could be a first check to see if you stayed up on your subject matter
Dont get me wrong though, if you dont know it that does not mean you dont know your stuff just that you havent yet heard of that one yet.

But back to the sine algorithm...
This one beats the rest i assure you as i have used it countless times back in the 1980's because it was so fast and my original TRS80 computer only did single precision floats like 0.12345678 while i needed 0.1234567812345678 which is a lot different.
Could have been slower than i remember? I guess it could have been, but it could not be too slow or i would have never used it because i knew about Taylor's and Chebychev's for a long time before that.

An interesting part of this is that i had developed the algorithm independently before i had any idea it existed so that could be why it was not well known. However, even so, i had found it on a computer disk some years later and i cant be sure if it was known before my discovery or they got it from something i wrote ( wrote a lot more in those days). Right now though i dont care who first came up with it, i just want to be able to use it again

It is very nice to ba talking to someone who majored in some sort of numerical analysis and computations though i have always loved this subject as far back as i can remember. That is mostly because i quickly realized that many problems can not be solved in some sort of closed form and so numerical analysis was the last resort. I spent many hours studying methods to solve harder problems like partial differential equations which sometimes are either too difficult to solve normally or there is no solution other than a numerical one. I found realkly cool ways to solve some of those kind of problems as well as the simpler ones like regular ODE's and got a lot of enjoyment out of them all as well as good methods.

So maybe if i mention one or two of the ways i had discovered the sine algorithm maybe you can figure out how it was done.

The first was to use the inverse function x=asin(y) and having that we could solve for sin(x). Trouble is i cant remember what i used for asin(y) as it was not a series.
The second idea was using Taylor's on more than one function, and after combining functions we get an identity that reduces to a simple expression that results in the sin(x) function.
IT was either of those two ideas that led me to the solution but i cant remember which one because it was so long ago and i know i tried both.
The last one was when i explained it to someone right here on AAC's, in a PM i think. I explained the simple algorithm as well as the Taylor series derivation. I cant remember who that was (a college student) though too bad.

I also explained it on another site and i am now asking around there too.

Well any other ideas you have would be appreciated and thanks for looking into this.
Apparently if i can find it myself you are going to be very surprised at how fast it converges but keep in mind it was not made specifically for a binary routine (as is the usual case) it was for a higher level language that can already do the four banger's (+,-,*,/) and maybe square root already. Maybe that is why it is not very well known although i never looked into the binary application.

 

Well, if you preprocess your angles to keep' below pi/2 Taylor's series will give you sines of angles within 10 iterations (terms) to (just about) 64 bit precision.

 

https://en.wikipedia.org/wiki/Goertzel_algorithm

http://www.ee.ic.ac.uk/pcheung/teaching/ee3_Study_Project/Sinewave Generation(708).pdf

https://dspguru.com/dsp/tricks/sine_tone_generator/

https://zipcpu.com/dsp/2017/12/09/nco.html

 

It's a C++ template, just replace 'T' with 'double' and it should be readable. If you have trouble, look at the simulation here: https://www.desmos.com/calculator/cbuhbme355, it's pretty readable. I'm pretty sure it's not what you are talking about, it's just a (very) quick and dirty approximation.



You're missing the point about the CORDIC algorithm, the cleverness of it is that you can do complex vector rotations by arbitrary angles using ONLY bit shifts and additions, plus one multiplication if you want to preserve scale. Depending on the hardware, this may be the fastest option.



I agree....

cordic typiclay take one stage per bit of result
so a 16 bit answer takes 16 stages of cordic

 

Dug out one of my old dusty books, “Approximation of Functions” by about 8 authors, including one of my old professors.

This is the bible for computer function libraries giving you optimized polynomials and rational functions for approximations of many common functions found in runtime libraries.

On iterative algorithms, it states that they are only practical for functions whose inverse is an algebraic function, so that would eliminate sine.

It includes polynomials for sine and cosine that are good on the interval of 0 to pi/4 that take 3 terms to get 8 digits and 6 terms to get 16 digits. sine of any angle can be done by a sine or cosine in that range by symmetry. I doubt you could find an algorithm much faster than that.

Bob

 

Well, if you preprocess your angles to keep' below pi/2 Taylor's series will give you sines of angles within 10 iterations (terms) to (just about) 64 bit precision.

Thanks. What i found was that if i use a short Taylor's series for sin(x) combined with one of the sine angle reduction formulas i can get about 32 digits with 9 iterations. That's pretty good i think so i might end up using that at least for now. I just hope i can find the algorithm i was looking for even if i just use it for comparison.

 

https://en.wikipedia.org/wiki/Goertzel_algorithm

http://www.ee.ic.ac.uk/pcheung/teaching/ee3_Study_Project/Sinewave Generation(708).pdf

https://dspguru.com/dsp/tricks/sine_tone_generator/

https://zipcpu.com/dsp/2017/12/09/nco.html

Thanks a bunch i'll have to look through some of that stuff and see if i can use any of it.
Funny i was thinking of looking into the sine approximation using the z transform too.

 

Dug out one of my old dusty books, “Approximation of Functions” by about 8 authors, including one of my old professors.

This is the bible for computer function libraries giving you optimized polynomials and rational functions for approximations of many common functions found in runtime libraries.

On iterative algorithms, it states that they are only practical for functions whose inverse is an algebraic function, so that would eliminate sine.

It includes polynomials for sine and cosine that are good on the interval of 0 to pi/4 that take 3 terms to get 8 digits and 6 terms to get 16 digits. sine of any angle can be done by a sine or cosine in that range by symmetry. I doubt you could find an algorithm much faster than that.

Bob

Thanks for the info there. I can see that their point of view is different than mine in that they are probably referring to a raw sine calculation/generation in binary with a machine that can not calculate any form of a sine yet, which beings me to a very important point i forgot to mention even though it can be gleaned from my previous posts (it's not obvious at first). That is, the machine i was working with back in the 1980's could actually already calculate the sine of an angle, but only in single precision which is only about 8 digits. I needed 16 digits, so an iterative algorithm worked well because i already had a decent approximation all i had to do was feed it into the iterative algorithm. If i remember right there was also some sort of angle reduction with that one too, but that single precision pre-calculation is an important point because that changes everything. With an iterative algorithm that operates on the previous value like y[k+1]=f(y[k]) it works fast because the result is so close to perfect already. That may be why i remember it being so darn fast.

I hope either I or someone else can find it somehow i am sure you will get a kick out of it since you were deeply involved with numerical techniques.

Thanks for your replies and any other info you can add even if from that book which sounds very interesting.

I will also post another algorithm that i might be able to use so you can review it and maybe give me some tips on it or some modification.