Why is Mathematica's expansion of expressions with square roots so slow?

Mathematica expansion of expressions with symbols isn't slow, but with square roots it is very slow. In Maple or Mupad both are fast: with square roots they both take less than a second.

Here is an example.

Expand[(a + b + c + d + e)^100]; // Timing

Expand[(Sqrt[2] + Sqrt[3] + Sqrt[5] + Sqrt[6] + Sqrt[7])^100]; // Timing


Can you reproduce this?

I used Mathematica9.0.0.0 and Maple16 on windows7 64 bit.

Updated

Maple and Mupad also give the exact result, please see following picture. It's equal to Mathematica' result.

-
Please do not use the bugs tag when you post a new question. This tag is used to categorize problems which were verified to be due to a bug by the community. If the consensus is that it's a bug, the tag will be added eventualy. –  Szabolcs Feb 1 '13 at 20:14

Looks like a computation that rightfully should be slow, you end up with close to 5 million sequences, and I suppose it's checking each constantly throughout to see if the products of the squares lead to square-able numbers.

Why is Maple and Mupad faster? I can't say, but looking at the timing I would suspect they are just using approximate floats, leading to it calculating a single number and then taking that to 100. In Mathematica the second line is treated in a sense just as symbolically as the first, for instance Sqrt(2) will not be converted to the approximate real value: 1.41421..., but it does check along the calculations and convert when the root can be found exactly such as Sqrt[4] evaluating to 2. If you convert to approximate numerical values, then it is faster:

 Expand[N[Sqrt[2] + Sqrt[3] + Sqrt[5] + Sqrt[6] +  Sqrt[7]]^100]; // AbsoluteTiming
{0., Null}


Note the N function, which converts to floating point approximations.

Update

Interesting it would seem the reason for the large difference in performance is that Mathematica expands and calculates the product at once rather than iteratively. This means that if some common subsequences can be simplified it will carry out those simplifications multiple times rather than once while iterating through it.

This mush faster code runs through with one term at a time expanding each time:

 term = (Sqrt[2] + Sqrt[3] + Sqrt[5] + Sqrt[6] + Sqrt[7]);
Nest[Expand[# term] & , term, 100-1]; // AbsoluteTiming
(* {0.120012,Null} *)


To see how Mathematica expands the series you can use

 f /: Times[a___, b_f, c___] := (Print[a, b, c]; Times @@ (First /@ {a}))
(f[a] + f[b] + f[c])^6 // Expand

(* f[a] f[b] f[c] *)
(* f[b] 6 f[a]^5 *)
(* f[a] 6 f[b]^5 *)
(* ... etc. *)

-
No, Maple also gives the exact result. –  mathe Jan 25 '13 at 8:29
@jVincent: Your workaround hits the point and actually seems to work very well. But you have some errors there which you might want to correct, it should rather be Nest[Expand[#*term] &, term, 100 - 1]. Then the results can be checked to be the same (I only checked for 50, not 100). –  Albert Retey Jan 25 '13 at 9:45
@AlbertRetey I wouldn't call it a workaround. They are two different methods of achieving the same result, and in this case one is faster. I would wonder however if anyone knows if there are arguments for using Mathematica's rather than iterating. Perhaps it's due to elements of Expand's other functionality. –  jVincent Jan 25 '13 at 9:54
@jVincent: actually I don't care what we call it, fact is that the most straightforward input does in this case perform very poor, and for some reason maple handles that case better internally. It could of course have deeper reasons that Mathematica does the expansion the way it does and even considered to be a feature, e.g. to avoid accumulation of numeric errors -- but whatever these reasons are they don't matter for this case which thus could be improved. By the way, I think the precedence of // and & is still not correct in your answer (sometimes FullForm has its advantages :-) –  Albert Retey Jan 25 '13 at 10:06
@AlbertRetey I updated the timing. And indeed, I would expect that Maple is just doing it iteratively while Mathematica evaluates each possible sequence. I expect it's a case where complexity analysis dictates the suboptimal algorithm for this case. I think the Maple style expansion will worst case get 5^O(n) terms that can then be collected, while Mathematica already has all the trival terms collected, and therefore only evaluates around 5000 terms. However, since the iterative approach can quite effectively reduce the number of terms, it's nowhere near the upper limit for this example. –  jVincent Jan 25 '13 at 10:38

Mathematica is doing it symbolically. Try:

Expand[(Sqrt[2.] + Sqrt[3.] + Sqrt[5.] + Sqrt[6.] +  Sqrt[7.])^100] // Timing


{0., 1.06187*10^102}

almost instantaneous for a numerical result

-
As the OP has stated maple is also doing this symbolically and still is much faster than Mathematica. It is a well known fact that each of these systems has its strengths and weaknesses. I think it would fit this site well if we try to avoid the impression that users with high reputation like you are not willing to see the weaknesses that Mathematica unavoidably has in some areas. As jVincent has shown there is a workaround which makes Mathematica almost as fast as maple for this particular case... –  Albert Retey Jan 25 '13 at 9:58
@AlbertRetey I'm as critic of the product as a user can be. I've just stated a (perhaps obvious) fact, and that was done before the OP wrote his update –  belisarius Jan 25 '13 at 13:31
@AlbertRetey At the time of writing of this answer OP did not include the information needed to realize that he was in fact comparing two analytically solutions. As such both me and belisarius belived it was a case of comparing numerical to analytical timings, which is often the case when people observer unexpected slow code. –  jVincent Jan 25 '13 at 14:29
@belisarius: I now understand that you didn't have the information when writing this that I had when reading it, which of course makes quite a difference. Sorry if my critizism was unjustfied, the answer(s) just looked like a defence reaction that I think is common but unnecessary (and IMHO even counterproductive). –  Albert Retey Jan 26 '13 at 16:00
@AlbertRetey No problem, sometimes the timeline of the events on the site isn't clear enough at first sight. As a matter of fact I plan to delete this answer in a few days, since it's pointless now. Just as a sidenote, I try to stay far away from bigotry too (and agree about the counter-productiveness of such positions) –  belisarius Jan 26 '13 at 19:08