How to simplify square roots

[Ondřej Čertík]

Hi,

How do I simplify the following:

sage: sqrt(3)/sqrt(15)
1/15*sqrt(15)*sqrt(3)
sage: simplify(_)
1/15*sqrt(15)*sqrt(3)

With sympy one gets:

>>> sqrt(3)/sqrt(15)
sqrt(5)/5

The reason I am asking is that we are designing a very fast core in
C++ (https://github.com/sympy/csympy) and so far we can't figure out a
fast way to do the full SymPy like simplification. The rule for Sage
(GiNaC?) simplification seems to be: convert expressions of the form
1/sqrt(2), 1/sqrt(15) into 1/2*sqrt(2), 1/15*sqrt(15), then collect
all integers, and leave the square roots as is, i.e. do not attempt
any integer factorization (in or outside of the square root). This we
know how to implement fast I think.

So I would like to know which function you can later use to do the
full simplification.
And also if you run into any issues with the current Sage behavior (I
used Sage Version 6.2.rc2, Release Date: 2014-05-04).

Many thanks for any feedback,
Ondrej

[Volker Braun]

sage: sqrt(3)/sqrt(15) 

1/15*sqrt(15)*sqrt(3)

sage: _.radical_simplify()

1/5*sqrt(5)

[John Cremona]

Be careful though:

sage: (sqrt(-2)*sqrt(-3)).simplify_radical()
-sqrt(3)*sqrt(2)

i.e. you cannot use sqrt(a)*sqrt(b)=sqrt(a*b) everywhere without
reaching a contradiction.

sage: bool( (sqrt(-2)*sqrt(-3)) == sqrt(2)*sqrt(3) )
False

> --
> 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+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

[kcrisman]

On Monday, June 30, 2014 1:52:50 AM UTC-4, John Cremona wrote:

Be careful though:

sage: (sqrt(-2)*sqrt(-3)).simplify_radical()
-sqrt(3)*sqrt(2)

i.e. you cannot use sqrt(a)*sqrt(b)=sqrt(a*b) everywhere without
reaching a contradiction.

sage: bool( (sqrt(-2)*sqrt(-3)) == sqrt(2)*sqrt(3) )
False

+1 

[Ondřej Čertík]

Thanks Volker for the tip, that does the job. More comments below:

On Sun, Jun 29, 2014 at 11:52 PM, John Cremona <john.c...@gmail.com> wrote:
> Be careful though:
>
> sage: (sqrt(-2)*sqrt(-3)).simplify_radical()
> -sqrt(3)*sqrt(2)
>
> i.e. you cannot use sqrt(a)*sqrt(b)=sqrt(a*b) everywhere without
> reaching a contradiction.
>
> sage: bool( (sqrt(-2)*sqrt(-3)) == sqrt(2)*sqrt(3) )
> False

Right, e.g. in sympy:

>>> sqrt(-2)*sqrt(-3)
-sqrt(6)


Coming to the original example, sympy returns

>>> sqrt(3)/sqrt(15)
sqrt(5)/5

And Mathematica returns 1/sqrt(5).


Here is a more difficult example, in SymPy:

>>> 2**(S(1)/3) * 6**(S(1)/4)
2**(7/12)*3**(1/4)

Mathematica returns the same thing. Sage, on the other hand, does not
simplify this:

sage: 2**(1/3) * 6**(1/4)
6^(1/4)*2^(1/3)
sage: _.rational_simplify()
6^(1/4)*2^(1/3)


What is interesting though, is that Sage does perform some
factorization automatically, e.g.:

sage: sqrt(12)
2*sqrt(3)

Mathematica and SymPy do the same here.

Here is even better example, in Sage:

sage: sqrt(12)/sqrt(6)
1/3*sqrt(6)*sqrt(3)
sage: _.rational_simplify()
1/3*sqrt(6)*sqrt(3)

SymPy or Mathematica:

>>> sqrt(12)/sqrt(6)
sqrt(2)

So the Sage rule seems to be --- factorize simple sqrt(N) into the
form a*sqrt(b), do this for all sqrt() in the expression, and then
just convert 1/sqrt(n) -> sqrt(n)/n, and return the result, after
canceling common factors.

I think a better rule is to either

a) factor everything, like SymPy or Mathematica
2) do not factor anything, and just leave sqrt(12)/sqrt(6) as is. Then
rational_simplify() should return the result from a).

