# Alternative to floating point computation for cortex m3

Hi,

I see that floating number calculations are consuming way too many CPU cycles for my application. I get one (float) sine oscillator for 7 sawtooth (integer) in 32kHz. I have tried also with sin(float) and with CMSIS arm_sin_f32, i get similar results in term of CPU demand.

Also scaling is a burden because normally it uses floats.

So i read that i should use fixed point arithmetic.
I haven't done it again, so what performance boost can i expect in general comparing to floating numbers?
Can someone present an example of scaling like multiplying an integer with (0.0f - 1.0f) in fixed point arithmetic?

I have downloaded some fixed point libs and I' m gonna try them. i just ask here for a alternative approach.

Isn't the absence of a floating point co-processor really limiting for the applications of a microcontroller or fixed point is an equal substitute?

Any help appreciated
Thanks

Several months ago I worked on a high resolution sine wave computation using fixed point. Here's the thread.

http://forum.arduino.cc/index.php?topic=372960.5

Admittedly, this uses the Cortex-M4 DSP extension instructions which do a 32x32 -> 64 multiply and then discards the low 32 bits, with round-off. Perhaps it could be done on Cortex-M3 with the normal 32x32 -> 64 multiply by just right shifting the result by 32 bits. The round off 32 bits down probably makes very little difference. Hopefully the compiler will be smart enough to just rearrange the registers?

You could also omit the 9th and 11th power terms to save some CPU time, for only a very slight loss of accuracy. The normal float library probably isn't that accurate anyway.

If you're ok with much lower (but still pretty decent) accuracy, you could also use the table lookup and linear interpolation approach, which can also be found in that same code, plus this lookup table. Notice it does 2 lookups from the table and uses the rest of the phase angle bits for the linear interpolation between them. The table is 257 entries, not 256, so the code can always just fetch 2 consecutive entries without extra time to check for the end of the table.

The other extreme would be using a board with a float point unit. I just recently launched a Kickstarter campaign for such a board. I know this doesn't help now with Cortex-M3, but maybe interesting for the future?

https://www.kickstarter.com/projects/paulstoffregen/teensy-35-and-36

Hm, thanks.

Yes the Teensy seems very interesting. The cortex m4 has also native DSP, m3 does this in software.

Anyway if it costs around 10euro I will certainly get some.

Wishes,
John

For this fixed point Taylor series code, the DSP extensions are only used for the 32x32 -> 64 with discard of low 32 bits, and an add or subtract. That all happens in 1 cycle, and it allows the compiler to avoid allocating another register for the never-used low 32 bits.

On Cortex-M3, you can do the same thing in (probably) 3 instructions, and of course the full 64 bits will be temporarily in registers which gives the compiler a little less optimization flexibility. Still, it should be pretty doable.

Sadly, only 10 euros for that high-end hardware isn't looking so feasible. Perhaps in the future as the microcontroller market moves to small silicon process nodes, and maybe if the microcontroller market becomes more competitive with these Chinese companies entering. But for now, those high-end chips with FPU aren't cheap, so 10 euro dev boards with them aren't likely anytime soon.

Hopefully that fixed point code helps in the meantime?

Fixed-point doesn't need a library. It's just formatting for the output. Like dollars and cents. Storing dollars as floating-point numbers is possible, with the cents represented as the decimal part. \$0.01, for example. But there's problems with loss of precision and approximation errors.

So just store cents in your internal variables. 123 items at \$0.20 each is 2460, which you write out as \$24.60. The decimal point is part of the formatting like the dollar sign. You will also notice that you don't have to format the trailing zero. If it was floating-point, you would be working with 24.6 as the number.

There are some other tricks to fixed-point maths, often related to the fact that division is relatively expensive compared to multiplication, but only on some architectures. The Due has a hardware division unit, so that is not necessary.

Thanks, yes i found this after a bit research. What i was looking for was easy.

I had something like s = y*(x0.000001f) and i made this as s= (yx)>>12. (digits are not exact in this example)

Very fast and no floats.

I have also started programming my 3 Due in vs2008 express and use Arduino IDE just for uploading (tick use external editor in preferences). Really satisfying for my kind of work.

Hello,

A while back i had to use 64 bit integers too because float or double just wasnt cutting it. This was on a Windows machine though but the idea should be the same.

The idea is to simply augment the real world number before storage. So a number like 3 gets multiplied by a number which is a whole power of 2 like 256, which means a shift will do it. So once the number is shifted it is then stored in this new form.
For example, the number 4 is shifted left 8 times which results in the number 1024. That gets stored. So each incoming number is scaled by 256 and then stored.
The precision gets better as we go up with that 256, but the range gets lower, so it's a trade off. We have to watch out for powers though because they can quickly get very large and cause an overflow in the data type.

Also, Chebyshev is better than Taylor's for computing trig functions because the errors are more uniformly distributed. How much this matters though will depend on the application to some degree.

Interesting.

In my app I create a sine with signal processing and saturating arithmetic,
I start with a sawtooth and compute the sawtooth with double frequency, a triangle and a pulse.
I create the sine by adding (saturated) the sawx2 with the product of the pulse and the triangle multiplied together.

This way i get all 4 basic waveforms in 7 lines of code, without lookup tables or floating calculation.

I don't know the math, i have made the algorithm through experimenting

fra77x:
Interesting.

In my app I create a sine with signal processing and saturating arithmetic,
I start with a sawtooth and compute the sawtooth with double frequency, a triangle and a pulse.
I create the sine by adding (saturated) the sawx2 with the product of the pulse and the triangle multiplied together.

