What is in the Sine table?
ksltd
Posts: 163
I can find no information in the manual about the format of the 16-bit unsigned values in the sine table. I'm presuming they're fixed point values, but where's the implied binary point? Is the data 1.15?
Comments
http://www.parallax.com/downloads/propeller-manual
Thanks for your response. If you read my post carefully, you'll see that it says "I can find no information in the manual about the format of the 16-bit unsigned values in the sine table". That includes the samples in Appendix B.
Neither the text nor the code snippet indicate the format of the data in the ROM and the code snippet doesn't indicate the format of the data that it returns.
I'm sure you're trying to be helpful - but there's just nothing there.
Perhaps someone who knows?
If you can read Forth, here are my fixed point trig functions:
\ begin of fixed point trig functions. \ Values for common angles in brad13 0016 constant DEGREE_ANGLE 0400 constant EIGHTH_ANGLE 0800 constant RIGHT_ANGLE 1000 constant STRAIGHT_ANGLE \ sin function using brads ( brad13 -- sin32 ) \ The sine table contains one quadrant, so we'll need to \ work around that when generating the index into the table. \ note use um* with the return value! : sin dup \ save a copy of input for later. dup RIGHT_ANGLE and if \ ranges from 800 to 001 negate FFF and else \ ranges from 000 to 7FF 7FF and then \ convert to word count and index into sin table 2* E000 + W@ \ bit shift to 32 bits for future um* F lshift \ use the sign from the preserved value. swap STRAIGHT_ANGLE and if negate then ; decimal \ cos defined in terms of sin by coordinate rotation. : cos RIGHT_ANGLE + sin ; \ tangent can be derived from sine / cos. Both sine and cos are \ fast table lookups, so this is only a division more expensive \ than sine. \ ( brad13 -- tan ) : tan dup sin swap cos \ Note that we shift the cos down because we only want the \ numerator shifted left! 15 asr/ / ; RIGHT_ANGLE sin constant MAX_SIN RIGHT_ANGLE negate sin constant MIN_SIN \ clamps n between max and min to prevent inverse trig function overflow \ ( n -- clamped_value ) : clamp MIN_SIN max MAX_SIN min ; \ compute asin via a binary search. \ Note: we're shifting angles up two bits to allow for greater \ precision during the search. It will be shifted back before return. \ ( sin - brad13 ) : asin clamp \ push the first approximation and correction 0 EIGHTH_ANGLE 4* \ refine approximation and correction iteratively 13 0 do \ move the correction to the bottom of stack. -rot \ compare the sine of the approximation to the value. 2dup 2/ 2/ sin > if \ The approximation is too small, add the correction. rot dup -rot + else \ The approximation is too large, so decrease it. rot dup -rot - then \ half the correction factor for next iterration. swap 2/ loop \ return only the approximation. drop swap drop 2/ 2/ ; \ acos is defined in terms of asin \ ( cos -- brad13 ) : acos asin RIGHT_ANGLE - negate ; \ 13-bit fixed point four-quadrant arctangent. Given Cartesian vector (x, y), \ finds the angle subtended by the vector and the positive x-axis. \ y a signed integer \ x a signed integer \ ( y x -- brad13 ) : atan2 \ Handle crossing x axis case dup 0= if drop RIGHT_ANGLE swap \ adjust sign based upon y's sign. 0< if negate then exit then \ save x to use its sign to adjust results dup -rot swap 15 lshift swap / \ push the first approximation and correction 0 EIGHTH_ANGLE 4* \ refine approximation and correction iteratively 13 0 do \ move the correction to the bottom of stack. -rot \ compare the sine of the approximation to the value. 2dup 2/ 2/ tan > if \ The approximation is too small, add the correction. rot dup -rot + else \ The approximation is too large, so decrease it. rot dup -rot - then \ half the correction factor for next iterration. swap 2/ loop \ return only the approximation. drop swap drop 2/ 2/ \ if x's sign was negative, then move results into 3 & 4 quadrants. swap 0< if STRAIGHT_ANGLE + then ; \ end of fixed point trig functions.Sine Table
The sine table provides 2,049 unsigned 16-bit sine samples spanning from 0° to 90°,
inclusively (0.0439° resolution). Sine values for all other quadrants covering > 90° to < 360°
can be calculated from simple transformations on this single-quadrant sine table. The sine
table can be used for calculations related to angular phenomena.
See Appendix B: Math Samples and Function Tables on page 380 for more information.
Th appendix says the same and has an example of how to extend that too the full 360 degrees.
I'm going to assume the value at position 0 in the table is 00000000_00000000 seeing as sine(0) = 1.
I'm going to assume the value at position 2048 is 11111111_11111111 as that is the biggest unsigned 16 bit value one can have. It must represent 1.0 as sine(90) = 1.
So effectively the binary point is in front of that 0.11111111_11111111
The right most bit, the LSB, therefore being 90 / 2048 = 0.0439 degrees as stated in the manual.
The procedure presented in the index will get you the full circle.
I might be wrong but a quick Spin program would verify it. All the info required seems to be there.
Think of it as the values in the table as 16 bit unsigned integers. The output values represent fractional sine values ranging from 0 to 65535/65536 for values in the first quadrant. Effectively fixed point radix to the left of the 16th bit.
Here is a Spin program that prints out values at intervals around the full circle. The FullSine method takes an angle\ from 0 to 8191 and returns the sine of that angle as an integer from -65535 to +65535. Those values represent sines from -65535/65536 to +65535/65536. The program also converts the result into decimal, 4 digits precision.
[FONT=courier new] [/FONT][SIZE=1][FONT=courier new]CON _CLKMODE = XTAL1 + PLL16X _XINFREQ = 5_000_000 VAR OBJ pst : "parallax serial terminal" PUB basicSine | angle, sine pst.start(9600) waitcnt(clkfreq/10+cnt) pst.str(string("top",13)) repeat angle from 0 to 8192 step 256 ' step through the angles represnting circle, 360 degrees sine:=fullsine0(angle) ' this does the lookup in the hub sine table and adjust for quadrant ' show results... pst.dec(angle) pst.chars(32,5) pst.dec(angle>>11) ' quadrant pst.chars(32,5) pst.dec(sine) ' returned sine value, range -65535 to 65535 pst.chars(32,5) sine := 20000 ** (sine << 15) ' convert to decimal, 4 digits pst.chars(32,5) pst.dec(sine/10000) pst.char(".") pst.dec(sine//10000) pst.char(13) waitcnt(clkfreq/20+cnt) repeat PUB fullsine0(angle) | q ' angle is 13 bits, 0 to 360 degrees q := angle >> 11 ' quadrant, 0 to 3 angle := (angle & $7ff) << 1 ' 0 to 90- degrees, adjust to 11 bits case q ' by quadrant, shift for word address 0 : result := word[$E000 + angle] ' 1 : result := word[$F000 - angle] 2 : result := -word[$E000 + angle] 3 : result := -word[$F000 - angle] return[/FONT][/SIZE]It's definitely not indexed by radians, it's indexed by 1/2048ths of degrees. That much is explained in the manual.
Heater,
If all the information were there, believe me, I'd not have asked the question. And, I'd imagine that your explanation wouldn't be couched in two assumptions and the ubiquitous "I might be wrong".
Tracy,
So you're saying values in the table are in 0.16 fixed point format and your program takes Angles in degrees with the LSB equal to 90/2048 degrees and only works for angles in the range 0..360. Got it. Thanks.
http://forums.parallax.com/showthread.php/156866-Question-for-Chip-re-ROM-code
Radians or degrees it makes on difference.
What we have here is 2049 numbers representing the value of the sine function over one quarter of a full rotation.
What the manual clearly states is "...2,049 unsigned 16-bit sine samples spanning from 0° to 90°,
inclusively (0.0439° resolution)".
One could just as well say "...2,049 unsigned 16-bit sine samples spanning from 0 to PI/2 radians,
inclusively (0.0007666 radian resolution)".
Same thing.
We see that all the information is indeed in the manual.
Yes I'm fond of the "I might me wrong". Perhaps we find that the manual has errors or omissions on this point, would not be the first time. Perhaps the ROM in the Propeller is wrong, unlikely. Perhaps my own understanding or arithmetic has slipped up, that certainly would not be a first.
Finally given the information in the manual, which turns out to be correct and complete, it would only take a five minute experiment to dump out the values and check ones understanding.
I said binary radian, not radian. It's a common technique for representing trig functions with integers. See this article:
http://en.wikipedia.org/wiki/Binary_scaling
Sort of. Implementation of trig functions always involves clever folding, scaling and range reduction. My snippet of a program does the calculation in brads (as Martin_H said, binary radians) with the full circle broken into 8192 segments. It is easy enough to convert that to units of degrees or radians if that is what is required. Range extension too is easy, if required. The 11 bit precision going in is less than the 16 bit precision coming out, so the 0.16 fixed point format is a bit deceptive unless you also implement interpolation, as is done in the floating point packages. I can see it as 0.16 fixed point, but I think of it first as a dimensionless ratio of integers apart from any particular number system or scale factor.
Erna A poet as always!
Here's an object I wrote that uses the Sin table in Spin.
Most functions take a radius argument. The radius argument is necessary to scale the sin value output to be an integer number. Otherwise a value of -1 to 1 would be returned. Generally, just call the functions with the radius value set to something large. Like 100 or 1000.
2049 sounds like an odd value to me. Is it a typo?
Sandy
Imagine you wanted to plot a graph of some function, y = f(x), over the range x >= 0, x >= 10. And you only had values of y for integer values of x, x = 0,1,2,3,4,5,6,7,8,9,10
See, we have 11 points to plot not just 10. This is a "fence post" problem. There is one more fence post that the number of gaps between the posts to cover a particular length of fence.
So it goes with the table of sin(x) in the PROM.
I think you're right.
I got bored and wrote a little program to dump the contents of the sine table. The results are included as Sine Table Dump.txt in the archive. I had to do in in three goes because otherwise the results would be clipped in the debug window. The debug window contents were copied into Sine Table Dump.txt after each program run.
After word number 2048 ( address F000 to F001 ) the numbers are obviously wrong.
Sandy
The sine table addresses are from $E000 to $F001 and the booter/interpreter addresses are $F002 to $FFFF.
See page 31 in the Propeller manual (Memory map)
Yes, this is indeed correct and a special accommodation of 2049 entries in order to make the use of binary radians deploy easily. At some point, the use of the table requires one to learn what a 'binary radian' is and how to use it with binary maths. The Table is intended to allow optimal programing in binary maths, not floating point or fixed point.
Search on BRADs...
http://en.wikipedia.org/wiki/Binary_scaling
Which works perfectly. I just cut and pasted two PUBs (Sin and Cos) and two PRI helper methods (one scales the radius and one does the actual lookup) and LoAndBehold: an analog clock!