Ondrej

[William Stein]

On Mon, Jun 30, 2014 at 9:29 AM, Ondřej Čertík <ondrej...@gmail.com> wrote:
> Thanks Volker for the tip, that does the job. More comments below:

Another comment. Evidently Sage uses **Maxima** for
rational_simplify, hence the integer factorization that is required to
do this is not-surprisingly insanely stupidly slow, by modern
standards:

sage: p = next_prime(10^10); q = next_prime(10^11)
sage: a = sqrt(p^2*q)/p
sage: %time a.rational_simplify()
1/10000000019*sqrt(10000000038300000037240000001083)
CPU time: 1.12 s, Wall time: 3.52 s
sage: %time factor(p^2*q)
10000000019^2 * 100000000003
CPU time: 0.00 s, Wall time: 0.03 s

Don't even try increasing the size of p, q above... or it'll take forever.

We should maybe consider sometime make our rational_simplify first
factor or something (I don't know), so it can leverage sage's much
better integer factorization code.

William

> --
> 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+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org

[Ondřej Čertík]

On Mon, Jun 30, 2014 at 11:23 AM, William Stein <wst...@gmail.com> wrote:
> On Mon, Jun 30, 2014 at 9:29 AM, Ondřej Čertík <ondrej...@gmail.com> wrote:
>> Thanks Volker for the tip, that does the job. More comments below:
>
> Another comment. Evidently Sage uses **Maxima** for
> rational_simplify, hence the integer factorization that is required to
> do this is not-surprisingly insanely stupidly slow, by modern
> standards:
>
> sage: p = next_prime(10^10); q = next_prime(10^11)
> sage: a = sqrt(p^2*q)/p
> sage: %time a.rational_simplify()
> 1/10000000019*sqrt(10000000038300000037240000001083)
> CPU time: 1.12 s, Wall time: 3.52 s

More importantly, the result is not simplified...

> sage: %time factor(p^2*q)
> 10000000019^2 * 100000000003
> CPU time: 0.00 s, Wall time: 0.03 s
>
> Don't even try increasing the size of p, q above... or it'll take forever.

Btw, Mathematica always returns sqrt(100000000003) and it seems to
cancel "p" no matter how large p and q is (I assume it puts 1/p into
the sqrt() and simplifies the rational).
However, in Mathematica, sqrt(12) gets simplified to 2*sqrt(3). But
sqrt(p*q) returns as
sqrt(1000000001930000000057). So Mathematica seems to have a cut-off, after
which it won't attempt the factorization.

In SymPy, we have a cut-off as well, but unlike Mathematica, we don't
seem to be able to factorize
it either for larger p, q, e.g.:

In [21]: p = 19

In [22]: q = 31

In [23]: sqrt(p**2*q)/p
sqrt(31)


But:

In [18]: p = 10000000019

In [19]: q = 100000000003

In [20]: sqrt(p**2*q)/p
sqrt(10000000038300000037240000001083)/10000000019

> We should maybe consider sometime make our rational_simplify first
> factor or something (I don't know), so it can leverage sage's much
> better integer factorization code.

Btw, in csympy we started using a very fast primesieve library
(http://primesieve.org/).
It's only for generating the primes (and only up to 10^9), but it
might be the fastest library out there.

Ondrej

[rjf]

On Monday, June 30, 2014 10:24:39 AM UTC-7, William wrote:

On Mon, Jun 30, 2014 at 9:29 AM, Ondřej Čertík <ondrej...@gmail.com> wrote:
> Thanks Volker for the tip, that does the job. More comments below:

Another comment.  Evidently Sage uses **Maxima** for
rational_simplify, hence the integer factorization that is required to
do this is not-surprisingly insanely stupidly slow, by modern
standards:

Another, perhaps simpler, tactic would be to change the Maxima code for

integer factorization. This would have the synergistic effect of making any

other code that implicitly uses integer factorization in Maxima, faster as well.

Also, it could be that the lisp you are using has slow arithmetic compared to

some other lisps. Just a guess though.

For sqrt(polynomial) it is plausible to do a "square-free" factorization -- not so expensive

and reasonable payoff -- for polynomials.