This way i get all 4 basic waveforms in 7 lines of code, without lookup tables or floating calculation.

I don't know the math, i have made the algorithm through experimenting

Hi,

That sounds interesting too but if you want anyone to understand what you are doing and perhaps confirm the math you need to be more explicit about the technique details.
"I start with a sawtooth and compute the sawtooth with double frequency"

You mean you are creating a time domain version or frequency domain version or z transform or what?
Much more details on the procedure needed to expand and check over.

As i said my math skills are way limited.

I know the difference between time and frequency domain but i have only heard about the z transform.

My version is time domain based as i understand, and creates non band limited sawtooth and pulse waves.

I' m using this technique to create cheap triangle and sine.

I still haven't decided to post the code though that's the reason i just written an outline of the procedure.
In some months, perhaps i'll do it.

I guess people influent in math or signal processing would be able to understand the basic outline of the procedure and perhaps be able to provide amateur users code to create computational cheap sine waves...
(because i see code 200+ lines long to create a sine (i do it in 3 lines), or using tables with bilinear interpolation like the CMSIS emulated math functions and i' m not sure what is the point.
Perhaps mine is not so "accurate", but i do not care. These seem like triangles and sines to me and i have worked with triangles and sines for some time. Perhaps someday i will need a more accurate version and i would appreciate other people code but not now.

I have quite a big experience working with a modular synth where the only tools you had was to start from basic waves and apply basic arithmetic with saturation. It ran on a DSP platform and i had made on this quite a big amount of algorithms. (oscs, resonant filters, envs) So now i pass these algorithms in C. I'm happy the cortex-m3 offers 2 saturating instructions ( __SSAT(), __USAT() ) and with CMSIS i can put these instruction directly in my C code.

Hello again,

Well you have every right to perform crappy calculations as much as you see fit

(ha ha, just kidding there).

The main point is if it works and you are happy with the results, then what the heck, use it.

I'm not trying to tell you how to do this, just suggesting some things, and originally it looked like you were using Taylor's so i through i would add a little information here.

You might also be familiar with the technique of generating a sine synthesis for PWM. That involves the solutions to the intersections of a triangle and a sine wave. The triangle is at a fairly high multiple of the sine so it 'picks out' time portions of the sine. Those portions are then the PWM pulse length for that average time position.

There are a lot of ways of doing these things so i guess i thought you would like to discuss them. Some are better than others, and some are faster than others, but if you have something that works for you that's great too no matter how it compares to other methods.

I wish you all the luck with it.

Thanks,

well no i haven't heard again about what you mention but i googled it and came across this:

I can very loosely follow the article, the only thing i recognize is the multiple modulators with phase difference aspect, I have used 3-phase (and 6-phase) modulators on a digital chorus i have build with good, smooth result, way superior than the effect of units with one or two modulators.

Yes electronics, and signal processing are very interesting, and i try to read the papers i came across because bare practice can't replicate the accumulated knowledge of theory. The only drawback i can see is when theory overwhelms the simplicity of matters or when it draws too much intention on itself.

Anyway you have grabbed my interest on this and i' m almost ready to post this code and reveal my corporate secret (lol).

p.s. I made a google search on this and i can't find "cheap" sine function. I found instead:

So can you find an algorithm for sine creation with the following prerequisites:

a. No floating calculation

b. No look up tables.

c. arbitrary frequency

d. Max 10 -20 lines of code (mine is 7)

1. How many bits of precision?
2. How much error?
2a. How do you want to calculate the error - mean squares?

Look up "modified sine wave". That will show you one approach that works quite well for a large number of applications. It only has 1.5 bits of precision (3 value output) and that is all that's needed in many cases.

1. 32 bit
2. Don't know. I take it as an opportunity to learn that stuff. I'm gonna try to use the RMSE procedure to calculate error.

My version looks like this (the phase difference between channels comes from my scope, it isn't finished yet) The scope captures the output of my oscillator out of a DAC MCP4822 (12bit) running on a arduino due.

24kHz sample rate, 32 bit audio engine, 12bit DAC

(haven't found a way to upload an image) I uploaded it in my blogspot.

Why does the number of lines of source code matter so much?

I can understand concern about speed, accuracy, RAM consumption, even the amount of flash memory used by the compiled code.

For me code efficiency leads to speed, and i test it with how many oscillators i can run on the same time.

When I replace a couple of instructions with a single one (i.e. a C macro to saturate numbers consisting of 5 lines of code with a single CPU instruction i.e. __SSAT) i' m able to run more oscillators.

Also compilers are smart enough (as i found out) to make choices that lead to fewer instructions.

For an example an (int64_t) multiplication i perform in my function is assembled with the SMULL function that takes two 32 bit operands and produce a 64 bit result. This is faster.

If you deny that give me an example of the code i asked for with the constraints i asked, and forget constrain number 4 and a reality test can prove your point

I can understand that your trying to deal with the presumption that less lines of code always lead to faster code, which in some cases is true but the idea that fewer cpu instructions are computed faster is self obvious.

Read the image guide. I think it's a sticky post or it's in the "useful links" sticky post.

Of course once it's online somewhere else, you can link to it with [ img ] tags.

That's better.

Hello again,

Those waves dont look too bad really.
If you superimpose a real sine wave drawing you can get an idea how well it conforms, but if you want a real analysis then you can do a harmonic distortion analysis similar to the way it is done with audio amplifiers. That gives a good idea how good or bad it is. Of course if it works good enough for the application then there's no problem anyway.

Loop unrolling is a common way to speed up this sort of code, since looping overhead is quite expensive. Fewer instructions is not always faster.