Operations efficiency – Memory vs. CPU speed

viki2000 · Joined: 08 May 2013 Posts: 233

Thank you for the code and suggestions.
I will test that too and compare with CORDIC to see the error and the speed.
I noticed you tested with 128 steps, but actually I am interested in 10.000 or 5.000 steps. 128 is 8 bit, but 10K or 5K is 16bit. Do you will lose efficiency or slow down a lot the execution of the subroutine because I want so many steps?

Ttelmah · Joined: 11 Mar 2010 Posts: 19222

The operation takes the same time for each angle.
I was just testing to show that the error doesn't have any large jumps.

viki2000 · Joined: 08 May 2013 Posts: 233

I was wondering how did come up to that polynomial approximation formula and searching on internet I arrived to next websites:
http://www.coranac.com/2009/07/sines/
http://allenchou.net/2014/02/game-math-faster-sine-cosine-with-polynomial-curves/
http://www.nabla.hr/CL-DerivativeG3.htm#The%20approximation%20of%20the%20sine%20function%20by%20polynomial%20using%20Taylor%27s%20or%20Maclaurin%27s%20formula
http://www.math.smith.edu/~rhaas/m114-00/chp4taylor.pdf
https://namoseley.wordpress.com/2012/09/18/a-quick-and-dirty-sinx-approximation/
https://ccrma.stanford.edu/~dattorro/EffectDesignPart3.pdf

Ttelmah · Joined: 11 Mar 2010 Posts: 19222

I'm sure lots of people will have done the same. I just used a second order polynomial fit formula, applied it to the sin curve to get a best fit, then calculated the error terms and applied a third order fit to these.
Nowadays things like Numbers, and Excel even have the ability to do this for you, while in the past I programmed these by hand.

You may find some of the published ones are better than mine, but you have the balancing act of work versus the fit accuracy. 8* the performance while still giving close to 3 decimals, seemed a pretty good compromise.

The second one down you point to is a very similar approach, but he 'misses a trick'. By using abs, I generate both the upper and lower halves of the curve without having to do any if tests. I must admit I didn't bother to see if any similar improvement could be done on cos, but suspect it might be possible to improve this a little.

Ttelmah · Joined: 11 Mar 2010 Posts: 19222

I do find myself wondering what you are actually hoping to achieve?.
Thing is that working to great accuracy, requires accuracy all the way down the system, and this is often not compatible with speed (not just in the PIC itself, but in all the components feeding the PIC, and being fed by the PIC). So (for instance), synthesising a waveform, would not only require DAC's with really high accuracy, but all the subsequent circuitry, and designs that maintain this accuracy while the values are being updated. Then the likelyhood of high accuracy DAC's maintaining this actually accuracy at high slew rates is very low. Then at small angles, it is pointless to actually even try to calculate sin. For example at 1/10000th a full circle (0.0012566 radians), the sin gives the same number (0.0012566). Even up to 10 degrees, the difference between the angle in radians, and the sin of this angle is only in the third decimal!...
Unless you have some unlikely degree of precision in the actual values being fed into the system, or coming out, trying to work to large number of decimal places, especially quickly, is pointless.
Now, that having been said, if you really do need high speed, then the lookup table will always win. You only need 2500 points to generate sin for 10000 points round a circle, and this can be done in 10KB or ROM. Even some PIC16's could do this, while most PIC18's would do it using only a small percentage of their ROM, and 'run rings' round any other approach.

viki2000 · Joined: 08 May 2013 Posts: 233

viki2000 · Joined: 08 May 2013 Posts: 233

Speaking about accuracy and error of getting the sine using CORDIC or polynomial approximation, below is a link to an Excel file where I compare two sine waves.
https://goo.gl/cnDyfP
I used PIC14HJ64GP202 with XC16 complier _Q15sinPI mentioned above and I swept the range -32768 to +32767 and I got sine values in the same range, which I sent them with UART to a serial port.
Then I captured them as HEX directly in a .txt file using RealTerm serial software, and then I imported them in Excel in column A.
Column B is a conversion in DEC of the column A.
Then in column C I calculate/generate the sine using sin() Excel function having as index the column D.
In column E I make the difference between sin() Excel and the received data at the serial port converted in DEC (column B), which is basically the sine from _Q15sinPI function inside the PIC.
The charts of the sine waves show almost a perfect overlay.
The max. error/difference is 2.48.
Then considering 32767 as 100%, the max. spread/deviation is maximum 0.00759% between sine calculated with sin() Excel function and sine from _Q15sinPI function inside the PIC, which I find very good.
I would like to know if CORDIC or polynomial approximation can provide similar accuracy and if my comparison is the right approach. Afterwards I can look over the CPU speed, the execution speed of instructions. In the end I want to implement everything in CCS.

