2

我有以下代码，它完全符合我的要求，只是速度慢得离谱。我不会那么烦恼，除了当我“手动”处理代码时，即我将它分成几部分并单独执行，它几乎是瞬时的。

这是我的代码：

Coefficient[Product[Sum[x^(j*Prime[i]), {j, 0, Floor[q/Prime[i]]}], 
                        {i, 1, PrimePi[q]}], x, q]

为清楚起见添加了图片：

在此处输入图像描述

我认为它正在尝试优化总和，但不确定。有没有办法阻止它？

此外，由于我所有的系数都是正的，而且我只想要第 x^q 个，有没有办法让 Mathematica 丢弃所有大于那个的指数而不用这些指数做所有乘法？

4

2 回答 2

5

我可能误解了您想要的内容，但是由于系数取决于q，我假设您希望对特定的 进行评估q。因为我怀疑（像你一样）优化产品和总和需要时间，所以我重写了它。你有类似的东西：

With[{q = 80}, Coefficient[\!\(
\*UnderoverscriptBox[\(\[Product]\), \(i = 1\), \(PrimePi[q]\)]\((
\*UnderoverscriptBox[\(\[Sum]\), \(j = 0\), \(\[LeftFloor]
\*FractionBox[\(q\), \(Prime[i]\)]\[RightFloor]\)]
\*SuperscriptBox[\(x\), \(j*Prime[i]\)])\)\), x, q]] // Timing
(*
-> {8.36181, 10003}
*)

我用纯粹的结构操作重写为

With[{q = 80},
 Coefficient[Times @@ 
 Table[Plus @@ Table[x^(j*Prime[i]), {j, 0, Floor[q/Prime[i]]}],
        {i, 1, PrimePi[q]}], x, q]] // Timing
(*
-> {8.36357, 10003}
*)

（这只是建立一个术语列表，然后将它们相乘，因此不执行符号分析）。

只是建立多项式是瞬时的，但它有几千项，所以可能发生的事情是Coefficient花费大量时间来确保它具有正确的系数。实际上，您可以通过Expand多项式来解决这个问题。因此：

 With[{q = 80}, Coefficient[Expand[\!\(
 \*UnderoverscriptBox[\(\[Product]\), \(i = 1\), \(PrimePi[q]\)]\((
 \*UnderoverscriptBox[\(\[Sum]\), \(j = 0\), \(\[LeftFloor]
 \*FractionBox[\(q\), \(Prime[i]\)]\[RightFloor]\)]
 \*SuperscriptBox[\(x\), \(j*Prime[i]\)])\)\)], x, q]] // Timing
 (*
 -> {0.240862, 10003}
 *)

它也适用于我的方法。

总而言之，只要坚持Expand在表达式前面和取系数之前。

于 2011-06-26T19:21:14.270 回答
1

我认为原始代码缓慢的原因是因为Coefficient即使使用非常大的表达式也可以工作 - 如果天真地扩展这些表达式将不适合内存。

这是原始多项式：

poly[q_, x_] := Product[Sum[ x^(j*Prime[i]), 
                            {j, 0, Floor[q/Prime[i]]}], {i, 1, PrimePi[q]}]

看看如果不是太大q，扩展多项式会占用更多内存并且变得相当慢：

In[2]:= Through[{LeafCount, ByteCount}[poly[300, x]]] // Timing
        Through[{LeafCount, ByteCount}[Expand@poly[300, x]]] // Timing
Out[2]= { 0.01, { 1859,   55864}}
Out[3]= {25.27, {77368, 3175840}}

现在让我们以 3 种不同的方式定义系数并为它们计时

coeff[q_]    := Module[{x}, Coefficient[poly[q, x], x, q]]
exCoeff[q_]  := Module[{x}, Coefficient[Expand@poly[q, x], x, q]]
serCoeff[q_] := Module[{x}, SeriesCoefficient[poly[q, x], {x, 0, q}]]

In[7]:= Table[   coeff[q],{q,1,30}]//Timing
        Table[ exCoeff[q],{q,1,30}]//Timing
        Table[serCoeff[q],{q,1,30}]//Timing
Out[7]= {0.37,{0,1,1,1,2,2,3,3,4,5,6,7,9,10,12,14,17,19,23,26,30,35,40,46,52,60,67,77,87,98}}
Out[8]= {0.12,{0,1,1,1,2,2,3,3,4,5,6,7,9,10,12,14,17,19,23,26,30,35,40,46,52,60,67,77,87,98}}
Out[9]= {0.06,{0,1,1,1,2,2,3,3,4,5,6,7,9,10,12,14,17,19,23,26,30,35,40,46,52,60,67,77,87,98}}

In[10]:=    coeff[100]//Timing
          exCoeff[100]//Timing
         serCoeff[100]//Timing
Out[10]= {56.28,40899}
Out[11]= { 0.84,40899}
Out[12]= { 0.06,40899}

所以SeriesCoefficient绝对是要走的路。当然，除非您在组合数学方面比我好一点，并且您知道以下素数分区公式（oeis）

In[13]:= CoefficientList[Series[1/Product[1-x^Prime[i],{i,1,30}],{x,0,30}],x]
Out[13]= {1,0,1,1,1,2,2,3,3,4,5,6,7,9,10,12,14,17,19,23,26,30,35,40,46,52,60,67,77,87,98}

In[14]:= f[n_]:=Length@IntegerPartitions[n,All,Prime@Range@PrimePi@n]; Array[f,30]
Out[14]= {0,1,1,1,2,2,3,3,4,5,6,7,9,10,12,14,17,19,23,26,30,35,40,46,52,60,67,77,87,98}
于 2011-06-26T23:24:19.203 回答