[sage-devel] Re: Slowness in comparing symbolic expressions
Le jeudi 27 novembre 2014 02:46:26 UTC+1, Robert Dodier a écrit :
On 2014-11-26, Han Frederic h...@math.jussieu.fr javascript: wrote:
Hi, I have tried the factorization with giacpy. (cf trac 12375).
I had to expexpand first before factoring and did this:
sage: from giacpy import libgiac
sage: x=libgiac('x')
sage: s=exp(1024*(x+1))-1
sage: %time s.expexpand().factor()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 1.32 ms
(exp(x+1)-1)*(exp(x+1)+1)*(exp(x+1)^2+1)*(exp(x+1)^4+1)*(exp(x+1)^8+1)*(exp(x+1)^16+1)*(exp(x+1)^32+1)*(exp(x+1)^64+1)*(exp(x+1)^128+1)*(exp(x+1)^256+1)*(exp(x+1)^512+1)
That's terrific. Do you know anything about the implementation of Giac?
I downloaded the source code and after poking around a bit, I can't
tell where factoring such an expression actually occurs. Does Giac
handle that itself, or does it punt to PARI or something else?
What is the effect of expexpand in the example above?
Thanks for any information,
Robert Dodier
expexpand do this:
sage: s
exp(1024*(x+1))-1
sage: s.expexpand()
exp(x+1)^1024-1
so I guess that factor works as if it was a polynomial in one variable. (I
have asked on giac forum to obtain confirmation about the implementation
for one variable, but I think that for multivariable giac does it alone:
so I have tried this:
sage: x,y=libgiac('x,y')
sage: s=exp(1024*(x+1))-exp(768*(y+2))
sage: %time s.expexpand().factor()
CPU times: user 1.21 s, sys: 16 ms, total: 1.23 s
Wall time: 1.22 s
-(exp(y+2)^3-exp(x+1)^4)*(exp(y+2)^3+exp(x+1)^4)*(exp(y+2)^6+exp(x+1)^8)*(exp(y+2)^12+exp(x+1)^16)*(exp(y+2)^24+exp(x+1)^32)*(exp(y+2)^48+exp(x+1)^64)*(exp(y+2)^96+exp(x+1)^128)*(exp(y+2)^192+exp(x+1)^256)*(exp(y+2)^384+exp(x+1)^512)
best
Frederic
--
You received this message because you are subscribed to the Google Groups
sage-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slowness in comparing symbolic expressions
Incidentally I observe that Sympy has the same behavior, so we can't
just nick their factoring algorithm -- maybe some other package we can
try the same example to see if any of them handle it quickly?
best
Robert Dodier
Hi, I have tried the factorization with giacpy. (cf trac 12375). I had to
expexpand first before factoring and did this:
sage: from giacpy import libgiac
sage: x=libgiac('x')
sage: s=exp(1024*(x+1))-1
sage: %time s.expexpand().factor()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 1.32 ms
(exp(x+1)-1)*(exp(x+1)+1)*(exp(x+1)^2+1)*(exp(x+1)^4+1)*(exp(x+1)^8+1)*(exp(x+1)^16+1)*(exp(x+1)^32+1)*(exp(x+1)^64+1)*(exp(x+1)^128+1)*(exp(x+1)^256+1)*(exp(x+1)^512+1)
or
sage: %time s.expexpand().factor().expexpand()
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 1.13 ms
(exp(x)*exp(1)-1)*(exp(x)*exp(1)+1)*((exp(x)*exp(1))^2+1)*((exp(x)*exp(1))^4+1)*((exp(x)*exp(1))^8+1)*((exp(x)*exp(1))^16+1)*((exp(x)*exp(1))^32+1)*((exp(x)*exp(1))^64+1)*((exp(x)*exp(1))^128+1)*((exp(x)*exp(1))^256+1)*((exp(x)*exp(1))^512+1)
best
Frederic
--
You received this message because you are subscribed to the Google Groups
sage-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slowness in comparing symbolic expressions
On 2014-11-26, Han Frederic h...@math.jussieu.fr wrote:
Hi, I have tried the factorization with giacpy. (cf trac 12375).
I had to expexpand first before factoring and did this:
sage: from giacpy import libgiac
sage: x=libgiac('x')
sage: s=exp(1024*(x+1))-1
sage: %time s.expexpand().factor()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 1.32 ms
(exp(x+1)-1)*(exp(x+1)+1)*(exp(x+1)^2+1)*(exp(x+1)^4+1)*(exp(x+1)^8+1)*(exp(x+1)^16+1)*(exp(x+1)^32+1)*(exp(x+1)^64+1)*(exp(x+1)^128+1)*(exp(x+1)^256+1)*(exp(x+1)^512+1)
That's terrific. Do you know anything about the implementation of Giac?
I downloaded the source code and after poking around a bit, I can't
tell where factoring such an expression actually occurs. Does Giac
handle that itself, or does it punt to PARI or something else?
What is the effect of expexpand in the example above?
Thanks for any information,
Robert Dodier
--
You received this message because you are subscribed to the Google Groups
sage-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Slowness in comparing symbolic expressions
if you are looking to proof equivalence to zero, you could use the zeroequiv command in maxima, which is going to be, in general, pretty fast. But as i recall, if it says false that merely means it could not prove the expression is zero. Look for discussion of bugs / features in maxima mailing list some years ago On Friday, November 7, 2014 2:04:54 PM UTC-8, Nils Bruin wrote: On Friday, November 7, 2014 1:43:13 PM UTC-8, Thierry (sage-googlesucks@xxx) wrote: Incidentally I observe that Sympy has the same behavior, so we can't just nick their factoring algorithm -- maybe some other package we can try the same example to see if any of them handle it quickly? How did you observe the same behaviour for sympy ? I'm pretty sure Robert is alluding to the fact that the factoring in sympy is also slow: sage: %time (exp(256*(x+1)) - 1)._sympy_().factor() CPU times: user 20.3 s, sys: 11 ms, total: 20.3 s Wall time: 20.3 s (E*exp(x) - 1)*(E*exp(x) + 1)*(exp(2)*exp(2*x) + 1)*(exp(4)*exp(4*x) + 1)*(exp(8)*exp(8*x) + 1)*(exp(16)*exp(16*x) + 1)*(exp(32)*exp(32*x) + 1)*(exp(64)*exp(64*x) + 1)*(exp(128)*exp(128*x) + 1) Apparently, sympy doesn't try factoring as part of its zero test (or at least arrives at a definitive answer for this example). However, note that the answers of sympy and maxima are different: sympy says false because the expression is not identically 0 and maxima says unknown because the expression is not identically 0, but is 0 for some values of x (or at least I hope that is what maxima is doing). So maxima is determining more information. -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Slowness in comparing symbolic expressions
Hi,
On Thu, Nov 06, 2014 at 03:07:36AM +, Robert Dodier wrote:
On 2014-11-05, Nils Bruin nbr...@sfu.ca wrote:
On Tuesday, November 4, 2014 3:46:55 PM UTC-8, Robert Dodier wrote:
I don't know a work-around for is(equal(1,exp(256*(x+1. As always,
a bug report will be very helpful. http://sourceforge.net/p/maxima/bugs
I'm not so sure it's a bug or that something can be done about it, but you
can track progress at https://sourceforge.net/p/maxima/bugs/2836/
Well, it's certainly disconcerting to have everything grind to a halt
when one tries a simple operation ... I've bumped into this same
bug/feature in various contexts.
Incidentally I observe that Sympy has the same behavior, so we can't
just nick their factoring algorithm -- maybe some other package we can
try the same example to see if any of them handle it quickly?
How did you observe the same behaviour for sympy ?
I can not reproduce this with the following naive code:
sage: assume(x, 'real')
sage: a = exp(512*(x+1)) - 1
sage: s = a._sympy_()
sage: %time bool(s == 0)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 241 盜
False
sage: %time bool(a == 0)
CPU times: user 10min 21s, sys: 200 ms, total: 10min 21s
Wall time: 10min 24s
False
or in raw python:
In [1]: from sympy import Symbol, exp
In [2]: x = Symbol('x', real=True)
In [3]: s = exp(512*(x+1)) - 1
In [4]: %time s == 0
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
Out[4]: False
Ciao,
Thierry
best
Robert Dodier
--
You received this message because you are subscribed to the Google Groups
sage-devel group.
To unsubscribe from this group and stop receiving emails from it, send an
email to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups
sage-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Slowness in comparing symbolic expressions
On Friday, November 7, 2014 1:43:13 PM UTC-8, Thierry (sage-googlesucks@xxx) wrote: Incidentally I observe that Sympy has the same behavior, so we can't just nick their factoring algorithm -- maybe some other package we can try the same example to see if any of them handle it quickly? How did you observe the same behaviour for sympy ? I'm pretty sure Robert is alluding to the fact that the factoring in sympy is also slow: sage: %time (exp(256*(x+1)) - 1)._sympy_().factor() CPU times: user 20.3 s, sys: 11 ms, total: 20.3 s Wall time: 20.3 s (E*exp(x) - 1)*(E*exp(x) + 1)*(exp(2)*exp(2*x) + 1)*(exp(4)*exp(4*x) + 1)*(exp(8)*exp(8*x) + 1)*(exp(16)*exp(16*x) + 1)*(exp(32)*exp(32*x) + 1)*(exp(64)*exp(64*x) + 1)*(exp(128)*exp(128*x) + 1) Apparently, sympy doesn't try factoring as part of its zero test (or at least arrives at a definitive answer for this example). However, note that the answers of sympy and maxima are different: sympy says false because the expression is not identically 0 and maxima says unknown because the expression is not identically 0, but is 0 for some values of x (or at least I hope that is what maxima is doing). So maxima is determining more information. -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slowness in comparing symbolic expressions
On 2014-11-05, Nils Bruin nbr...@sfu.ca wrote: On Tuesday, November 4, 2014 3:46:55 PM UTC-8, Robert Dodier wrote: I don't know a work-around for is(equal(1,exp(256*(x+1. As always, a bug report will be very helpful. http://sourceforge.net/p/maxima/bugs I'm not so sure it's a bug or that something can be done about it, but you can track progress at https://sourceforge.net/p/maxima/bugs/2836/ Well, it's certainly disconcerting to have everything grind to a halt when one tries a simple operation ... I've bumped into this same bug/feature in various contexts. Incidentally I observe that Sympy has the same behavior, so we can't just nick their factoring algorithm -- maybe some other package we can try the same example to see if any of them handle it quickly? best Robert Dodier -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slowness in comparing symbolic expressions
Interesting. Since this assumption stuff does something in Maxima, perhaps that is where the slowdown happens. I'm not sure that we ask Maxima to check for our equality, though perhaps it comes into play once that assumption is made. Hi, I know that comparing symbolic expressions of a real variable is generally an undecidable problem, but I've recently faced the following CPU time issue on very simple symbolic expressions: sage: assume(x, 'real') sage: %time bool(exp(512*(x+1)) == 1) CPU times: user 4min 46s, sys: 116 ms, total: 4min 46s Wall time: 4min 48s False The CPU time actually increases with the factor in front of (x+1): sage: %time bool(exp(2*(x+1)) == 1) CPU times: user 24 ms, sys: 4 ms, total: 28 ms Wall time: 23.7 ms False sage: %time bool(exp(32*(x+1)) == 1) CPU times: user 108 ms, sys: 0 ns, total: 108 ms Wall time: 105 ms False sage: %time bool(exp(64*(x+1)) == 1) CPU times: user 660 ms, sys: 4 ms, total: 664 ms Wall time: 664 ms False sage: %time bool(exp(128*(x+1)) == 1) CPU times: user 4.2 s, sys: 0 ns, total: 4.2 s Wall time: 4.23 s False sage: %time bool(exp(256*(x+1)) == 1) CPU times: user 33.9 s, sys: 4 ms, total: 33.9 s Wall time: 34.1 s False If x is not assumed to be real, everything is fine: sage: forget() sage: %time bool(exp(512*(x+1)) == 1) CPU times: user 32 ms, sys: 0 ns, total: 32 ms Wall time: 31.7 ms False Thanks for your comments / advice on this. Eric. -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slowness in comparing symbolic expressions
On Tuesday, November 4, 2014 9:52:03 AM UTC-8, kcrisman wrote: Interesting. Since this assumption stuff does something in Maxima, perhaps that is where the slowdown happens. I'm not sure that we ask Maxima to check for our equality, though perhaps it comes into play once that assumption is made. Sage apparently does not call Maxima for this, since is(equal(0,exp(512*(x+1; takes 0.05ms, even if one provides the irrelevant declare(x,real). Or if it calls Maxima, it does something else for quite a while. RJF Hi, I know that comparing symbolic expressions of a real variable is generally an undecidable problem, but I've recently faced the following CPU time issue on very simple symbolic expressions: sage: assume(x, 'real') sage: %time bool(exp(512*(x+1)) == 1) CPU times: user 4min 46s, sys: 116 ms, total: 4min 46s Wall time: 4min 48s False The CPU time actually increases with the factor in front of (x+1): sage: %time bool(exp(2*(x+1)) == 1) CPU times: user 24 ms, sys: 4 ms, total: 28 ms Wall time: 23.7 ms False sage: %time bool(exp(32*(x+1)) == 1) CPU times: user 108 ms, sys: 0 ns, total: 108 ms Wall time: 105 ms False sage: %time bool(exp(64*(x+1)) == 1) CPU times: user 660 ms, sys: 4 ms, total: 664 ms Wall time: 664 ms False sage: %time bool(exp(128*(x+1)) == 1) CPU times: user 4.2 s, sys: 0 ns, total: 4.2 s Wall time: 4.23 s False sage: %time bool(exp(256*(x+1)) == 1) CPU times: user 33.9 s, sys: 4 ms, total: 33.9 s Wall time: 34.1 s False If x is not assumed to be real, everything is fine: sage: forget() sage: %time bool(exp(512*(x+1)) == 1) CPU times: user 32 ms, sys: 0 ns, total: 32 ms Wall time: 31.7 ms False Thanks for your comments / advice on this. Eric. -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slowness in comparing symbolic expressions
On Tuesday, November 4, 2014 10:54:51 AM UTC-8, rjf wrote: Sage apparently does not call Maxima for this, since is(equal(0,exp(512*(x+1; takes 0.05ms, even if one provides the irrelevant declare(x,real). Indeed, sage doesn't call Maxima with *that* statement because it would produce a result that has very little bearing on the question asked. sage DOES call Maxima with is (equal(1,exp(256*(x+1; which indeed can take quite a while. In fact, profile data indicates nearly all time reported is spent on that statement. The relevant routine is test_relation_maxima in sage/symbolic/relation.py . The routine could use a facelift (it's doing a lot of strings-based stuff that doesn't need to be done strings-based anymore), but the bottleneck for this example seems to be entirely in maxima. -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slowness in comparing symbolic expressions
On Tuesday, November 4, 2014 11:38:33 AM UTC-8, Nils Bruin wrote: On Tuesday, November 4, 2014 10:54:51 AM UTC-8, rjf wrote: Sage apparently does not call Maxima for this, since is(equal(0,exp(512*(x+1; takes 0.05ms, even if one provides the irrelevant declare(x,real). Indeed, sage doesn't call Maxima with *that* statement because it would produce a result that has very little bearing on the question asked. sage DOES call Maxima with is (equal(1,exp(256*(x+1; That would seem to be a bug. At least I don't see any productive way of spending a lot of time on this. Someone should run it with a profiler and see what's happening. For Sage, I think a better approach if you are going to use Maxima, might be to something like .. is(simplify(1-exp(256*(x+1)) = 0) where simplify is some particular simplification program, e.g. ratsimp, fullratsimp, radcan, ... For radcan() the time reported on my computer is 0. sec which indeed can take quite a while. In fact, profile data indicates nearly all time reported is spent on that statement. The relevant routine is test_relation_maxima in sage/symbolic/relation.py . The routine could use a facelift (it's doing a lot of strings-based stuff that doesn't need to be done strings-based anymore), but the bottleneck for this example seems to be entirely in maxima. -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slowness in comparing symbolic expressions
On Tuesday, November 4, 2014 11:59:18 AM UTC-8, rjf wrote: For Sage, I think a better approach if you are going to use Maxima, might be to something like .. is(simplify(1-exp(256*(x+1)) = 0) where simplify is some particular simplification program, e.g. ratsimp, fullratsimp, radcan, ... which happens in test_relation_maxima, after the is(equal(...)) class has returned unknown. Is your suggestion to try the simplification approaches before? If so, what's your reasoning (apart from the fact that is(equal(...)) currently seems to have a bug that makes it take unduly long). For radcan() the time reported on my computer is 0. sec which indeed can take quite a while. In fact, profile data indicates nearly all time reported is spent on that statement. The relevant routine is test_relation_maxima in sage/symbolic/relation.py . The routine could use a facelift (it's doing a lot of strings-based stuff that doesn't need to be done strings-based anymore), but the bottleneck for this example seems to be entirely in maxima. -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slowness in comparing symbolic expressions
On 2014-11-04, Nils Bruin nbr...@sfu.ca wrote: sage DOES call Maxima with is (equal(1,exp(256*(x+1; which indeed can take quite a while. In fact, profile data indicates nearly all time reported is spent on that statement. A stack trace shows that Maxima is trying to factor 1 - exp(256*(x + 1)) as an intermediate step in trying to figure out the sign (+, -, zero) of that expression, which turns it into a mess and takes a long time; I don't know where the time is eaten up. Smaller versions show how it goes: (%i1) display2d : false $ (%i2) showtime : true $ Evaluation took 0. seconds (0.0001 elapsed) using 32 bytes. (%i3) factor (1 - exp(8*(x + 1))); Evaluation took 0.0280 seconds (0.0251 elapsed) using 401.672 KB. (%o3) -(%e^(x+1)-1)*(%e^(x+1)+1)*(%e^(2*x+2)+1)*(%e^(4*x+4)+1) (%i4) factor (1 - exp(32*(x + 1))); Evaluation took 0.1960 seconds (0.1962 elapsed) using 6.866 MB. (%o4) -(%e^(x+1)-1)*(%e^(x+1)+1)*(%e^(2*x+2)+1)*(%e^(4*x+4)+1)*(%e^(8*x+8)+1) *(%e^(16*x+16)+1) (%i5) factor (1 - exp(64*(x + 1))); Evaluation took 1.4401 seconds (1.4433 elapsed) using 58.820 MB. (%o5) -(%e^(x+1)-1)*(%e^(x+1)+1)*(%e^(2*x+2)+1)*(%e^(4*x+4)+1)*(%e^(8*x+8)+1) *(%e^(16*x+16)+1)*(%e^(32*x+32)+1) I don't know a work-around for is(equal(1,exp(256*(x+1. As always, a bug report will be very helpful. http://sourceforge.net/p/maxima/bugs Sorry I can't be more helpful, Robert Dodier -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slowness in comparing symbolic expressions
On Tuesday, November 4, 2014 3:46:55 PM UTC-8, Robert Dodier wrote: I don't know a work-around for is(equal(1,exp(256*(x+1. As always, a bug report will be very helpful. http://sourceforge.net/p/maxima/bugs I'm not so sure it's a bug or that something can be done about it, but you can track progress at https://sourceforge.net/p/maxima/bugs/2836/ Cheers, Nils -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
