Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 PolynomialRatioSeriesCoefficient

Source Notebook

Calculate the coefficient of series P(x)/Q(x) in front of x^n, where P(x) and Q(x) are polynomials in x

Contributed by: Illia Voinovskyi

ResourceFunction["PolynomialRatioSeriesCoefficient"][p,q,x,n]

Calculates the coefficient of series in front of xn, where P(x) and Q(x) are polynomials in x.

Details

PolynomialRatioSeriesCoefficient is much faster version of SeriesCoefficient specifically tailored for a ratio of 2 polynomials.
PolynomialRatioSeriesCoefficient can be used to analyze behavior of generating functions and recursive equations with high values of n.
This algorithm was mentioned in Schönhage's article and is inspired by Graeffe's method.
The complexity of this method can be estimated as O(pLog[n]), where n is the coefficient sought and p is the degree of the input polynomials.

Examples

Basic Examples (2) 

The coefficient in front of x5 of series expansion of is 8:

In[1]:=
Series[1/(1 - x - x^2), {x, 0, 10}]
Out[1]=

Get the same result with PolynomialRatioSeriesCoefficient:

In[2]:=
ResourceFunction["PolynomialRatioSeriesCoefficient"][1, 1 - x - x^2, x, 5]
Out[2]=

Scope (1) 

PolynomialRatioSeriesCoefficient supports symbolic computation:

In[3]:=
ResourceFunction["PolynomialRatioSeriesCoefficient"][c, 1 - a x - b x^2, x, 5]
Out[3]=

Applications (3) 

Attempting to find a faraway coefficient of a recursive function, is time consuming with RecurrenceTable:

In[4]:=
TimeConstrained[ Last@RecurrenceTable[{f[n + 3] == f[n + 1] + f[n] + 1, f[0] == 0, f[1] == 0, f[2] == 0}, f, {n, 1, 10^6}], 1]
Out[4]=

For a faster solution, first find the generating function:

In[5]:=
GeneratingFunction[f[n + 3] == f[n + 1] + f[n] + 1, n, x] /. {f[0] -> 0, f[1] -> 0, f[2] -> 0}
Out[5]=
In[6]:=
gf = First@SolveValues[%, GeneratingFunction[f[n], n, x]]
Out[6]=

Then use PolynomialRatioSeriesCoefficient to find a very faraway coefficient:

In[7]:=
Timing[Short[ ResourceFunction["PolynomialRatioSeriesCoefficient"][Numerator@gf, Denominator@gf, x, 10^6]]]
Out[7]=

Properties and Relations (2) 

PolynomialRatioSeriesCoefficient returns the same value as SeriesCoefficient

In[8]:=
ResourceFunction["PolynomialRatioSeriesCoefficient"][1, 1 - x - x^2, x, 10]
Out[8]=
In[9]:=
SeriesCoefficient[1/(1 - x - x^2), {x, 0, 10}]
Out[9]=

However PolynomialRatioSeriesCoefficient is much faster for large orders:

In[10]:=
Timing[Short[ ResourceFunction["PolynomialRatioSeriesCoefficient"][1, 1 - x - x^2, x, 10^6]]]
Out[10]=
In[11]:=
TimeConstrained[ Short[SeriesCoefficient[1/(1 - x - x^2), {x, 0, 10^6}]], 1]
Out[11]=

Neat Examples (3) 

Find out how many ways exist to represent 4000 as different sums of numbers {2,3,5}:

In[12]:=
Timing[IntegerPartitions[4000, All, {2, 3, 5}] // Length]
Out[12]=

Same result can be obtained much faster using generating function method and PolynomialRatioSeriesCoefficient:

In[13]:=
Timing[ResourceFunction["PolynomialRatioSeriesCoefficient"][ 1, (1 - x^2) (1 - x^3) (1 - x^5), x, 4000]]
Out[13]=

PolynomialRatioSeriesCoefficient can calculate for large numbers quickly:

In[14]:=
Timing[ResourceFunction["PolynomialRatioSeriesCoefficient"][ 1, (1 - x^2) (1 - x^3) (1 - x^5), x, 10^18]]
Out[14]=

Publisher

Illia Voinovskyi

Requirements

Wolfram Language 13.0 (December 2021) or above

Version History

  • 1.0.0 – 25 November 2024

Source Metadata

  • Citation:
    • Householder, Alston Scott (1959). "Dandelin, Lobačevskiǐ, or Graeffe". The American Mathematical Monthly. 66 (6): 464–466. doi:10.2307/2310626. JSTOR 2310626.

Related Resources

License Information