Ask Your Question
2

Solving ax^2+bxy+cy^2=n fast?

asked 2013-01-01 04:03:39 -0500

Rolandb gravatar image

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 by Dario Alejandro Alpern, or 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, but these have to be optimized via Cython and GMP. Another source is the LMM algorithm. 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! Roland

edit retag flag offensive close merge delete

Comments

Are `a`, `b`, `c`, `n` all integers, and are you looking for integer solutions `(x,y)`?

slelievre gravatar imageslelievre ( 2014-06-22 07:36:42 -0500 )edit

Could you provide a link to the work you have already done?

vdelecroix gravatar imagevdelecroix ( 2014-06-29 15:29:51 -0500 )edit

Thanks 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). Roland

Rolandb gravatar imageRolandb ( 2014-06-29 15:45:18 -0500 )edit

4 answers

Sort by ยป oldest newest most voted
3

answered 2014-06-29 16:49:47 -0500

John Cremona gravatar image

It'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]
edit flag offensive delete link more
2

answered 2014-06-29 14:25:24 -0500

updated 2014-06-30 04:48:38 -0500

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)}
edit flag offensive delete link more
2

answered 2014-06-29 15:27:30 -0500

updated 2014-06-29 15:27:55 -0500

Hi,

The case of the sum of squares (a=c=1 and b=0) has been implemented recently in trac 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!

Vincent

edit flag offensive delete link more
1

answered 2014-06-30 08:28:50 -0500

Peter Luschny gravatar image

updated 2014-06-30 08:29:44 -0500

Sage 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_Lusch...

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-01-01 04:03:39 -0500

Seen: 703 times

Last updated: Jun 30 '14