Re: [math-fun] perfect squares
=Bill & Rosemary Cordwell Is there an easy way to tell when a + b*sqrt(k) is a perfect square in the extension field Q(sqrt(k))? [...] I'm particularly interested in when a, b, k are integers...
For some value of "easy": With JHC's x=sqrt k, if a+bx = (c+dx)^2 then b=2cd, so first off b must be even, and then you could run through factorizations to see if any give you the right value of a=cc+kdd. Or maybe you could do something by implementing Newton's method in Q(x)? 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"<;-).
Solve A = a+b*sqrt(d) = (x+y*sqrt(d))^2 with a,b,x,y rational. First of all, the norm aa-dbb must be square, say NN, or else A is not a square. We get xx+dyy = a, 2xy = b. Substitute y=b/(2x) into the first equation, and solve the resulting quadratic. xx = (a +- sqrt(aa-dbb))/2 = (a +- N)/2. If either (a+N)/2 or (a-N)/2 is square, we get a rational x, and also a rational y. --- Marc LeBrun <mlb@fxpt.com> wrote:
=Bill & Rosemary Cordwell Is there an easy way to tell when a + b*sqrt(k) is a perfect square in the extension field Q(sqrt(k))? [...] I'm particularly interested in when a, b, k are integers...
For some value of "easy":
With JHC's x=sqrt k, if a+bx = (c+dx)^2 then b=2cd, so first off b must be even, and then you could run through factorizations to see if any give you the right value of a=cc+kdd.
Or maybe you could do something by implementing Newton's method in Q(x)?
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"<;-).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
__________________________________ Do you Yahoo!? New and Improved Yahoo! Mail - Send 10MB messages! http://promotions.yahoo.com/new_mail
On Thu, Jul 08, 2004 at 10:42:17AM -0700, Marc LeBrun wrote:
BTW I've shared RCS's interesting experience of the surprising messiness of such algorithms, ...
OK, I'll bite.
such as determining whether p+qx < r+sx for signed p,q,r,s using only integer operations.
What's wrong with (p-r > 0 && q-s > 0 && (p-r)^2 < k*(q-s)^2) || (p-r < 0 && q-s < 0 && (p-r)^2 > k*(q-s)^2) ? [As before, x = sqrt(k)]
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"<;-).
Err, it is easy once you have the continued fraction expansion, right? Is the issue getting the continued fraction expansion? Peace, Dylan
=Dylan Thurston What's wrong with (p-r > 0 && q-s > 0 && (p-r)^2 < k*(q-s)^2) || (p-r < 0 && q-s < 0 && (p-r)^2 > k*(q-s)^2) ? [As before, x = sqrt(k)]
Nothing's wrong, but is there any "good" reason for why it's so complicated? By comparison, p/q < r/s is much simpler. The forms p+qx seem in some sense "morally equivalent" to p/q (for example they "induce" the reals similarly). Square testing, simple ordering, whatever: p+qx always seems to get "casey".
=Marc LeBrun 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"<;-).
=Dylan Thurston Err, it is easy once you have the continued fraction expansion, right? Is the issue getting the continued fraction expansion?
No, getting a CF is of course "solved". For example say k=2 so it's 1,2,2,2,... Maybe I've just been dense on seeing how to use that to nicely generate the a+bx. If you can tell me a truly easy way, then you've made an easy $50! "Easy" would be something like the so-called "BRM" raster line drawing algorithm, where you step directly to the next a,b without maintaining a whole bunch of state. (The best I've got so far maintains a sorted list of all a+bx with the same floor). Even funner would be directly computing the Nth a,b. Or, the number below some C+Dx. Here's the ordered forty-four k=2 pairs for a+bx < 10, then their a and b components: 0,0 1,0 0,1 2,0 1,1 0,2 3,0 2,1 1,2 4,0 0,3 3,1 2,2 5,0 1,3 4,1 0,4 3,2 6,0 2,3 5,1 1,4 4,2 7,0 0,5 3,3 6,1 2,4 5,2 8,0 1,5 4,3 7,1 0,6 3,4 6,2 9,0 2,5 5,3 8,1 1,6 4,4 7,2 0,7 0 1 0 2 1 0 3 2 1 4 0 3 2 5 1 4 0 3 6 2 5 1 4 7 0 3 6 2 5 8 1 4 7 0 3 6 9 2 5 8 1 4 7 0 0 0 1 0 1 2 0 1 2 0 3 1 2 0 3 1 4 2 0 3 1 4 2 0 5 3 1 4 2 0 5 3 1 6 4 2 0 5 3 1 6 4 2 7
participants (3)
-
dpt＠lotus.bostoncoop.net -
Eugene Salamin -
Marc LeBrun