Re: [math-fun] perfect squares
--- math-fun-request@mailman.xmission.com wrote:
From: Marc LeBrun <mlb@fxpt.com> Subject: Re: [math-fun] perfect squares [snip] BTW I've shared RCS's interesting experience of the surprising messiness of such algorithms, such as determining whether p+qx < r+sx for signed p,q,r,s using only integer operations. Heck, I'd even pay $50 for an easy way to generate a+bx in increasing order for a,b >=0 (if you think you have one contact me to negotiate the definition of "easy"<;-).
Fool's errand, if I understand correctly. For any terms p+qx < r+sx, there exists an u s.t. frac(qx) < frac(ux) < frac(sx) And therefore there exists a t, s.t. p+qx < t+ux < r+sx. (p,q,r,s,t,u integers, x irrational) To lift from mathworld: <<< A consequence of Weyl's criterion is that the sequence {frac(nx)} is dense and equidistributed in the interval [0,1) for irrational x, where n = 1, 2, ... (Finch 2003). ... Finch, S. R. "Powers of 3/2 Modulo One." §2.30.1 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 194-199, 2003.
Phil ===== When inserting a CD, hold down shift to stop the AutoRun feature In the Device Manager, disable the SbcpHid device. http://www.cs.princeton.edu/~jhalderm/cd3/ __________________________________ Do you Yahoo!? Yahoo! Mail - 50x more storage than other providers! http://promotions.yahoo.com/new_mail
On Sun, Jul 11, 2004 at 09:13:27AM -0700, Phil Carmody wrote:
--- math-fun-request@mailman.xmission.com wrote:
From: Marc LeBrun <mlb@fxpt.com> Subject: Re: [math-fun] perfect squares [snip] BTW I've shared RCS's interesting experience of the surprising messiness of such algorithms, such as determining whether p+qx < r+sx for signed p,q,r,s using only integer operations. Heck, I'd even pay $50 for an easy way to generate a+bx in increasing order for a,b >=0 (if you think you have one contact me to negotiate the definition of "easy"<;-).
Fool's errand, if I understand correctly.
For any terms p+qx < r+sx, there exists an u s.t. frac(qx) < frac(ux) < frac(sx) And therefore there exists a t, s.t. p+qx < t+ux < r+sx. (p,q,r,s,t,u integers, x irrational)
I think you missed the constraint 'a,b >= 0'. Peace, Dylan
--- Dylan Thurston <dpt@lotus.bostoncoop.net> wrote:
On Sun, Jul 11, 2004 at 09:13:27AM -0700, Phil Carmody wrote:
--- math-fun-request@mailman.xmission.com wrote:
From: Marc LeBrun <mlb@fxpt.com> Subject: Re: [math-fun] perfect squares [snip] BTW I've shared RCS's interesting experience of the surprising messiness of such algorithms, such as determining whether p+qx < r+sx for signed p,q,r,s using only integer operations. Heck, I'd even pay $50 for an easy way to generate a+bx in increasing order for a,b >=0 (if you think you have one contact me to negotiate the definition of "easy"<;-).
Fool's errand, if I understand correctly.
For any terms p+qx < r+sx, there exists an u s.t. frac(qx) < frac(ux) < frac(sx) And therefore there exists a t, s.t. p+qx < t+ux < r+sx. (p,q,r,s,t,u integers, x irrational)
I think you missed the constraint 'a,b >= 0'.
Peace, Dylan
If p,q,r,s are integers and d is a nonsquare positive integer, we want to determine the truth of p+q*sqrt(d) < r+s*sqrt(d). This is the same as p-r < (s-q)*sqrt(d). If p-r and s-q are of opposite sign or either is zero, the inequality is immediately decided. If p-r and s-q are both positive, then the answer is given by (p-r)^2 < (s-q)^2*d, while if they are both negative, change "<" to ">" in the last inequality. Gene __________________________________ Do you Yahoo!? Take Yahoo! Mail with you! Get it on your mobile phone. http://mobile.yahoo.com/maildemo
="Schroeppel, Richard" <rschroe@sandia.gov> I'm not sure if this qualifies as "easy", and it's got some annoying branches in the algorithm.
=Marc LeBrun I've shared RCS's interesting experience of the surprising messiness of such algorithms, such as determining whether p+qx < r+sx
=Eugene Salamin If p-r and s-q are of opposite sign or either is zero, ... while if they are both negative, change "<" to ">" ...
All these strange branches and cases are what I meant by "surprising messiness". Somehow it seems like there ought to be a simpler way to compute these kinds of things. Is there some "good reason" that arithmetic on p+qx expressions gets so complicated? (eg maybe there's some better representation than "rectangular coordinates"?)
=Marc LeBrun Heck, I'd even pay $50 for an easy way to generate a+bx in increasing order for a,b >=0
=Phil Carmody For any terms p+qx < r+sx, there exists an u s.t. frac(qx) < frac(ux) < frac(sx)
=Dylan Thurston I think you missed the constraint 'a,b >= 0'.
Aye, there's the rub.
participants (4)
-
dpt＠lotus.bostoncoop.net -
Eugene Salamin -
Marc LeBrun -
Phil Carmody