collapse

Author Topic: CORDIC algorithms  (Read 4342 times)

deshipu

  • Member
  • *
  • Posts: 113
  • Radomir Dopieralski
    • Homepage
CORDIC algorithms
« on: December 21, 2016, 04:46:58 PM »
We often need to use trigonometric and inverse trigonometric functions in our microcontroller projects. Whether it's calculating inverse kinematics, figuring out angles and distances, stabilizing a quadcopter or otherwise dealing with angles -- those functions are indispensable. Personally I'm using the atan2 and acos functions in my robots for calculating inverse kinematics of the legs. I'm using the standard floating-point functions from math.h, but that is suboptimal.

First of all, the implementations of those functions are rather large. Just adding them to my AVR code makes it swell by some 3000 bytes. That is partially because they probably have some lookup tables and complicated logic, but also because they are floating-point functions, and pull in all the floating point multiplication, division and other operations, which are quite costly on a poor microcontroller without a co-processor.

Second, they take and return values that are scaled rather arbitrarily (-1:1, -PI:PI, etc.), so afterwards I have to do some more floating point operations to get them to the 0-1800 range that I need for my servos.

So I decided to try and find integer replacements for those functions. I couldn't find any that would be suitable. They were either floating-point, using some strange fixed-point types, using huge lookup tables, etc. However, during my search I discovered a family of algorithms called CORDIC, which allows me to calculate trigonometric and inverse trigonometric functions with minimal code, using only a lookup into a tiny table, additions and bit shifts. If you are interested about how those algorithms work, I wrote a short article about it at https://hackaday.io/project/6050-tote/log/50664-cordic

Anyways, I still couldn't find a decent implementation of those algorithms for the AVR, so I set out to write my own. I started by prototyping them in Python (because it's easy to debug for me and fast to write), and when I got them to work with a reasonable accuracy (I don't need much, 0.1° is enough, my servos won't move at better accuracy anyways), I re-wrote them in AVR C. The code is at https://bitbucket.org/thesheep/imath/src/tip/imath.c and it currently takes about 514 bytes when compiled with my avr-gcc. I suspect a couple of bytes could be shaved here and there from it, but I'm pretty happy with it already. Oh, I also added a square root function in there, for completeness.

Enjoy!

Protowrxs

  • Member
  • *
  • Posts: 146
    • The Protowrxs World
Re: CORDIC algorithms
« Reply #1 on: December 21, 2016, 10:27:17 PM »
Although I really don't understand it all it has always been a pain trying to do many math functions on an Arduino even for dead reckoning, etc for me. I understand the concept of IK but not the method. I followed up on some of your links and it does help me some, just have much more to read to try to fully understand.

Thanks for sharing your info. Can this stuff be added as an Arduino library in any manner?
(Sorry, more stuff I do not understand)

I'd really like to try again to build a four legged walker but do it right this time. Maybe someday.

Stephen
The past is done, the future is not here, live today...
My Bots: http://www.Protowrxs.com/robotics

deshipu

  • Member
  • *
  • Posts: 113
  • Radomir Dopieralski
    • Homepage
Re: CORDIC algorithms
« Reply #2 on: December 22, 2016, 04:40:14 AM »
Can this stuff be added as an Arduino library in any manner?

Not sure what you mean. If you are asking if you can use this in your Arduino programs, then yes, the easiest way is to just copy the imath.h and imath.c files into the directory of your sketch, and do #include "imath.h" in your code. If you are asking whether I plan to make a pull request to the Arduino core to have this code included by default, then the answer is no.

 

* Search


* Recent Topics

"1984 Nixie Time" by 1 what
[May 08, 2020, 01:04:18 AM]


2D Side Scroller Cyberpunk themed by Killer Angel
[February 06, 2020, 06:39:40 AM]


A new wing design for model aircraft / drones by OddBot
[February 06, 2020, 04:42:06 AM]


SDR (Software Defined Radio) by Gareth
[February 02, 2020, 06:15:42 AM]


Circuit Math by ZeroMax
[January 31, 2020, 01:50:18 PM]


NanOMeter by Protowrxs
[January 01, 2020, 12:59:44 PM]


Investigating the VL53L0X Laser Rangefinder by erco
[December 30, 2019, 10:45:44 PM]


PS4 Single Handed Controller Deployed (part 7 of 7) by Gareth
[December 30, 2019, 09:52:29 AM]


"D" -Pad Workio just like Magic (Will Merlin stay or Go) (part 6 of 7) by Gareth
[December 30, 2019, 09:51:27 AM]


PS4 Joystick Digitals 4,5,6,7,10 - Analog's Lx,Ly,Rx,Ry Workio (part 5 of 7) by Gareth
[December 30, 2019, 09:50:37 AM]


Menu Workio ! (part 4 of 7) by Gareth
[December 30, 2019, 09:49:49 AM]


L1 trigger design Workio (Hori controller) (part 3 of 7) by Gareth
[December 30, 2019, 09:48:50 AM]


Hori aka PS4 Joystick Mappings (part 2 of 7) by Gareth
[December 30, 2019, 09:47:17 AM]


PS4 Single Left-Handed Controller (part 1 of 7) by Gareth
[December 30, 2019, 09:44:58 AM]


Time of Flight >>> Rounded Corners !!! by BaldwinK
[December 04, 2019, 05:46:08 PM]

* Recent Posts

Re: "1984 Nixie Time" by 1 what
[May 08, 2020, 01:04:18 AM]


Re: "1984 Nixie Time" by tomasp
[April 13, 2020, 06:03:28 PM]


Re: 2D Side Scroller Cyberpunk themed by Killer Angel
[February 06, 2020, 06:39:40 AM]


A new wing design for model aircraft / drones by OddBot
[February 06, 2020, 04:42:06 AM]


Re: "1984 Nixie Time" by Gareth
[February 02, 2020, 06:23:01 AM]


Re: SDR (Software Defined Radio) by Gareth
[February 02, 2020, 06:15:42 AM]


Re: SDR (Software Defined Radio) by ZeroMax
[January 31, 2020, 01:54:21 PM]


Re: "1984 Nixie Time" by ZeroMax
[January 31, 2020, 01:52:29 PM]


Circuit Math by ZeroMax
[January 31, 2020, 01:50:18 PM]


Re: 2D Side Scroller Cyberpunk themed by ZeroMax
[January 31, 2020, 01:45:33 PM]


NanOMeter by Protowrxs
[January 01, 2020, 12:59:44 PM]


Re: Investigating the VL53L0X Laser Rangefinder by erco
[December 30, 2019, 10:45:44 PM]


PS4 Single Handed Controller Deployed (part 7 of 7) by Gareth
[December 30, 2019, 09:52:29 AM]


"D" -Pad Workio just like Magic (Will Merlin stay or Go) (part 6 of 7) by Gareth
[December 30, 2019, 09:51:27 AM]


PS4 Joystick Digitals 4,5,6,7,10 - Analog's Lx,Ly,Rx,Ry Workio (part 5 of 7) by Gareth
[December 30, 2019, 09:50:37 AM]