Re: [pygame] exact algebraic numbers?
Michael George wrote:
Greg Ewing wrote:
But the back of my envelope is not wide enough
to accommodate any more of this.
A little bit further and you would have seen the fail: sqrt(3) *
sqrt(6) = 3 * sqrt(2) and we're back where we started. However my
algebra book assures me (non-constructively) that {1, sqrt(2),
sqrt(3), sqrt(6)} is a basis for the smallest field over the rationals
containing sqrt(2) and sqrt(3), so it should be possible to divide. I
just have to chase the proofs backwards to figure out how. I'll let
you know.
In the end the solution came out rather nicely. Here's my
implementation (sans comparisons) for anyone who is interested.
--Mike
import fractions
from math import sqrt
FLOAT_SQRT2 = sqrt(2)
FLOAT_SQRT3 = sqrt(3)
FLOAT_SQRT6 = sqrt(6)
class Number(object):
"""
Represents a number of the form [a1 + a2*sqrt(2) + a3*sqrt(3) + a6*sqrt(6)]/d, where ai and d are integers
"""
__slots__ = ['a1', 'a2', 'a3', 'a6', 'd']
def __init__(self, a1=0, a2=0, a3=0, a6=0, d=1):
self.a1 = a1
self.a2 = a2
self.a3 = a3
self.a6 = a6
self.d = d
self.reduce()
def __copy__(self):
return Number(self.a1, self.a2, self.a3, self.a6, self.d)
#
# string conversions
#
def __repr__(self):
return 'Number(%d,%d,%d,%d,%d)' % tuple(self)
def __str__(self):
return '[%d%+d*sqrt(2)%+d*sqrt(3)%+d*sqrt(6)]/%d' % tuple(self)
def __unicode__(self):
return u'[%d%+d\u221a2%+d\u221a3%+d\u221a6]/%d' % tuple(self)
#
# comparison operators
#
def __eq__(self, other):
a1, a2, a3, a6, ad = self
b1, b2, b3, b6, bd = other
return ad*b1 == bd*a1 \
and ad*b2 == bd*a2 \
and ad*b3 == bd*a3 \
and ad*b6 == bd*a6
def __neq__(self, other):
return not self.__eq__(other)
def __cmp__(self, other):
# TODO
return NotImplemented
def __nonzero__(self):
return self.a1 != 0 \
or self.a2 != 0 \
or self.a3 != 0 \
or self.a6 != 0
#
# sequence operators
#
def __iter__(self):
return iter((self.a1, self.a2, self.a3, self.a6, self.d))
#
# arithmetic operators
#
def __add__(self, other):
a1, a2, a3, a6, ad = self
b1, b2, b3, b6, bd = other
return Number(bd*a1 + ad*b1,
bd*a2 + ad*b2,
bd*a3 + ad*b3,
bd*a6 + ad*b6,
ad*bd)
def __sub__(self, other):
return self + (-other)
def __mul__(self, other):
a1, a2, a3, a6, ad = self
b1, b2, b3, b6, bd = other
c1 = a1*b1 + 2*a2*b2 + 3*a3*b3 + 6*a6*b6
c2 = a1*b2 + a2*b1 + 3*a3*b6 + 3*a6*b3
c3 = a1*b3 + 2*a2*b6 + a3*b1 + 2*a6*b2
c6 = a1*b6 + a2*b3 + a3*b2 + a6*b1
cd = ad*bd
return Number(c1, c2, c3, c6, cd)
def __div__(self, other):
return self * other.inv()
def __radd__(self, other):
return self + other
def __rsub__(self, other):
return (-self) + other
def __rmul__(self, other):
return self * other
def __rdiv__(self, other):
return self.inv() * other
def __neg__(self):
return Number(-self.a1, -self.a2, -self.a3, -self.a6, self.d)
def __pos__(self):
return self
def __abs__(self):
# TODO
pass
def __complex__(self):
return complex(self.__float__())
def __float__(self):
return self.a1 + self.a2*FLOAT_SQRT2 + self.a3*FLOAT_SQRT3 + self.a6*FLOAT_SQRT6
#
# helper functions
#
def conj2(self):
"""conjugate the sqrt(2) portion"""
return Number(self.a1, -self.a2, self.a3, -self.a6, 1)
def conj3(self):
"""conjugate the sqrt(3) portion"""
return Number(self.a1, self.a2, -self.a3, -self.a6, 1)
def inv(self):
factor1 = self.conj2()
current = self * factor1
assert current.a2 == current.a6 == 0
factor2 = current.conj3()
current = current * factor2 # = self * factor1 * factor2
assert current.a2 == current.a3 == current.a6 == 0
return Number(current.d, 0, 0, 0, current.a1) * factor1 * factor2
def reduce(self):
gcd = reduce(fractions.gcd, self)
self.a1 = self.a1 / gcd
self.a2 = self.a2 / gcd
self.a3 = self.a3 / gcd
self.a6 = self.a6 / gcd
self.d = self.d / gcd
NMBR1 = Number(1,0,0,0,1)
SQRT2 = Number(0,1,0,0,1)
SQRT3 = Number(0,0,1,0,1)
SQRT6 = Number(0,0,0,1,1)
Re: [pygame] exact algebraic numbers?
Greg Ewing wrote:
But the back of my envelope is not wide enough
to accommodate any more of this.
A little bit further and you would have seen the fail: sqrt(3) * sqrt(6)
= 3 * sqrt(2) and we're back where we started. However my algebra book
assures me (non-constructively) that {1, sqrt(2), sqrt(3), sqrt(6)} is
a basis for the smallest field over the rationals containing sqrt(2) and
sqrt(3), so it should be possible to divide. I just have to chase the
proofs backwards to figure out how. I'll let you know.
As for libraries dealing with this kind of stuff, there
might be something in Sage. But you're probably not going to
want to bolt Sage into your game...
Ah, I'd not seen sage, that looks cool. I agree though, prolly don't
want it as part of my game :).
--Mike
Re: [pygame] exact algebraic numbers?
Michael George wrote: I'm trying to implement a game that allows dragging of objects while maintaining the fact that they do not intersect one another. I want to be able to drag one object so that it abuts another. Another way to approach this is to allow a tolerance when deciding whether two objects abut. If the tolerance is less than a pixel, the player won't be able to tell the difference. a + b*sqrt(2) + c*sqrt(3) + d*sqrt(6). These are closed under multiplication and addition, still not sure about division Hmm. Possibly it might be, although the formulas are going to get pretty horrendous. For example, a quick calculation shows that 1 / (a + b*sqrt(2)) = (a - b*sqrt(2)) / (a*a-2*b*b) which you can get by multiplying top and bottom by (a - b*sqrt(2)). Attempting the first stage of a similar trick using the full form, I got (a + b*sqrt*(2) + c*sqrt(3) + d*sqrt(6)) * (a - b*sqrt(2)) = (a*a-2*b*b) + (a*c-2*b*d)*sqrt(3) + (a*d-b*c)*sqrt(6) This no longer contains a sqrt(2) term, which is encouraging. Presumably one could then go on to multiply this by (a*a-2*b*b) - (a*c-2*b*d)*sqrt(3) to eliminate the sqrt(3) term, and then E - F*sqrt(6) for some E and F to be determined. But the back of my envelope is not wide enough to accommodate any more of this. As for libraries dealing with this kind of stuff, there might be something in Sage. But you're probably not going to want to bolt Sage into your game... -- Greg
Re: [pygame] exact algebraic numbers?
Hi Mike, Such algebraic numbers are used in computational geometry, you can take a look at CGAL http://www.cgal.org, it's a powerfull Computational geometry written in C++ (a python binding exists) and it has an algebraic kernel for exact computation of points on a circle or on a sphere. I'm not sure that it includes the transformations because it is done to maintain data structures like meshes, etc... Well you have to see if it suits your need and if the effort of installing it is woth it! Regards. Olivier 2009/11/29 René Dudfield > On Sun, Nov 29, 2009 at 5:59 AM, Michael George > wrote: > > > > Hello, > > > > For my game I need to represent right isosceles triangles, and do > operations including translation and rotation in 15 degree increments. > Unfortunately, I cannot tolerate rounding error, because it will cause bad > visual and gameplay artifacts. I'm thinking of representing points as > vectors where the components are of the form > > > > a + b * sqrt(2) + c * sqrt(3) + d * sqrt(6) > > > > where a, b, c, and d are rationals. I believe numbers of this form are > sufficient for my purposes, although I haven't worked out all the proofs > yet. Anyway, I was wondering if anyone has done anything similar and can > suggest a library I can use for manipulating such vectors before I go off > and implement it myself. > > > > Thanks! > > > > --Mike > > > hi, > > python 2.6 and 3.1 have a fractions module: > http://docs.python.org/library/fractions.html > > The Fraction class inherits from the abstract base class numbers.Rational: >http://docs.python.org/library/numbers.html#numbers.Rational > > To avoid rounding (and other numerical) errors, the typical technique > is to apply the transformations each time from the identity matrix. > So in a game where a rotation happens at say 1.0 - 1.444 degrees each > frame, you keep count of the total rotation (eg 1.444) and apply the > total rotation every frame. Rather than applying the 1.0 rotation one > frame, and then applying the 1.444 rotation the next frame. Over > 10,000 frames or so, you can see there would be little rounding error. > > You can also use integers instead of floats, but divide the value by > 1,000,000 or so. eg, 1.444 degrees could be 1,444,000. Then as you > do not get the floating point problems. If all of your angles are > between 0-360, and the angle increments are also small it turns out > ok. Python has a long type, so you can get a lot of precision this > way, and avoid floating point problems somewhat. Just before you use > the rotation, you can divide the number by 1,000,000 or so(1444000 / > 100 == 1.444). > > > cu. > -- Rouiller Olivier 06 79 66 89 63 Résidence Léonard de Vinci App. A008 59650 Villeneuve d'Ascq
Re: [pygame] exact algebraic numbers?
DR0ID wrote: Michael George schrieb: Hello, For my game I need to represent right isosceles triangles, and do operations including translation and rotation in 15 degree increments. Unfortunately, I cannot tolerate rounding error, because it will cause bad visual and gameplay artifacts. I'm thinking of representing points as vectors where the components are of the form a + b * sqrt(2) + c * sqrt(3) + d * sqrt(6) where a, b, c, and d are rationals. I believe numbers of this form are sufficient for my purposes, although I haven't worked out all the proofs yet. Anyway, I was wondering if anyone has done anything similar and can suggest a library I can use for manipulating such vectors before I go off and implement it myself. Thanks! --Mike Hi I don't think that you can avoid rounding errors, unless you use a math library that takes the math errors of the computer into account (which can differ from hardware to hardware). I'm not sure, why you want to represent points in such a complicated way, but I don't know the theory about it and I'm not a mathematician. One way to go is to accumulate the angle of a rotation (same for translation) and use the accumulated angle on a object to transform it into the right orientation (if you do use a previously rotated object then you will get much more rounding errors over time!). Using that way one would have a variable 'angle' which would be incremented in 15 degree steps (15, 30, 45,...) and use it to construct the rotation matrix (or whatever it is used to rotate). This should be precise enough. Unless you can draw using subpixels, you will have rounding errors when trying to draw the points on integer coordinates of the screen anyway. Maybe I'm wrong. ~DR0ID For the curious: The reason I need exact arithmetic is not for drawing, but for collision response. I'm trying to implement a game that allows dragging of objects while maintaining the fact that they do not intersect one another. I want to be able to drag one object so that it abuts another. So if a user surrounds one object with other objects, then drags the center object away, I want them to be able to "pop" it back into the hole. If there's rounding errors, then it won't necessarily fit. That's the easiest example, but I'm pretty sure there are others where things won't work right. In this case, I'm dealing with very specific shapes, namely right triangles with legs of length 1. Those can be represented with integer coordinates ((0, 0), (0,1), (1,0)). However it turns out my snapping algorithm requires division, so I need rational numbers. So far, so good. But if you rotate a triangle by 45 degrees, you start needing to deal with sqrt(2) in the coordinates. For example, ((0,0), (sqrt(2)/2, sqrt(2)/2), (-sqrt(2)/2)). Luckily, numbers of the form a + b*sqrt(2) are good enough for this case, and you can still divide them exactly using integer arithmetic! Similarly, you may recall from high school geometry (I had to look it up) that a cos 30 = sqrt(3)/2. So if I allow rotation by 30 degrees, then I can represent those by a + b*sqrt(3). But it turns out that composing rotations requires multiplication, so to get 15 degrees for example, you can rotate by 45 and then back by 30, and multiplying it out you get ((0,0), (sqrt(2) + sqrt(6), -sqrt(2) + sqrt(6))/4, [left for reader]). So in general, you can represent all of the points on the unit circle in 15 degree increments using only integer arithmetic using the form a + b*sqrt(2) + c*sqrt(3) + d*sqrt(6). These are closed under multiplication and addition, still not sure about division (you might need quotients of these things in general, or worse). I need to relearn my abstract algebra. --Mike
Re: [pygame] exact algebraic numbers?
On Sun, Nov 29, 2009 at 5:59 AM, Michael George wrote: > > Hello, > > For my game I need to represent right isosceles triangles, and do operations > including translation and rotation in 15 degree increments. Unfortunately, I > cannot tolerate rounding error, because it will cause bad visual and gameplay > artifacts. I'm thinking of representing points as vectors where the > components are of the form > > a + b * sqrt(2) + c * sqrt(3) + d * sqrt(6) > > where a, b, c, and d are rationals. I believe numbers of this form are > sufficient for my purposes, although I haven't worked out all the proofs yet. > Anyway, I was wondering if anyone has done anything similar and can suggest > a library I can use for manipulating such vectors before I go off and > implement it myself. > > Thanks! > > --Mike hi, python 2.6 and 3.1 have a fractions module: http://docs.python.org/library/fractions.html The Fraction class inherits from the abstract base class numbers.Rational: http://docs.python.org/library/numbers.html#numbers.Rational To avoid rounding (and other numerical) errors, the typical technique is to apply the transformations each time from the identity matrix. So in a game where a rotation happens at say 1.0 - 1.444 degrees each frame, you keep count of the total rotation (eg 1.444) and apply the total rotation every frame. Rather than applying the 1.0 rotation one frame, and then applying the 1.444 rotation the next frame. Over 10,000 frames or so, you can see there would be little rounding error. You can also use integers instead of floats, but divide the value by 1,000,000 or so. eg, 1.444 degrees could be 1,444,000. Then as you do not get the floating point problems. If all of your angles are between 0-360, and the angle increments are also small it turns out ok. Python has a long type, so you can get a lot of precision this way, and avoid floating point problems somewhat. Just before you use the rotation, you can divide the number by 1,000,000 or so(1444000 / 100 == 1.444). cu.
Re: [pygame] exact algebraic numbers?
Michael George schrieb: Hello, For my game I need to represent right isosceles triangles, and do operations including translation and rotation in 15 degree increments. Unfortunately, I cannot tolerate rounding error, because it will cause bad visual and gameplay artifacts. I'm thinking of representing points as vectors where the components are of the form a + b * sqrt(2) + c * sqrt(3) + d * sqrt(6) where a, b, c, and d are rationals. I believe numbers of this form are sufficient for my purposes, although I haven't worked out all the proofs yet. Anyway, I was wondering if anyone has done anything similar and can suggest a library I can use for manipulating such vectors before I go off and implement it myself. Thanks! --Mike Hi I don't think that you can avoid rounding errors, unless you use a math library that takes the math errors of the computer into account (which can differ from hardware to hardware). I'm not sure, why you want to represent points in such a complicated way, but I don't know the theory about it and I'm not a mathematician. One way to go is to accumulate the angle of a rotation (same for translation) and use the accumulated angle on a object to transform it into the right orientation (if you do use a previously rotated object then you will get much more rounding errors over time!). Using that way one would have a variable 'angle' which would be incremented in 15 degree steps (15, 30, 45,...) and use it to construct the rotation matrix (or whatever it is used to rotate). This should be precise enough. Unless you can draw using subpixels, you will have rounding errors when trying to draw the points on integer coordinates of the screen anyway. Maybe I'm wrong. ~DR0ID
[pygame] exact algebraic numbers?
Hello, For my game I need to represent right isosceles triangles, and do operations including translation and rotation in 15 degree increments. Unfortunately, I cannot tolerate rounding error, because it will cause bad visual and gameplay artifacts. I'm thinking of representing points as vectors where the components are of the form a + b * sqrt(2) + c * sqrt(3) + d * sqrt(6) where a, b, c, and d are rationals. I believe numbers of this form are sufficient for my purposes, although I haven't worked out all the proofs yet. Anyway, I was wondering if anyone has done anything similar and can suggest a library I can use for manipulating such vectors before I go off and implement it myself. Thanks! --Mike
