Re: [math-fun] Boy do we need a good radical simplifier
Joerg> * Bill Gosper <billgosper@gmail.com <http://gosper.org/webmail/src/compose.php?send_to=billgosper%40gmail.com>> [Feb 11. 2011 09:45]:
[...] Out[250]= (1 - Sqrt[5] + 3 Sqrt[-2 + Sqrt[5]] + (-2 + Sqrt[5])^(3/2))/(2 Sqrt[2])
which canNOT be done by working outward from the innermost.
Your (1 - sqrt(5) + 3*sqrt(-2+sqrt(5)) + (-2+sqrt(5))^(3/2))/(2*sqrt(2)) = 1/2*(sqrt(sqrt(5)-1) - sqrt(3-sqrt(5))) = 0.1188769458... (sqrt of 5th singular value) Yeth, LambdaStar[x]:=Sqrt[ModularLambda[Sqrt[-x]]] is the xth singular value. For the three fifthsth singular value, MathWorld misprints a doubly nested radical containing a 23 that should be 27, which upon correction denests completely to LambdaStar[3/5] = (1 - Sqrt[3] + 3 Sqrt[5] + Sqrt[15])/(8 Sqrt[2]). Bob Baillie>in mathematica 8: c = (1 + Sqrt[3] + Sqrt[2] 3^(3/4))^(1/3)/(Sqrt[3] - 1)^(1/6); FullSimplify[c] = (2*(7 + 3*Sqrt[3] + Sqrt[72 + 42*Sqrt[3]]))^(1/6) which has even fewer radicals than the one given just below. of course, one can always ask, what does "simplest" mean? bob --- For most purposes, nesting depth trumps radical count. Regrettably, FullSimplify just minimizes LeafCount. I haven't tried it in Mma 8, but in 7, tedious penalization of nesting via custom definitions of ComplexityFunction led me to conclude that Mma does not know how to denest. Perhaps there is something infeasible about Landau's 18yr old algorithm. --rwg
On Sun, Feb 13, 2011 at 1:01 AM, Bill Gosper <billgosper@gmail.com> wrote:
For most purposes, nesting depth trumps radical count. Regrettably, FullSimplify just minimizes LeafCount. I haven't tried it in Mma 8,
but in 7, tedious penalization of nesting via custom definitions of ComplexityFunction led me to conclude that Mma does not know how to denest.
For whomever else wants it, here are three depth metrics you can use in Mma. (********** begin **********) HeuristicNestingDepth::badexpr="HeuristicNestingDepth given unrecognizeable argument `1`."; HeuristicNestingDepth[0]:=0 HeuristicNestingDepth[x_Integer]:=0 HeuristicNestingDepth[x_Rational]:=0 HeuristicNestingDepth[Complex[a_,b_]]:=HeuristicNestingDepth[a]+Max[HeuristicNestingDepth[b],2] HeuristicNestingDepth[Power[x_,n_Integer]]:=HeuristicNestingDepth[x] HeuristicNestingDepth[Power[x_,n_Rational]]:=1+HeuristicNestingDepth[x] HeuristicNestingDepth[Times[x_,y_]]:=Max[HeuristicNestingDepth[x],HeuristicNestingDepth[y]] HeuristicNestingDepth[Plus[x_,y_]]:=HeuristicNestingDepth[x]+HeuristicNestingDepth[y] HeuristicNestingDepth[x_]:=(Message[HeuristicNestingDepth::badexpr,x];Abort[]) MaxNestingDepth::badexpr="MaxNestingDepth given unrecognizeable argument `1`."; MaxNestingDepth[0]:=0 MaxNestingDepth[x_Integer]:=0 MaxNestingDepth[x_Rational]:=0 MaxNestingDepth[Complex[a_,b_]]:=MaxNestingDepth[a]+Max[MaxNestingDepth[b],2] MaxNestingDepth[Power[x_,n_Integer]]:=MaxNestingDepth[x] MaxNestingDepth[Power[x_,n_Rational]]:=1+MaxNestingDepth[x] MaxNestingDepth[Times[x_,y_]]:=Max[MaxNestingDepth[x],MaxNestingDepth[y]] MaxNestingDepth[Plus[x_,y_]]:=Max[MaxNestingDepth[x],MaxNestingDepth[y]] MaxNestingDepth[x_]:=(Message[MaxNestingDepth::badexpr,x];Abort[]) CumulativeNestingDepth::badexpr="CumulativeNestingDepth given unrecognizeable argument `1`."; CumulativeNestingDepth[0]:=0 CumulativeNestingDepth[x_Integer]:=0 CumulativeNestingDepth[x_Rational]:=0 CumulativeNestingDepth[Complex[a_,b_]]:=CumulativeNestingDepth[a]+CumulativeNestingDepth[b]+2 CumulativeNestingDepth[Power[x_,n_Integer]]:=CumulativeNestingDepth[x] CumulativeNestingDepth[Power[x_,n_Rational]]:=1+CumulativeNestingDepth[x] CumulativeNestingDepth[Times[x_,y_]]:=CumulativeNestingDepth[x]+CumulativeNestingDepth[y] CumulativeNestingDepth[Plus[x_,y_]]:=CumulativeNestingDepth[x]+CumulativeNestingDepth[y] CumulativeNestingDepth[x_]:=(Message[CumulativeNestingDepth::badexpr,x];Abort[]) (********** end ***********) And for some example usage: (********** begin ***********) In[169]:= ListApply[fns_,x_]:=Map[#@x&,fns] NestingDepths[x_]:=ListApply[{HeuristicNestingDepth,MaxNestingDepth,CumulativeNestingDepth},x] Module[{exs={1+Sqrt[2]+Sqrt[3], Sqrt[1+Sqrt[2]], (1+Sqrt[3]+Sqrt[2] 3^(3/4))^(1/3)/(-1+Sqrt[3])^(1/6), (2 (7+3 Sqrt[3]+Sqrt[72+42 Sqrt[3]]))^(1/6)}}, TableForm[NestingDepths/@exs,TableHeadings->{exs,{"Heur","Max","Cumul"}}]]//TraditionalForm Out[177]//TraditionalForm= (* P = Power[1+Sqrt[3]+Sqrt[2] 3^(3/4), (3)^-1]/Power[-1+Sqrt[3], (6)^-1] *) (* Q = Power[2 (7+3 Sqrt[3]+Sqrt[72+42 Sqrt[3]]), (6)^-1] *) Heur Max Cumul 1+Sqrt[2]+Sqrt[3] 2 1 2 Sqrt[1+Sqrt[2]] 2 2 2 Expression P 3 2 6 Expression Q 4 3 4 (********** end ***********) Like Mr Gosper said, it seems Mma isn't very knowledgeable about decreasing depth. RWG>
Perhaps there is something infeasible about Landau's 18yr old algorithm.
It's not impossible or infeasible, but getting it to be efficient is difficult. 1. The time complexity of the algorithm is the same as the time complexity of computing the splitting field of the minimal polynomial of the algebraic, which in turn depends on the degree of the minimal polynomial. 2. We need to compute the Galois group of the field in which the algebraic lies (loosely), which is what requires the minimal polynomial and the splitting field. AFAIK, we don't have an algorithm to perform these two things (together) in polynomial time. The algorithm Landau proposed specifically uses polynomial factorization over a field k (her complexity bounds were based on factorization of elements over Q). Anyway, I hope this sheds a little more light. -Robert
participants (2)
-
Bill Gosper -
quad