Cordic object
Graham Stabler
Posts: 2,507
I'm still working on my Cordic engine, it is based on this website:
www.voidware.com/cordic.htm
It uses a generalized loop and function for each operation that sets the various parameters.
So far I have the Rsin(theta), Rcos(theta) and the cartesian to polar conversion working and have just done atan.
Doing the atan got me thinking. tan(theta) = o/a so you pass the function o/a and it computes theta. The way it does this is to set the x component to 1 and to try and make the y component equal the passed value.
Origionally I coded it so that the value passed was scaled up by shifting the bits to well fill the 32 bits before scaling by the factor K, the value one was also scaled up by the same number of bit shifts. Using bigger numbers seems to result in a better value for theta as it did in the RsinRcos code.
But then I realized, what about arguments less than one? I'm assuming integer maths here and the argument could be anything from 0 to infinity. My solution has been to have two arguments to the function, one the o/a value and the other the value for one. So if you have one decimal place in your integer maths, you use 10 as your value for one. This seems to work quite well.
What I'm not sure about is:
1) Is my scaling by bit shifting a good way to make the numbers big and is there a more efficient way than just looping?
2) How does my variable one sound as an idea?
Personally I don't have an application for some of the trigometric functions so it is hard to imagine how they will be used in practise and this is causing a few problems in the implementation.
Cheers,
Graham
www.voidware.com/cordic.htm
It uses a generalized loop and function for each operation that sets the various parameters.
So far I have the Rsin(theta), Rcos(theta) and the cartesian to polar conversion working and have just done atan.
Doing the atan got me thinking. tan(theta) = o/a so you pass the function o/a and it computes theta. The way it does this is to set the x component to 1 and to try and make the y component equal the passed value.
Origionally I coded it so that the value passed was scaled up by shifting the bits to well fill the 32 bits before scaling by the factor K, the value one was also scaled up by the same number of bit shifts. Using bigger numbers seems to result in a better value for theta as it did in the RsinRcos code.
But then I realized, what about arguments less than one? I'm assuming integer maths here and the argument could be anything from 0 to infinity. My solution has been to have two arguments to the function, one the o/a value and the other the value for one. So if you have one decimal place in your integer maths, you use 10 as your value for one. This seems to work quite well.
What I'm not sure about is:
1) Is my scaling by bit shifting a good way to make the numbers big and is there a more efficient way than just looping?
2) How does my variable one sound as an idea?
Personally I don't have an application for some of the trigometric functions so it is hard to imagine how they will be used in practise and this is causing a few problems in the implementation.
Cheers,
Graham
Comments
This came from discussions with Peter Verkaik when he was also developing CORDIC ofor the Javalin Stamp, and the discussion of the errors in in this thread... http://forums.parallax.com/showthread.php?p=563729
The numerical value to stand for unity will be quite application specific, I believe.
I meant to get to the hyperbolic functions, if only to get to the log and exponential, if not just for fun (?!), but it is still on the back burner. It was interesting what the voidware site had to say about the history in relation to the HP calculator, wondering why they didn't put the hyperbolic functions on the keypad. I know I would never have worn out that key! Last week I ran into a problem we are working on that turned out to have a hyperbolic solution. It is the effect of an electric field on an ionized gas, where the resistance to ion motion is proportional to the square of velocity.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com
The exponential functions need just a slightly different loop, the effort is in the wrappers it seems, making sure that the results are robust and useful. This issue of what one actually equates too is really interesting and is something calculators based on interger maths must deal with quite cleverly.
Graham
I can't access the site http://www.voidware.com/cordic.htm today. I'll try again tomorrow and I don't know squat about cordic methods. I tried to read the stuff posted on other threads... I think by Chip...but the logic just didn't tickle my hippocampus in the right way.
There is (of course) an entirely different way to do math... by treating numbers as variable length strings and then creating the operators and functions that you need from there.
The only thing is with my current state of Spin knowledge if I were to try to actually do that right now, I would be up a creek with a very short paddle.
I needled the Forth guys a little and got enough of an answer to indicate that you could probably eliminate this kind of scoping problem by using a minimally abstracted language... like Forth.
(AND you wouldn't have to treat numbers like strings!!!)
I would be interested in your opinion... have you looked at Forth? And if so, what did you think?
Rich
http://en.wikipedia.org/wiki/Hippocampus
Rgds,
······ Quattro
·
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
'Necessity is the mother of invention'
Post Edited (QuattroRS4) : 4/1/2007 11:42:27 PM GMT
Graham
There are theoretical reasons to treat numbers as string: unlimited precision and the elimination of math functions from the machine code level.
Everything is handled by lists and logic. In theory, you could build a microprocessor that would have no numerical bit limits, and the processor would not necessarily require an arithmetic ADD code.
Rich
Why don't you get reading the spin manual, grow your paddle!
Graham
It is a credit to you that you saw that it was necessary. Most of the references I have do not say much or anything about the range reductions requrired. For example, Turner's Guide to Numerical Analysis posits a convergence domain of [noparse][[/noparse]-2,2], and notes that from that one can cover the entire real line (being the ratio y/x) . And "this range remains sufficient since we can scale both coordinates by an approprieate binary exponent." But he also throws in, "We do not concern ourselves with the detais here".
The choice remains rather arbitrary of where where to place the binary radix point and what value to use as unity. For atan it could be scaled over to just in front of bit 30 in a long. That carries along the maximum precision through the calculation. The magnitude can then slew up to 2.83 = 2*sqr(2) maximum, and that would have to be scaled back by undoing the scale factor. On the other hand, for some purposes a binary radix just in front of bit 24 would be convenient, to merge with floating point methods. Math is always a detailed undertaking, no matter how we string it out; hardly ever a song and a prayer.
The hyperbolic functions sinh z and cosh z have a convergence domain of z < 1.74. Also, they only converge at all points only if certain iterations are repeated twice, for index=1, 4, 13, 40.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com
Tracy, you know the pdf "A survey of CORDIC algorithms for FPGAs" it shows the same algorithm for doing linear operations as the voidware website. Neither of which are as far as I can tell correct. They say:
xi+1 = xi (x value does not change and is the first argument of the multiply)
yi+1 = yi + xi.di.2^-i (y starts as zero and ends up with result in)
zi+1 = zi - di.2^-i (z contains other argument of multiply)
where di determines if it is added or otherwise and is decided based on z's value compared to zero.
the thing is if you take a multiplication like 10X10, x = 10, z1 = 10 then even if D was positive for every interation y would end up being no larger than 20.
So in my little test spreadsheet I changed 2^-1 to z1.2^-i and this works but it seems as if I must be missing something as both sources quote the same equations and I am not sure hw robust my cheat is.
I have attached my spreadsheet.
Graham
I don't have time to look at it right now, but there must be a good explanation for the apparent discrepancy! I'm posting just to point to another reference. The book by Turner I was thinking of is actually titled Guide to Scientific Computing, and as luck would have it, the chapter that includes the CORDIC is available for download from the publisher at, www.palgrave.com/products/Catalogue.aspx?is=0333794508. He has nice explanations and example code (in MATLAB) for all three main CORDIC modes. Another resource to compare with the others.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com
Yes it all became clear, both multiply and divide work as long as the end result is less than 2!
Again the devil is in the detail and I need to give this all a bit more thought.
Graham
Graham