MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Re: NInegrate Bug
  • Next by Date: n-adic integers
  • Previous by thread: Re: How to do quickest
  • Next by thread: Re: How to do quickest