viki2000 · Joined: 08 May 2013 Posts: 233

I have tried the 1st implementation of CORDIC with the suggestion code, but I get some errors. The code is compiled, but the sine is not produced, the numbers that I get on serial port are not sine.

Ttelmah · Joined: 11 Mar 2010 Posts: 19222

Honestly I have to repeat my comment about using a look-up.

2500 points, will give you a 10000 point sin.

However you have already been told that no matter how good the signal is, you will get better results by changing the approach and synthesising a genuine sin, filtering, and using a precision rectifier.

temtronic · Posted: Mon Jun 12, 2017 6:34 am

Mr T's last paragraph is the real answer....
...a simple lookup table as it will be the fastest to implement,especially when only integers are used
Any ( every) time a PIC is asked to do floating point math or trancendentals(sin,cos,etc) it takes a LOT of time to do the calculations and the more precision you want the longer it takes.

Jay

viki2000 · Joined: 08 May 2013 Posts: 233

I will keep that in mind as the best implementation for speed and accuracy, lookup table to be the most reliable, when the memory space allows it.
Nevertheless, because you made me curious and for my learning steps, I will try the Cordic and polynomial approach and I will compare with _Q15sinPI XC16 in terms of accuracy (compared with Excel sin) and speed.
Below it is your polynomial approach calculated in Excel for 128 and for 32767 points.
https://goo.gl/3f2h9o
It gives 0.10902 % error compared with sin() Excel, versus 0.00759 % _Q15sinPI XC16 compared with Excel, so almost 15 times worse.
Now I will try some real implementation on PIC.

Ttelmah · Joined: 11 Mar 2010 Posts: 19222

You have to be aware also though that simple 'error' figures do not always tell the story.
The key point about the polynomial synthesis is it always gives smooth changes. Which for an analog synthesis means the nature of the error is less likely to be objectionable.....

RF_Developer · Joined: 07 Feb 2011 Posts: 839

Again, I am struggling to understand the motivation for this. Knowledge of computing history will probably shed some light on this topic, or vice-versa, as this is a subject that has occupied many of the finest minds of applied computing such as Knuth and others; much of the early applications of computers was algorithmic in nature and so much effort was applied to the efficient computation of transcendental functions (i.e. trig such as sine, cos, etc.).

Polynomial approximation based on Tchebychev polynomials has long (as in since the early 50s) been established as the most effective way of evaluating random sines and cosines. The maths of Tchebychev polynomials is well-established, and in particular provides a way of evaluating errors and controlling them to provide known error bounds over defined intervals.

