Polynomials using Arrays

Polynomials as Arrays:

Array is defined as continuous memory locations where same type of elements or data is stored.

            Let us consider a polynomial A(x) with single variable

            A(x)= a_nxⁿ  +  a_n-1x^n-1  + a_n-2x^n-2  + - - - - + a₁x   +  a₀

           

The degree of the  polynomial is n, if n!=0.  we can represent A(x) as an ordered list of coefficients using a one – Dimensional array of length n+2,  Where ‘n’ is the degree of polynomial.  The array representation of above polynomial is

A= [n, a_n-1, a_n-2, a_{n-3  - - - - - -+} a_1, a_0]

            Here A[1] is the degree of the polynomial.  A[2],A[3] - - - -A[n+2] are the coefficients in the order of decreasing exponents.  Consider a polynomial     x⁸-5x⁶ +7x³.  The Array is represented as  [ 8, 1, 0 , -5, 0, 0, 7, 0, 0, 0].

            However there are some disadvantages in this representation.  Consider a polynomial x¹⁰⁰⁰ -2.  The degree of this polynomial is 1000.  Therefore no. of elements are 1002, out of which 0 elements are 999 and non-zero elements are three i.e., [ 1000, 1, 0, 0 ,0 -------------------0, 0, -2].

            Thus above representation leads to large amount of wastage of memory.  To overcome this we use another representation where only non-zero terms are represented and zero terms are ignored.

            Consider a polynomial  x⁸-5x⁶ +7x³ .  Second method representation is as follows

            A= [3, 8, 1, 6, -5, 3, 7]

           

            A[1]= No. of terms

           A[2], A[4], A[6]  -- - - - - - are the powers of terms.

           A[3], A[5], A[7] - - - - - - -  are the coefficients of the terms

           

            The no. of elements in the array is equal to 2n+1 where n is the no. of terms i.e., A[1].

            Consider a polynomial  x¹⁰⁰⁰ -2,  the representation is

            A= [2, 1000, 1, 0 ,-2]

           

            In this representation we require just 5 locations compared to 1002 locations in first method.  Also, no. of zero elements are negligible in the second method compared to 999 in the first method.  Thus memory is preserved in second method is an efficient representation of the polynomial.

Convert the following polynomial into array representation.

1. x⁴+5x³ +6x² +1

A= [ 4, 4, 1, 3, 5, 2, 6, 0, 1]

2. x⁶⁴ – 100

A= [2, 64, 1, 0, -100]