Fixed point math routines

Sub forums for various specialist XMOS applications. e.g. USB audio, motor control and robotics.
Gothmag
XCore Addict
Posts: 129
Joined: Wed May 11, 2016 3:50 pm

Fixed point math routines

Post by Gothmag »

I hate to ask, but does anybody have a fixed point math acos or asin functions written they could share? I'm trying to get these calls down some, they dont take forever at 42uS but when I'm performing multiple calls of them at the same time along with i2c transactions the timing can start to get tight. Alternatively if anyone could recommend some books, papers, or other libraries in whatever language with source, that describe how this would be done I'd appreciate it.


User avatar
akp
XCore Expert
Posts: 578
Joined: Thu Nov 26, 2015 11:47 pm

Post by akp »

The quickest method, if you can use it, is a lookup table. acos(x) can be computed from asin(x) and asin(-x) is just -asin(x) so it seems to me you could have a pretty small asin lookup table (+ve input +ve output) if you don't need huge resolution. You can interpolate between points in your table to improve resolution a bit to trade off computation time with memory usage. I have done this for sin but not asin.

I have seen asin computed using N-R or from atan (which is itself computed from continued fraction expansion) if you despise lookup tables. And then the fixed point math gets messy compared to floating point in my opinion. But I don't think for real-world resolutions it would save a tonne of memory and would use a lot more compute power.

Interested to hear if anyone knows better, like I said I've not actually implemented arcsin myself in fixed point.
User avatar
akp
XCore Expert
Posts: 578
Joined: Thu Nov 26, 2015 11:47 pm

Post by akp »

Of course the lookup table + interpolation will get pretty inaccurate very close to input of -1 or +1, but N-R will take a long time to converge there, too. You might want to convert some of the functions here (http://http.developer.nvidia.com/Cg/index_stdlib.html) from floating point to fixed point for acos and asin and see if that gives you better results. Won't be as fast a lookup table but will use less memory. I haven't done it myself either.
Gothmag
XCore Addict
Posts: 129
Joined: Wed May 11, 2016 3:50 pm

Post by Gothmag »

Thanks, I'll check it out and see what works for me.
henk
Respected Member
Posts: 347
Joined: Wed Jan 27, 2016 5:21 pm

Post by henk »

Hi,

Have a look at https://github.com/xmos/lib_dsp
It contains many of the functions, and they are all reasonably well optimised.

Cheers,
Henk
henk
Respected Member
Posts: 347
Joined: Wed Jan 27, 2016 5:21 pm

Post by henk »

Sorry - that appears to be closed at the moment. Whilst that is being sorted out, you can download the source here

<https://www.xmos.com/support/libraries?subcategory=DSP>
henk
Respected Member
Posts: 347
Joined: Wed Jan 27, 2016 5:21 pm

Post by henk »

Even more sorry - just realised you want the arc sin and arc cos. Cody and Waite will have an algorithm for them, I will try and dig it out.
Gothmag
XCore Addict
Posts: 129
Joined: Wed May 11, 2016 3:50 pm

Post by Gothmag »

If you can find those that'd be great. As it is I use the xcore200 dsp math library everywhere it makes sense and it works really well. I looked for a copy of the book since it was cited but couldn't find one near.
User avatar
ahenshaw
Experienced Member
Posts: 96
Joined: Mon Mar 22, 2010 8:55 pm

Post by ahenshaw »

You can calculate arcsin from a reasonably simple infinite series. Look at:
https://en.wikipedia.org/wiki/Inverse_t ... ite_series
and choose a suitable cutoff point.

Arccos can be derived from that as arccos(z) = pi/2 - arcsin(z).

Someone on stackexchange provided this as a pretty accurate floating-point implementation:
y = x*(1+x*x*(1/6+ x*x*(3/(2*4*5) + x*x*((1*3*5)/(2*4*6*7)))))
Looks like you could get a fixed-point implementation out of that.
User avatar
ahenshaw
Experienced Member
Posts: 96
Joined: Mon Mar 22, 2010 8:55 pm

Post by ahenshaw »

I think you'll need to do a range reduction to use the polynomial approach, though. This may not be suitable. See this:
http://stackoverflow.com/questions/7378 ... c-funcions
Post Reply