Take a look at math.h. It is typical of most compilers maths libraries, and is conveniently implemented in C. Sin() and cos() functions are generally the same internally, using the cos() function with an altered input. This is indeed what is in math.h. Sin() is simple coded as cos(x - PI_DIV_BY_TWO). So, calling cos() is always faster than calling sin(). Then there are the cos() routines themselves. They all evaluate polynomials. They all evaluate polynomials (and the coefficients will have come from Tchebychev) but the polynomials are different for each required precision: float32 is different from float48 (yes, there's such as thing in PCD) and float64. Why? Because the coefficients required to give the precision required by each float type are different. There's no need to evaluate all the terms needed by float64 when working in float32. The polynomial is chosen to give the precision required by the float format.

Also, the polynomial is only required to evaluate cos over a limited range, normally one quadrant, generally, as in math.h, 0-Pi radians, or 0-90 degrees. So the input angle has to be normalised into that range. In math.h only six lines of each routine actually compute the cosine, the rest deal with sorting out the quadrant.

You may recall that I wrote this was for evaluating random sines and cosines. That's to say each call is independant and each value is calculated from the ground up. This is fine for general use, but for is not great for sequential evaluation, which is what you need to do when creating a wave live or for a table. One method that I've used successfully for such sequential computation, where a result can be partially derived from the previous value(s), is finite differences. This is the way Babbage would have done it. The basic concept is this:

sin(n+1) = sin(n) * Delta_c + cos(n) * Delta_s
cos(n+1) = cos(n) * Delta_c - sin(n) * Delta_s

The next sine and cosine are calculated from the previous values interactively. The deltas are the ratios between the values for sin/cos(1) and sin/cos(0) and are dependant on the number of steps you want to use. You only need to evaluate a quadrant, and simply reflect and reuse to get the other three quadrants. The limitation comes as Delta_c is almost one and Delta_s is nearly zero, and become much more so as the number of points increases. This results in precision problems. However I have used this twice, once fairly recently for a test pattern, where high precision was not a requirement, and the first time in the mid-eighties where I computed a sine/cosine table for 256 point FFTs in 16 bit integers on a TMS32010. It did the job well. Much later I did some analysis on the errors, which were surprisingly small and had no practical effect on the resulting FFTed data.

I would not use this for evaluating 10000 point sine waves on the fly, but is quite usable and fast compared to a polynomial approach for smaller numbers of points.

In any case a table driven approach is pretty much always going to be faster than any evaluative method if ultimate speed is your prime requirement. If there's not enough memory then simply use a bigger processor, it's that simple.

I have to say, though, that in general ultimate speed has never been my prime requirement. When I first got into computing, in the mid to late seventies, I did have something of an obsession with speed above all else, after all wasn't that what computers were all about? Well, no as it turns out. As I learned to program in high level languages, I realised that raw speed was rarely what I needed to worry about. Also, optimisation was rarely cost-effective in terms of speeding things up: buying faster hardware was generally a much better option, even then. Optimisation rarely gave more than a few percentage points of improvement in any case. Instead adopting better algorithms tended to give much better returns. With PICs I have rarely, if ever, had to get firmware working faster. I have only ever use fast_io once - for an active attenuator, but even then, overlapping ADC conversions with setting the attenuator gave much greater improvement, to the point where fast_io didn't improve the raw speed, instead it just gave faster transition times as the IO was not on one port (due to someone else's design I inherited, I hasten to add) and therefore had to be done in two stages.

In this particular case, it's worth going back to the basic lessons: most, if not all, compilers implement constant collapse. This replaces expressions using constants with an equivalent constant. It is certainly worthwhile re-arranging expressions to exploit this as much as possible, especially divisions. In much the same vein, its often worthwhile replacing divisions by constants with multiplications by the reciprocal, i.e. 1/constant. Look-up tables will always give much faster results, but at the price of using more memory. For PICs, tables in RAM are always faster that tables in other memory, but again, it comes at a price. Pre-calculating partial results that are used more than once often saves some time, but again uses more RAM and code space. using pointers into RAM arrays is generally faster than array indexes, especially into multi-dimensional arrays as array access often involves a multiplication (by the element size and by the size of higher dimensions). The price is that pointers are very easy to get wrong, causing hard to find errors. I've done all in my time, but rarely do any unless I really have to.

Knowing if and when to optimise and what will give you the best result is a matter of experience, and one size never fits all. Its also, unfortunately, hard to get that experience without a project with a definite requirement which targets your effort.

viki2000 · Joined: 08 May 2013 Posts: 233

Thank you for your suggestions.

viki2000 · Joined: 08 May 2013 Posts: 233

I have made some tests using the proposed polynomial approximation.
The PIC used is PIC24HJ64GP202 with 80MHz internal clock. The data is sent to serial port and analyzed in Excel. I have tried the 128 points and 32767 points.
The result is here: https://goo.gl/3f2h9o
The conclusion is this, so far:
- Considering 32767 as 100%, the max. deviation between sine calculated with sin() Excel function and sine received at serial port, calculated inside the PIC with the polynomial approach below is 0.111%. Inside Excel, without any PIC involved the max. deviation between sine calculated with sin() Excel function and the proposed polynomial approximation is 0.109%.
- The _Q15sinPI fixed point math function from XC16 is still the winner up to now with max. deviation 0.00759%, so better accuracy to approximate the sine with float.
Later I will measure also the speed of execution and I will compare them.
Here is the working code that I used with the proposed polynomial approximation.