Angles don't map nicely to two's complement turns 
Author Message
 Angles don't map nicely to two's complement turns

If you use n bits to represent a signed two's complement number, the
range is  [-1,1) in 2^n steps of 2^(1-n) (times whatever scale factor
you like).

It would be nice to have the range [-pi,pi) correspond to the above
sometimes, especially if i/o is interfacing with shaft position
encoders using such angle representation. Or if you just want
to use exact rational numbers to represent exact points in the two-pi
sweep. [0,2pi) or [-pi,pi) seem easiest to deal with. What does the
IEEE floating point standard say? My Pentium book says the FPATAN
instruction computes the arctangent of ST(1)/ST, returns the value
to ST(1), and pops ST. The result has the same sign as the operand
from ST(1), and a magnitude *less* than pi. That says (-pi,pi) to me,
or maybe [-pi,pi] if you treat the largest magnitude as pi. Either
way, it wouldn't seem to be biasing what scheme should do. Or is there
something else driving the scheme choice?

It seems that scheme (R5) defines angles ranging (-pi,pi] instead:

        "...In general, the mathematical functions log, arcsine,
        arccosine, and arctangent are multiply defined. The value of
        log z is defined to be the one whose imaginary part lies in
        the range from -pi (exclusive) to pi (inclusive). log 0 is
        undefined. With log defined this way, the values of sin^-1 z,
        cos^-1 z, and tan^-1 z are according to the following
        formulae: ..."
and

        "...(angle z)                              ==> x_angle
                where -pi < x_angle <= pi with x_angle = x4 + 2pi n
        for some integer n. ..."

Comments?

Regards,
Bengt Richter



Thu, 25 Sep 2003 15:37:43 GMT  
 Angles don't map nicely to two's complement turns


Perhaps the other title not indicative enough?
Wondering if anyone else noticed or was affected
by this issue.

If I quote the whole thing here, it will probably
get bounced as having too high a proportion of
quoted material. OTOH, maybe I should just have
appended (fib 5000) as filler ;-/



Mon, 29 Sep 2003 04:11:15 GMT  
 Angles don't map nicely to two's complement turns

Quote:

> If you use n bits to represent a signed two's complement number, the
> range is  [-1,1) in 2^n steps of 2^(1-n) (times whatever scale factor
> you like).

> It would be nice to have the range [-pi,pi) correspond to the above
> sometimes, especially if i/o is interfacing with shaft position
> encoders using such angle representation. Or if you just want
> to use exact rational numbers to represent exact points in the two-pi
> sweep. [0,2pi) or [-pi,pi) seem easiest to deal with.
> It seems that scheme (R5) defines angles ranging (-pi,pi] instead:

To map [-pi,pi) to signed n-bit integers, you would multiply by
2^(n-1)/pi.  To map (-pi,pi] to signed n-bit integers, you multiply by
-2^(n-1)/pi.  Is this really that much less convenient?

As for the history, I believe the convention of (angle -1) being
positive has precedent in mathematics that predates the dawn of
computer science, but I can't back that up.

If you want more bitwise justification, consider the fact that in the
world of two's complement, zero has more in common with positive
numbers than with negative numbers, and the (-pi,pi] range corresponds
to the simple rule that the angle's sign bit is the same as the
imaginary part's sign bit.

What does bother me about the r5rs specification for angle is that it
fails to state what (angle 0) should be.

-al



Mon, 29 Sep 2003 05:58:42 GMT  
 Angles don't map nicely to two's complement turns
On 11 Apr 2001 14:58:42 -0700, Alps Petrofsky

Quote:


>> If you use n bits to represent a signed two's complement number, the
>> range is  [-1,1) in 2^n steps of 2^(1-n) (times whatever scale factor
>> you like).

>> It would be nice to have the range [-pi,pi) correspond to the above
>> sometimes, especially if i/o is interfacing with shaft position
>> encoders using such angle representation. Or if you just want
>> to use exact rational numbers to represent exact points in the two-pi
>> sweep. [0,2pi) or [-pi,pi) seem easiest to deal with.

>> It seems that scheme (R5) defines angles ranging (-pi,pi] instead:

>To map [-pi,pi) to signed n-bit integers, you would multiply by
>2^(n-1)/pi.  To map (-pi,pi] to signed n-bit integers, you multiply by
>-2^(n-1)/pi. Is this really that much less convenient?

Yes, if it doesn't work ;-)

If you're getting input from a shaft encoder that produces signed
two's complement binary to represent a turn of a shaft, half of
the shaft's angles will be encoded with the sign bit set and the
other half not set. So in general, the encodings of angles pi
apart will have opposite signs, whatever the binary resolution.
Meaning 0 and pi encodings have opposite signs, and so pi has
a unique representation as -2^(n-1) for n-bit signed integers.

