CODEWITHSUNDEEP
arrayslinked-list
user379888
user379888

Reputation:

Array Representation of Polynomials

I was reading about linked list implementation of polynomials. It stated,

Compare this representation with storing the same
polynomial using an array structure.
In the array we have to have keep a slot for each exponent
of x, thus if we have a polynomial of order 50 but containing
just 6 terms, then a large number of entries will be zero in
the array.

I was wondering how do we represent a polynomial in an array? Please guide me.

Thanks

Upvotes: 0

Views: 14421

Answers (4)

Ray Toal
Ray Toal

Reputation: 88418

A complete Java implementation of array-based polynomials is here: https://cs.lmu.edu/~ray/classes/dsa/assignment/2/answers/

The basic idea is that if you have a polynomial like

4x^6-2x+5

then your array would look like

   0     1    2    3    4    5    6
+----+-----+----+----+----+----+----+
| 5  |  -2 |  0 |  0 |  0 |  0 |  4 |
+----+-----+----+----+----+----+----+

That is

  • the coefficient 5 is in slot 0 of the array (representing 5x^0)
  • the coefficient -2 is in slot 1 of the array (representing -2x^1)
  • the coefficient 4 is in slot 6 of the array (representing 4x^6)

You can probably see how this represenation would be wasteful for polynomials like

3x^5000 + 2

In cases like this you want instead to use a sparse array representation. The simplest approach would be to use a map (dictionary) whose keys are the exponoents and whose values are the coefficients.

Upvotes: 6

Davide Aversa
Davide Aversa

Reputation: 5988

If you have a polynomial function like

3x^4 + x^2 + 2x + 1 = 0

You can represent it in array as

[1 2 1 0 3]

So, the element 0 is the coefficient of x^0, element 1 is the coefficient of x^1 and so on...

Upvotes: 1

amit
amit

Reputation: 178491

usually you hold one element for each exponent, so the polynom is actually:
poly[0]*x^0 + poly[1]*x^1 + ... + poly[n-1]*x^(n-1)

for example. if you have p(x) = 3x^5+5x^2+1, your array will be:

poly[0] = 1
poly[1] = 0
poly[2] = 5
poly[3] = 0
poly[4] = 0
poly[5] = 3

Upvotes: 1

Feanor
Feanor

Reputation: 670

Suppose your polynomial is

6x^50 + 4x^2 + 2x + 1

The paragraph you have posted is describing storing it in an array like this:

polynomial = new array(50)  // I'm assuming all elements initialize to zero
polynomial[50] = 6
polynomial[2] = 4
polynomial[1] = 2
polynomial[0] = 1

Basically its wasting a lot of space this way. Here the array index is the 'power' of x for the polynomial in x.

Upvotes: 1

Related Questions