Re: How to do quickest
- To: mathgroup at smc.vnet.net
- Subject: [mg116523] Re: How to do quickest
- From: David Bailey <dave at removedbailey.co.uk>
- Date: Fri, 18 Feb 2011 04:35:02 -0500 (EST)
- References: <ijgdbr$bsn$1@smc.vnet.net>
On 16/02/2011 11:44, Artur wrote:
> Dear David
> MY procedure count types of different factorizations given polynomial
> modulo successive primes which don't divided discriminant
> (also stored sets of primes of each kind of factorizatios, these
> poddible factorizations are identical as IntegerPartitions
> Best wishes
> Artur
>
> W dniu 2011-02-16 10:34, David Bailey pisze:
>> On 15/02/2011 11:33, Artur wrote:
>>> Dear Mathematica Gurus,
>>> How to do following procedure quickest?
>>> (*start*)
>>> pol = x^8 - x - 1; nn = Length[CoefficientList[pol, x]] - 1; If[
>>> IrreduciblePolynomialQ[pol], pp = IntegerPartitions[nn]; aa = {};
>>> Do[AppendTo[aa, {}], {n, 1, Length[pp]}]; Print[aa];
>>> ff = FactorInteger[Discriminant[pol, x]]; bb = {};
>>> Do[AppendTo[bb, ff[[n]][[1]]], {n, 1, Length[ff]}]; n = 1; cn = 0;
>>> While[cn< nn!, p = Prime[n];
>>> If[MemberQ[bb, p], , cn = cn + 1;
>>> kk = FactorList[pol, Modulus -> p]; ww = {};
>>> Do[cc = Length[CoefficientList[kk[[m]][[1]], x]];
>>> AppendTo[ww, cc - 1], {m, 2, Length[kk]}]; ww = Reverse[ww];
>>> pos = Position[pp, ww][[1]][[1]]; AppendTo[aa[[pos]], Prime[n]]];
>>> n++]]; Table[Length[aa[[m]]], {m, 1, Length[aa]}]
>>> (*end*)
>>> Best wishes
>>> Artur
>>>
>> It might be better to describe what you want Mathematica to do, rather
>> than leave people to decipher the code you have written!
>>
>> David Bailey
>> http://www.dbaileyconsultancy.co.uk
>>
>>
>>
>
Sorry, I've not been able to do too much to speed this up. My first
thought had been that the Append calls might be expensive, because if
you build up a long list with Append or AppendTo, this can be expensive
because the whole list is re-created each time, however the lists in
this problem are pretty short. There are certainly bits of the code that
could be made functional, but they don't seem to be in the part of the
code that consumes most of the CPU time.
Recoding the evaluation of ww as:
ww = Map[Exponent[#[[1]], x] &, Drop[kk, 1]];
and avoiding the recomputation of Prime[n] does save a little.
I suspect the FactorList takes a lot of the CPU cycles!
Of course, someone may come up with a different algorithm - which might
transform your problem!
David Bailey
http://www.dbaileyconsultancy.co.uk