On output, you could multiply an angle by 2^(n-1)/pi even for
scheme's angles (-pi,pi], if you can do it in a way that ignores
overflow for the bit pattern for 2^(n-1), since that gets you
-2^(n-1) as desired, without changing the signs of the other values.
( Multiplying by -2^(n-1)/pi wouldn't be less convenient, but it
wouldn't give the desired encoding for the other values).

On input, pi will come in as -2^(n-1), and scaling will give you -pi,
so if any of scheme's functions depend on getting +pi rather than -pi,
there might be a problem.

I could see wanting to maintain angles as integers modulo 6 for
walking around in a hexagonal tiling without accumulating roundoff
errors. It would seem to me the natural transformation when radians
were needed would be 2*pi*(ang-3)/6, which would give you [-pi,pi),
not (-pi,pi].

Quote:
>As for the history, I believe the convention of (angle -1) being
>positive has precedent in mathematics that predates the dawn of
>computer science, but I can't back that up.

I guess it goes back to e^(i*t) mapping the real axis to the unit
circle. pi and -pi both map to the same point (-1,0i) I think,
so you have a choice for angle(-1,0i) [i.e., angle(-1)]. What
choice is reasonable, pi or -pi? I think it depends on what you
are going to consider your primary 2*pi interval (that you are
going to add k*2*pi to to generate all the points on the real axis).
I think you need a half-open interval, and I think the conventional
choices would be [0,2*pi)+k*2*pi or that translated by pi, namely
[-pi,pi)+k*2*pi. Both pi and -pi aren't going to be included
in the primary interval. I don't know how to define a constant
for the translation from [0,2*pi) to (-pi,pi].

Exactly pi seems the most reasonable translation to me. So scheme's
angle interval does not feel right to me. If you go with [0,2*pi) and
thence by pi to [-pi,pi), angle(-1) should be -pi and other results
should also be in [-pi,pi), IMHO.

Quote:
>If you want more bitwise justification, consider the fact that in the
>world of two's complement, zero has more in common with positive
>numbers than with negative numbers, and the (-pi,pi] range corresponds
>to the simple rule that the angle's sign bit is the same as the
>imaginary part's sign bit.

I think that's kind of a red herring, or maybe worse. My gut feeling
is queasiness ;-) I think the selection of points on the unit circle
to correspond to a sequence of integers is the best focus. If you
space 2^n points evenly around the unit circle starting at (1,0i),
the rest follows, and you get interval [-pi,0) containing the negative
angle points and interval [0,pi) containing positive angle points,
nice and symmetrically.

Quote:
>What does bother me about the r5rs specification for angle is that it
>fails to state what (angle 0) should be.

Hm, when would (angle 0) not be an error?


Mon, 29 Sep 2003 13:27:44 GMT  
 Angles don't map nicely to two's complement turns

Quote:

> So scheme's angle interval does not feel right to me.

It's a mostly arbitrary convention.  If you want more justification,
perhaps you should check the Penfield paper cited in r5rs (I haven't
read it, so I'm not sure of whether it provides any insight).

If you want to use a different convention, then go ahead and implement it:

  (define (my-angle z) (if (real? z) (- (angle z)) (angle z)))

Alternatively, you can map between your signed n-bit angles and
standard scheme angles like so:

  (define (n-bit-angle->scheme-angle n-bit-angle)
    (if (= n-bit-angle (- (expt 2 (- n 1))))
        (angle -1)
        (* (angle -1) (/ n-bit-angle (expt 2 (- n 1))))))

  (define (scheme-angle->n-bit-angle scheme-angle)
    (let ((n-bit-angle (round (* (expt 2 (- n 1))
                                 (/ scheme-angle (angle -1))))))
      (if (= n-bit-angle (expt 2 (- n 1)))
        (- n-bit-angle)
        n-bit-angle)))

Quote:
> >What does bother me about the r5rs specification for angle is that it
> >fails to state what (angle 0) should be.

> Hm, when would (angle 0) not be an error?

In common lisp, it's zero.  In r5rs, I can't tell if it's an error
(meaning the interpreter is free to blow up), or if it's guaranteed to
return some value in the (-pi, pi] interval, or what.  The
specification for expt spells out the what the deal is for 0^0, but
the specification for angle is self-contradictory.  It says that the
angle of 0*e^0 is 0 and the angle of 0*e^1 is 1, even though 0*e^0 and
0*e^1 are the same number (zero).

-al



Mon, 29 Sep 2003 15:49:40 GMT  
 Angles don't map nicely to two's complement turns
On 12 Apr 2001 00:49:40 -0700, Alimony Petrofsky

Quote:


>> So scheme's angle interval does not feel right to me.

>It's a mostly arbitrary convention.  If you want more justification,
>perhaps you should check the Penfield paper cited in r5rs (I haven't
>read it, so I'm not sure of whether it provides any insight).

I googled all over the place, and found many references to the
Penfield paper, but couldn't find the paper itself. Common lisp
discussions and docs cite it also, but nothing I found had a link
to the actual paper. Even citeseer (http://citeseer.nj.nec.com/ --
a *nice* documentation search site BTW) didn't turn it up.

I'd appreciate a link if anyone has one. I find it strange that a
defining document for both CL and scheme is not easily available.
Will I have to order hard copy from ACM archives? (ACM's search
is apparently overloaded when I tried it, but the APL sig doesn't
list the proceedings/quad issue with its more recent ones.

Looking for either of (as cited in his own pubs list):

534.Paul Penfield, Jr., "Principal Values and Branch Cuts in Complex
APL," APL Quote Quad, vol. 12, no. 1, pp.
      248-256; September, 1981.

536.Paul Penfield, Jr., "Principal Values and Branch Cuts in Complex
APL," APL 81 Conference Proceedings,
      San Francisco, California, pp. 248-256; October 21-23, 1981.



Tue, 30 Sep 2003 01:29:23 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. Two's complement and -32768

2. Two's Complement

3. Two's Complement Shifter Code

4. Two's Complement Multiplication in Verilog

5. 16-bit Two's complement Multiplier

6. Two's complement signed binary addition and subtraction

7. Another Question on Two's Complement

8. two's complement

9. Help converting hex string to 16-bit signed two's complement integer

10. Why don't my textures map correctly?

11. Two SET constants I don't know

12. HELP: Porting MacPython to MPW SIOW - CR's sometimes turn to LF's

 

 
Powered by phpBB® Forum Software