@Thomas Klemm -> CORDIC Article
|
06-04-2014, 02:52 PM
(This post was last modified: 06-04-2014 03:18 PM by pito.)
Post: #21
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
@Pauli: Assuming my 27x x^2 and 27x POWPOW based tests give the same results as the wp34s, can I derive from that my trig implementation is a little bit more precise than yours?
|
|||
06-04-2014, 04:31 PM
Post: #22
|
|||
|
|||
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:Interesting, I wonder what justified the choice. 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 |
|||
06-04-2014, 05:57 PM
Post: #23
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
(06-03-2014 02:02 PM)pito Wrote: I've flashed my CM3 with the old stuff I've found - when running below code with 34digits I get (I've added your result for comparison): Does anyone know of a table of correct values for this? newRPL gave me (for 34 digits): 8.999999999999999999999999999999979 I ran a loop from 9 to 900 digits, and the difference is always only the last 2 digits, being the worst difference 85 ULP. But how do we know right from wrong? Claudio |
|||
06-04-2014, 06:06 PM
(This post was last modified: 06-04-2014 06:06 PM by pito.)
Post: #24
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
Quote:I recently implemented from scratch all the transcendental functions using CORDICOn which hw platform your implementation runs (cpu)? Quote:But how do we know right from wrong?The 9 degree test: The windows calculator (most probably decNumber lib 34+) gives you 9.0 Wolfram's alfa online gives you 9.0 |
|||
06-04-2014, 06:21 PM
Post: #25
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
(06-04-2014 06:06 PM)pito Wrote:Quote:I recently implemented from scratch all the transcendental functions using CORDICOn which hw platform your implementation runs (cpu)? Right now it's running on x86 (actually amd64). (06-04-2014 06:06 PM)pito Wrote:Quote:But how do we know right from wrong?The 9 degree test: That's my point, it's hard to find the right result. Obviously the 9.0 is incorrect if we accept that rounding is a fact. What I did to check: I got all my partial results at 34 digits precision on the stack, for each operation. Then I set the precision to 9 digits more. Then I picked each partial result and applied the operation (sin, cos, etc), and compared the result with higher precision to the rounded one to verify correct rounding (so I took a previous result, rounded to 34 digits, and used it as argument to a function with 43 digits). newRPL did the correct rounding every time. I found also that doing * PI / 180 is not the same as / 180 * PI (difference of 1 in the last digit). So I guess the "correct" answer will also depend on the order of the operations. I also tried preccalc (from sourceforge), which uses adaptive precision and also gives the useless 9.0. Claudio |
|||
06-04-2014, 06:30 PM
(This post was last modified: 06-04-2014 06:41 PM by pito.)
Post: #26
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
WP34s calc and various other arbitrary precision decimal fp libs/wrappers are using the IBM's decNumber library (which sets the standards). There are some settings for the rounding inside (context something), I never messed with them in detail, though. Maybe the difference between the results is related to the proper rounding setting's "know-how" with the library..
mpdecimal for example: Quote:libmpdec - C/C++ library |
|||
06-04-2014, 06:37 PM
Post: #27
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
(06-04-2014 06:30 PM)pito Wrote: WP34s calc and various other arbitrary precision decimal fp libs/wrappers are using the IBM's decNumber library (which sets the standards). There are some settings for the rounding inside (context something), I never messed with them in detail, though. Maybe the difference between the results is related to the proper rounding settings know how within the library.. Yes, but decNumber doesn't have sin, cos, tan, so everybody has their own implementations. We should all have correctly rounded results, so in theory all programs using a fixed precision should give the exact same number (not 9.0). The ones that use adaptive precision or use higher internal precision and the rounding is for display only (not for intermediate results) would be able to show 9.0. What we can do, is use Wolfram Alpha to do all the steps, but typing the 34 digit rounded result from the previous answer to get the final result with rounding. Same as I did in the stack. Claudio |
|||
06-04-2014, 06:45 PM
(This post was last modified: 06-04-2014 06:46 PM by pito.)
Post: #28
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
Caution: I've seen the situation where when 9 degree test had been compiled under C (crappy double precision) it gave 9.0. The C had optimized the math off, as it is symmetrical. Hopefully wolfram's alfa does not do the same when the 9 degree formula is entered in
![]() |
|||
06-04-2014, 07:16 PM
(This post was last modified: 06-04-2014 07:19 PM by pito.)
Post: #29
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
This is the entire sequence from wolfram's alfa (120digits):
Code: 0.15707963267948966192313216916397514420985846996875529104874722961539082031431044993140174126710585339910740432566411533 |
|||
06-04-2014, 07:30 PM
(This post was last modified: 06-04-2014 07:42 PM by pito.)
Post: #30
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
This is 34digits not rounded
Code: 0.157079632679489661923132169163975 and rounded Code: 0.157079632679489661923132169163975 Manual rounding at 34th digit. Not sure the proper one. |
|||
06-04-2014, 07:36 PM
(This post was last modified: 06-04-2014 07:37 PM by Claudio L..)
Post: #31
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
(06-04-2014 07:16 PM)pito Wrote: This is the entire sequence from wolfram's alfa (120digits): You just beat me to it, but here's my sequence for 34 digits: Code:
It's incomplete because the free version won't allow me to make it any longer, but all it's missing is the / pi * 180: Typing in the previous result: Code:
Gives the correct answer for 34 digits: 8.999999999999999999999999999999980 This is exactly what I get with newRPL (previously I reported 79 with the /pi*180 reversed, which is also correct). This can be used for any digits, changing the 34/33/35 accordingly for prec/(prec-1)/(prec+1). Claudio |
|||
06-04-2014, 07:41 PM
Post: #32
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
(06-04-2014 07:30 PM)pito Wrote: This is 34digits not rounded You got a problem here. Either the number above has one extra digit or all the others are missing one. Claudio |
|||
06-04-2014, 07:51 PM
(This post was last modified: 06-04-2014 08:22 PM by pito.)
Post: #33
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
Yea, it seems it is an extra, but the 1 at the end is not a big diff, maybe
![]() ![]() Do you mean (recalculated, rounded): Code: 0.157079632679489661923132169163975 |
|||
06-04-2014, 08:12 PM
(This post was last modified: 06-04-2014 08:21 PM by pito.)
Post: #34
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
When I put 9-1e-35 I get
Code: 8.99999999999999999999999999999999999 Code: 8.9999999999999999999999999999999999999999999999999999999 |
|||
06-04-2014, 08:34 PM
(This post was last modified: 06-04-2014 08:48 PM by pito.)
Post: #35
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
I did following experiment when entering the 9degree formula in the wolfram - I added a small epsilon to the 9:
Code: 180/pi*(asin(acos(atan(tan(cos(sin((9.0+epsilon)*pi/180))))))) |
|||
06-04-2014, 09:05 PM
Post: #36
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
(06-04-2014 07:51 PM)pito Wrote: Yea, it seems it is an extra, but the 1 at the end is not a big diff, maybe This one seems to be correct for 33 significant digits. WP34S uses 34, though. Claudio |
|||
06-04-2014, 09:21 PM
Post: #37
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
(06-04-2014 08:34 PM)pito Wrote: I did following experiment when entering the 9degree formula in the wolfram - I added a small epsilon to the 9: Wolfram has a very complex engine, either it symbolically cancels out the functions, or (more likely) uses adaptive precision. Basically, they internally keep recalculating the expression, adding as many precision digits as needed until the last digits they want to display don't change anymore. If they want to display a result with 34 digits, they start maybe with a 34-digit calculation, then they redo the math with let's say 39 digits, and round only the final result to 34 digits. If it is different, they add 5 more digits of precision and redo the calculation with 44, until the rounded final result doesn't change at all. So we see 34 digits, but all intermediate rounding was done at 39, 44 or higher, as needed to get a consistent final result. And in general, we should do this on the calculator as well: if WP34S has 34 digits for calculations, set your display to 30 digits or less, and in your mind, think that you are using only 30 digits. Then your 9 degree trig test will return exactly 9.0 with 30 digits, and the positive psychological effect of that "perfection" will put a smile on your face. Claudio |
|||
06-04-2014, 09:21 PM
(This post was last modified: 06-04-2014 09:29 PM by pito.)
Post: #38
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
Wolfram alfa, 34digits (hopefully), rounded:
Code: 0.1570796326794896619231321691639751 |
|||
06-04-2014, 09:33 PM
(This post was last modified: 06-04-2014 09:34 PM by pito.)
Post: #39
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
For users who are not happy with the trigo precision of their lovely calculators:
http://www.rskey.org/~mwsebastian/miscprj/results.htm |
|||
06-04-2014, 09:39 PM
(This post was last modified: 06-04-2014 09:40 PM by Claudio L..)
Post: #40
|
|||
|
|||
RE: @Thomas Klemm -> CORDIC Article
(06-04-2014 09:21 PM)pito Wrote: Wolfram alfa, 34digits (hopefully), rounded: Yes! We finally have the same answer, and since 2 matching answers is enough to define a mathematical truth, we can say that this is the correct number. Now I wonder what happened to your results: Quote:TRIG9 In particular the second one seems to be off by a lot (5 digits). Try to get partial results for each operation and compare with your latest list of partials from Wolfram to see what's going on. Claudio |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 2 Guest(s)