ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 30 Jun 2014 15:28:50 +0200Solving ax^2+bxy+cy^2=n fast?https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/Hi, I was wondering whether equations as ax^2+bxy+cy^2=n can be solved
*fast*. **Solve** is a general application with overhead.
I think of methods such as can be found on [www.alpertron.com.ar/METHODS.HTM](http://www.alpertron.com.ar/METHODS.HTM)
by Dario Alejandro Alpern, or [www.numbertheory.org/php/](http://www.numbertheory.org/php/) by Keith
Matthews. It seems to me logic that for instance **BinaryQF** would facilitate this within Sage.
I wrote some routines using Python (like NZMATH [cornacchiamodify](http://fossies.org/dox/NZMATH-1.2.0/ecpp_8py_source.html), but these have to be optimized via Cython and [GMP](http://gmplib.org/manual/Introduction-to-GMP.html#Introduction-to-GMP). Another source is the [LMM algorithm](http://mathafou.free.fr/themes_en/kpell.html). Before I take this route, I want to check that I'm not reinventing the wheel and/or I'm able to cooperate with someone.
Thanks in advance for your guidance! RolandTue, 01 Jan 2013 11:03:39 +0100https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/Comment by vdelecroix for <p>Hi, I was wondering whether equations as ax^2+bxy+cy^2=n can be solved
<em>fast</em>. <strong>Solve</strong> is a general application with overhead.
I think of methods such as can be found on <a href="http://www.alpertron.com.ar/METHODS.HTM">www.alpertron.com.ar/METHODS.HTM</a>
by Dario Alejandro Alpern, or <a href="http://www.numbertheory.org/php/">www.numbertheory.org/php/</a> by Keith
Matthews. It seems to me logic that for instance <strong>BinaryQF</strong> would facilitate this within Sage.</p>
<p>I wrote some routines using Python (like NZMATH <a href="http://fossies.org/dox/NZMATH-1.2.0/ecpp_8py_source.html">cornacchiamodify</a>, but these have to be optimized via Cython and <a href="http://gmplib.org/manual/Introduction-to-GMP.html#Introduction-to-GMP">GMP</a>. Another source is the <a href="http://mathafou.free.fr/themes_en/kpell.html">LMM algorithm</a>. Before I take this route, I want to check that I'm not reinventing the wheel and/or I'm able to cooperate with someone. </p>
<p>Thanks in advance for your guidance! Roland</p>
https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/?comment=23135#post-id-23135Could you provide a link to the work you have already done?Sun, 29 Jun 2014 22:29:51 +0200https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/?comment=23135#post-id-23135Comment by Rolandb for <p>Hi, I was wondering whether equations as ax^2+bxy+cy^2=n can be solved
<em>fast</em>. <strong>Solve</strong> is a general application with overhead.
I think of methods such as can be found on <a href="http://www.alpertron.com.ar/METHODS.HTM">www.alpertron.com.ar/METHODS.HTM</a>
by Dario Alejandro Alpern, or <a href="http://www.numbertheory.org/php/">www.numbertheory.org/php/</a> by Keith
Matthews. It seems to me logic that for instance <strong>BinaryQF</strong> would facilitate this within Sage.</p>
<p>I wrote some routines using Python (like NZMATH <a href="http://fossies.org/dox/NZMATH-1.2.0/ecpp_8py_source.html">cornacchiamodify</a>, but these have to be optimized via Cython and <a href="http://gmplib.org/manual/Introduction-to-GMP.html#Introduction-to-GMP">GMP</a>. Another source is the <a href="http://mathafou.free.fr/themes_en/kpell.html">LMM algorithm</a>. Before I take this route, I want to check that I'm not reinventing the wheel and/or I'm able to cooperate with someone. </p>
<p>Thanks in advance for your guidance! Roland</p>
https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/?comment=23136#post-id-23136Thanks for all replies!
Yes, I'm looking at integers.
A few months ago Thilina Rathnayake implemented routines in Sympy (http://thilinaatsympy.wordpress.com/2013/09/14/status-of-the-diophantine-module-2/). This seems to me a good start as Sympy is a standard package.
I'll have a 2nd look at my routines and I'll provide a link within a few days (if that's still wanted).
RolandSun, 29 Jun 2014 22:45:18 +0200https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/?comment=23136#post-id-23136Comment by slelievre for <p>Hi, I was wondering whether equations as ax^2+bxy+cy^2=n can be solved
<em>fast</em>. <strong>Solve</strong> is a general application with overhead.
I think of methods such as can be found on <a href="http://www.alpertron.com.ar/METHODS.HTM">www.alpertron.com.ar/METHODS.HTM</a>
by Dario Alejandro Alpern, or <a href="http://www.numbertheory.org/php/">www.numbertheory.org/php/</a> by Keith
Matthews. It seems to me logic that for instance <strong>BinaryQF</strong> would facilitate this within Sage.</p>
<p>I wrote some routines using Python (like NZMATH <a href="http://fossies.org/dox/NZMATH-1.2.0/ecpp_8py_source.html">cornacchiamodify</a>, but these have to be optimized via Cython and <a href="http://gmplib.org/manual/Introduction-to-GMP.html#Introduction-to-GMP">GMP</a>. Another source is the <a href="http://mathafou.free.fr/themes_en/kpell.html">LMM algorithm</a>. Before I take this route, I want to check that I'm not reinventing the wheel and/or I'm able to cooperate with someone. </p>
<p>Thanks in advance for your guidance! Roland</p>
https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/?comment=16143#post-id-16143Are `a`, `b`, `c`, `n` all integers, and are you looking for integer solutions `(x,y)`?Sun, 22 Jun 2014 14:36:42 +0200https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/?comment=16143#post-id-16143Answer by rws for <p>Hi, I was wondering whether equations as ax^2+bxy+cy^2=n can be solved
<em>fast</em>. <strong>Solve</strong> is a general application with overhead.
I think of methods such as can be found on <a href="http://www.alpertron.com.ar/METHODS.HTM">www.alpertron.com.ar/METHODS.HTM</a>
by Dario Alejandro Alpern, or <a href="http://www.numbertheory.org/php/">www.numbertheory.org/php/</a> by Keith
Matthews. It seems to me logic that for instance <strong>BinaryQF</strong> would facilitate this within Sage.</p>
<p>I wrote some routines using Python (like NZMATH <a href="http://fossies.org/dox/NZMATH-1.2.0/ecpp_8py_source.html">cornacchiamodify</a>, but these have to be optimized via Cython and <a href="http://gmplib.org/manual/Introduction-to-GMP.html#Introduction-to-GMP">GMP</a>. Another source is the <a href="http://mathafou.free.fr/themes_en/kpell.html">LMM algorithm</a>. Before I take this route, I want to check that I'm not reinventing the wheel and/or I'm able to cooperate with someone. </p>
<p>Thanks in advance for your guidance! Roland</p>
https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/?answer=23133#post-id-23133 Indeed, there is no code in Sage to solve the quadratic Diophantine in two variables like Alpern's program does. You are welcome to contribute, and I'm willing to help. Contact me through my G+ page if you are interested.
The most immediate task would be to integrate the sympy stuff. I have opened this ticket:
http://trac.sagemath.org/ticket/16590
Until then you can use sympy within Sage:
sage: from sympy.solvers.diophantine import *
sage: from sympy import sympify
sage: var('x,y,m')
(x, y, m)
sage: diop_solve(sympify(x**2 + y**2 - 5))
{(-2, -1), (-2, 1), (2, -1), (2, 1)}
sage: diop_solve(sympify(x**2 - 3*y**2 - 1))
{(-sqrt(3)*(-sqrt(3) + 2)**t/2 + (-sqrt(3) + 2)**t + sqrt(3)*(sqrt(3) + 2)**t/2 + (sqrt(3) + 2)**t,
-sqrt(3)*(-sqrt(3) + 2)**t/3 + (-sqrt(3) + 2)**t/2 + (sqrt(3) + 2)**t/2 + sqrt(3)*(sqrt(3) + 2)**t/3)}
Sun, 29 Jun 2014 21:25:24 +0200https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/?answer=23133#post-id-23133Answer by Peter Luschny for <p>Hi, I was wondering whether equations as ax^2+bxy+cy^2=n can be solved
<em>fast</em>. <strong>Solve</strong> is a general application with overhead.
I think of methods such as can be found on <a href="http://www.alpertron.com.ar/METHODS.HTM">www.alpertron.com.ar/METHODS.HTM</a>
by Dario Alejandro Alpern, or <a href="http://www.numbertheory.org/php/">www.numbertheory.org/php/</a> by Keith
Matthews. It seems to me logic that for instance <strong>BinaryQF</strong> would facilitate this within Sage.</p>
<p>I wrote some routines using Python (like NZMATH <a href="http://fossies.org/dox/NZMATH-1.2.0/ecpp_8py_source.html">cornacchiamodify</a>, but these have to be optimized via Cython and <a href="http://gmplib.org/manual/Introduction-to-GMP.html#Introduction-to-GMP">GMP</a>. Another source is the <a href="http://mathafou.free.fr/themes_en/kpell.html">LMM algorithm</a>. Before I take this route, I want to check that I'm not reinventing the wheel and/or I'm able to cooperate with someone. </p>
<p>Thanks in advance for your guidance! Roland</p>
https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/?answer=23145#post-id-23145Sage code which wraps some fast Pari functions and implements a fast solver from Will Jagy
('Conway_positive_primitive' and 'Conway_positive_all') can be found at [1].
The main function combines several important cases in a single function:
represented_by_binaryQF(
a, b, c, # the coefficients
M, # limit
primitively, # default false
prime, # default false
verbose # default true
)
See the many examples given there.
[1] http://oeis.org/wiki/User:Peter_Luschny/BinaryQuadraticForms
Mon, 30 Jun 2014 15:28:50 +0200https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/?answer=23145#post-id-23145Answer by vdelecroix for <p>Hi, I was wondering whether equations as ax^2+bxy+cy^2=n can be solved
<em>fast</em>. <strong>Solve</strong> is a general application with overhead.
I think of methods such as can be found on <a href="http://www.alpertron.com.ar/METHODS.HTM">www.alpertron.com.ar/METHODS.HTM</a>
by Dario Alejandro Alpern, or <a href="http://www.numbertheory.org/php/">www.numbertheory.org/php/</a> by Keith
Matthews. It seems to me logic that for instance <strong>BinaryQF</strong> would facilitate this within Sage.</p>
<p>I wrote some routines using Python (like NZMATH <a href="http://fossies.org/dox/NZMATH-1.2.0/ecpp_8py_source.html">cornacchiamodify</a>, but these have to be optimized via Cython and <a href="http://gmplib.org/manual/Introduction-to-GMP.html#Introduction-to-GMP">GMP</a>. Another source is the <a href="http://mathafou.free.fr/themes_en/kpell.html">LMM algorithm</a>. Before I take this route, I want to check that I'm not reinventing the wheel and/or I'm able to cooperate with someone. </p>
<p>Thanks in advance for your guidance! Roland</p>
https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/?answer=23134#post-id-23134Hi,
The case of the sum of squares (a=c=1 and b=0) has been implemented recently in [trac ticket #16308](http://trac.sagemath.org/ticket/16308). It uses factorisation of integers and Cornacchia's algorithm (as well as a naive method for small input but implemented in C).
I agree with Ralf it would be nice to have more general method for quadratic diophantine equations!
VincentSun, 29 Jun 2014 22:27:30 +0200https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/?answer=23134#post-id-23134Answer by John Cremona for <p>Hi, I was wondering whether equations as ax^2+bxy+cy^2=n can be solved
<em>fast</em>. <strong>Solve</strong> is a general application with overhead.
I think of methods such as can be found on <a href="http://www.alpertron.com.ar/METHODS.HTM">www.alpertron.com.ar/METHODS.HTM</a>
by Dario Alejandro Alpern, or <a href="http://www.numbertheory.org/php/">www.numbertheory.org/php/</a> by Keith
Matthews. It seems to me logic that for instance <strong>BinaryQF</strong> would facilitate this within Sage.</p>
<p>I wrote some routines using Python (like NZMATH <a href="http://fossies.org/dox/NZMATH-1.2.0/ecpp_8py_source.html">cornacchiamodify</a>, but these have to be optimized via Cython and <a href="http://gmplib.org/manual/Introduction-to-GMP.html#Introduction-to-GMP">GMP</a>. Another source is the <a href="http://mathafou.free.fr/themes_en/kpell.html">LMM algorithm</a>. Before I take this route, I want to check that I'm not reinventing the wheel and/or I'm able to cooperate with someone. </p>
<p>Thanks in advance for your guidance! Roland</p>
https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/?answer=23137#post-id-23137It's a special case, but the pari function qfbsolve(Q,p) solves Q(x,y)=p where Q is a binary quadratic form and p a prime. It would be easy to wrap that function in sage/libs/pari/gp.pyx. For now:
sage: Q = gp.Qfb(1,0,1)
sage: Q
Qfb(1, 0, 1)
sage: Q.qfbsolve(97)
[9, 4]
Sun, 29 Jun 2014 23:49:47 +0200https://ask.sagemath.org/question/9673/solving-ax2bxycy2n-fast/?answer=23137#post-id-23137