solve(x**2+N,x)

[draz...@gmail.com]

Hi,  

I used in some experiments the following simple code.

import time

from sympy.solvers import solve

from sympy import Symbol

x=Symbol('x')

N=2**264+2**64+1

solve(x**2 + N , x)

The previous code is very slow (at least in my machine, in fact I didn't wait to see the result). I want to ask if solve() command, before it prints the result tries to compute some factors of N, in order to simplify the result in the square root?

N is the following number

29642774844752946028434172162224104410437116074403984394101159952769834897375233L

which is large (but not really large).

Thank you.

Costas

[Ondřej Čertík]

Hi Costas,

Indeed, solve() is too slow. You can get around it with:

In [12]: solve(x**2 + y, x)
Out[12]:
⎡ ____ ____⎤
⎣-╲╱ -y , ╲╱ -y ⎦

In [15]: _12[0].subs(y, N)
Out[15]:
-33⋅√2722017892080160333189547489644086722721498262112395261166314045249755270
6497⋅ⅈ


This is immediate and should give you the right results.

Ondrej

[Aaron Meurer]

It looks like solve is calling factorint at some point. sqrt(N) will
already simplify intelligently (i.e., call factorint() with the limit
argument so that it isn't too slow). It looks like somewhere in
polyroots it is trying to compute all the divisors of the number. We
should investigate why it is doing this. I can see why that might be
necessary to compute the roots of a polynomial in general, but it
shouldn't be done when computing the roots of a quadratic.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/1dfc4ae4-2de2-45ba-a252-051e21fff72b%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Chris Smith]

It is happening in a call from _integer_basis. There should probably be a quick exit at the start of the function when len(coeffs) < 3.