@Thomas Klemm -> CORDIC Article
06-04-2014, 04:31 PM
Post: #22
 Claudio L. Senior Member Posts: 1,887 Joined: Dec 2013
RE: @Thomas Klemm -> CORDIC Article
(06-01-2014 11:57 AM)Tugdual Wrote:
(06-01-2014 07:32 AM)Thomas Klemm Wrote:  The WP-34S however uses:
Code:
    // Now Taylor series     // tan(x) = x(1-x^2/3+x^4/5-x^6/7...)
Interesting, I wonder what justified the choice.
A matter of patent?
What is the most efficient approach in terms of speed and accuracy between CORDIC and Taylor?
Or may be CORDIC was the right choice for old calculators with little ROM?

I recently implemented from scratch all the transcendental functions using CORDIC, and I tested a few simple cases using Taylor as well. I also used Taylor to compute the constants needed for the CORDIC method.

CORDIC is almost constant speed, regardless of the argument. Taylor needs more terms for larger arguments, and as you approach zero you need less terms. In the end, if you don't adaptively stop Taylor when you reach the desired accuracy, they should be about the same. For very small numbers, stopping Taylor properly will be much faster than CORDIC, while for large numbers CORDIC will likely win.
The other main difference comes with the hardware: if you have hardware multiply in the CPU, then Taylor will be fast, otherwise it will be much slower than the shifts in CORDIC.
If you are implementing Decimal CORDIC like I did, Taylor would be even faster since Decimal CORDIC needs a lot more shifts than the binary one (4 times more).

Regarding ROM memory usage, I think Taylor uses much less memory than CORDIC. CORDIC requires storage of a significant number of constants to operate properly in the entire range of numbers.
I thought I was going to be able to use only about 300kbytes of constants, but they ended up being about 1 MByte (half our total ROM space!). The additional constants were needed to obtain full precision in bad corner cases (like COSH(1e-500)).

For normal Trig functions, many of the 'quirks' of both methods can be resolved with argument reduction. Paul's example of COS(Pi/2-ULP) can easily be calculated as SIN(ULP) and only a few terms of Taylor will give you a good answer. For hyperbolics you are mostly out of luck.

I think CORDIC is still a very good method to implement in modest hardware or very small CPU's. Other methods start to shine when the CPU is more powerful. If the CPU can multiply in 1 cycle, and a shift takes also 1 cycle, then you'll get a lot more work done by using that multiplication than splitting it into many shifts and adds.

Still, it's quite competitive. My CORDIC implementation was about 3 to 5 times faster than the method implemented in mpdecimal for ln() and about 6 to 10 times for exp(). Granted, CORDIC was limited to 2016 digits precision, while the algorithms in mpdecimal are for unlimited arbitrary precision, so they can't use any precomputed constants to speed up calculations. If you were to specialize your algorithm for the same amount of digits you might be able to optimize it and match the speed.

The main reason to choose CORDIC is versatility: SIN,COS, TAN, ASIN, ACOS, ATAN, EXP, LN, SQRT, SINH, COSH, TANH, ATANH, ACOSH, ASINH, all use the same method. I had to code 5 variants of the method to keep it optimized: 2 for "normal" trig, 2 for hyperbolics, and one for exp() since it can use half of the operations, so it's twice as fast as the normal algorithm.

By the way, I'd like to share the best paper I found so far on Decimal CORDIC, which helped me a lot in my implementation:

http://www.ac.usc.es/arith19/sites/defau...paper1.pdf

Claudio
 « Next Oldest | Next Newest »

 Messages In This Thread @Thomas Klemm -> CORDIC Article - Tugdual - 05-31-2014, 08:00 PM RE: @Thomas Klemm -> CORDIC Article - brouhaha - 06-01-2014, 02:27 AM RE: @Thomas Klemm -> CORDIC Article - Thomas Klemm - 06-01-2014, 07:32 AM RE: @Thomas Klemm -> CORDIC Article - Tugdual - 06-01-2014, 11:57 AM RE: @Thomas Klemm -> CORDIC Article - Paul Dale - 06-01-2014, 12:12 PM RE: @Thomas Klemm -> CORDIC Article - Thomas Klemm - 06-01-2014, 07:32 PM RE: @Thomas Klemm -> CORDIC Article - Claudio L. - 06-04-2014 04:31 PM RE: @Thomas Klemm -> CORDIC Article - Tugdual - 06-01-2014, 07:48 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-01-2014, 08:28 PM RE: @Thomas Klemm -> CORDIC Article - Marcus von Cube - 06-02-2014, 08:47 PM RE: @Thomas Klemm -> CORDIC Article - Thomas Klemm - 06-02-2014, 06:39 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-02-2014, 10:13 PM RE: @Thomas Klemm -> CORDIC Article - Paul Dale - 06-02-2014, 10:26 PM RE: @Thomas Klemm -> CORDIC Article - Tugdual - 06-02-2014, 10:53 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-02-2014, 10:58 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-02-2014, 11:05 PM RE: @Thomas Klemm -> CORDIC Article - Paul Dale - 06-02-2014, 11:08 PM RE: @Thomas Klemm -> CORDIC Article - Tugdual - 06-02-2014, 11:13 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-02-2014, 11:20 PM RE: @Thomas Klemm -> CORDIC Article - Paul Dale - 06-02-2014, 11:42 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-03-2014, 02:02 PM RE: @Thomas Klemm -> CORDIC Article - Claudio L. - 06-04-2014, 05:57 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-04-2014, 02:52 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-04-2014, 06:06 PM RE: @Thomas Klemm -> CORDIC Article - Claudio L. - 06-04-2014, 06:21 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-04-2014, 06:30 PM RE: @Thomas Klemm -> CORDIC Article - Claudio L. - 06-04-2014, 06:37 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-04-2014, 06:45 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-04-2014, 07:16 PM RE: @Thomas Klemm -> CORDIC Article - Claudio L. - 06-04-2014, 07:36 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-04-2014, 07:30 PM RE: @Thomas Klemm -> CORDIC Article - Claudio L. - 06-04-2014, 07:41 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-04-2014, 07:51 PM RE: @Thomas Klemm -> CORDIC Article - Claudio L. - 06-04-2014, 09:05 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-04-2014, 08:12 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-04-2014, 08:34 PM RE: @Thomas Klemm -> CORDIC Article - Claudio L. - 06-04-2014, 09:21 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-04-2014, 09:21 PM RE: @Thomas Klemm -> CORDIC Article - Claudio L. - 06-04-2014, 09:39 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-04-2014, 09:33 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-04-2014, 09:41 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-04-2014, 09:50 PM RE: @Thomas Klemm -> CORDIC Article - pito - 06-04-2014, 10:46 PM

User(s) browsing this thread: 1 Guest(s)