ICT101 Assignment: Polynomial Evaluation Algorithm Investigation

This report delves into the realm of polynomial evaluation algorithms, crucial in high-performance DSP algorithms, digital circuits, and various applications like cryptography and speech recognition. It addresses the problem of efficiently evaluating polynomials, providing a general format and highlighting real-world uses such as in economics, engineering, and traffic control. The report presents a solution using the Horner rule, detailing the algorithm, cost analysis, and nested multiplication techniques. It concludes by emphasizing the broad applicability of polynomial algorithms across diverse sectors, including technology, engineering, and statistics, underscoring their role in accurate modeling and prediction, and encouraging their use for effective decision-making and service delivery. The report also includes reflections from group members on their contributions and insights gained from the assignment.

Polynomial evaluation algorithm
Introduction
Polynomials are always applied in high performance DSP algorithms to estimate the computation
of functions or parametrical modelling of the systems. Several basic digital circuits has the
polynomial evaluation algorithm such as high precision elementary functional evaluation circuits
and digital filters. In fact, at a system level, many applications such as cryptography, speech
recognition and communications, involve the computation of polynomials. Researchers have
always investigated the polynomials with the major challenge being speed of computation.
Polynomials are majorly beneficial as they only apply multiplication and addition. High degree
polynomials usually involve multiple word length multiplications which are time consuming.
This can always be reduced through a low latency application that can be through hard or
software approaches (Xu, 2013).
Problem statement of the polynomial evaluation algorithm
The problem of polynomial evaluation can be summarized as follow. Using a general format for
kth degree polynomial evaluation,
f ( x ) = ∫
i =1
k
ai xi ; x=input of the polynomial with a set of coefficient a1 of a constant value
The coefficient can be obtained by various algorithms. The coefficient will not be frequently
changed although they could be updated from one time to another. The range of the coefficient
and input x is defined to be (0, 1) enhancing accuracy in analysis to be performed later (Higham,
2002).

Real world uses of polynomials
Polynomials are often applied in a supermarket for instance, when one wants to know the
different good prices, let’s say a price for one bundle of flour, five crates of whiskey and one box
of milk then there is need to design a simple polynomial before going to prices. With the algebra
ready, one will be able to fix prices and determine the amount of cash that he/she will be able to
spend (Gohberg, Lancaster, & Rodman, 2009).
Professionals who are most likely to apply the polynomials on their day to day activities are
those who make complex calculations. A roller coaster designing engineer would use
polynomials to model curves as well as civil engineers who apply polynomials in road, building
and other structure designing.
Polynomials can as well be used in predicting the traffic patterns enabling appropriate control
measures on the traffic for example traffic lights.
Economists apply polynomial in modelling economic growth patterns as well as medical
researchers using the polynomials to establish and designate the bacteria colony.
The drivers also apply polynomials in calculating distance covered versus the amount of money
to be paid.
Solution to the problem
In the field of economics and statistics, there is always need to determine trends and make of
relevant conclusions. Economists often try to use polynomials in predicting demand and price
relationships (Pan, 2016). Suppose a simplified polynomial predicting the demand for a new
gadget as a function of price p (in dollars) over the interval 0 < p < 150 given by,

D ( p ) =0.006 p2−3.5 p+250
Then the average rate in change in demand as price goes from 75 dollars to 80 dollars then we
can apply the polynomial,
Average rate∈change=D ( p )=0.006 p2−3.5 p+250
D ( p1=75 ) =0.006(75)2−3.5 ( 75 ) +250=21.25
D ( p1=80 ) =0.006(80)2−3.5 ( 80 ) +250=8.4
Therefore, the average rate of change is given as follows;
∆= 8.4−21.25
(80−75) =−2.57
This shows that the demand changes by 2.57 whenever the price increases.
Possible algorithm (How computing can be useful in providing the solution discussed in
section 4)
The Horner rule is the algorithm that can be used in solving the above problem (Cahen &
Chabert, 2017).
Considering the following polynomial
p ( x ) =a0 + a1 x1 +a2 x2+ a3 x3 +…+ an xn
The idea behind the above polynomial is to evaluate the number of x values.
The standard way to evaluate the algorithm is to write it in some form of algorithmic format as
follows;

poly=a0
for j=1 :n
poly= poly+ aj x j
end
In order to do a comparison of the costs for the various numerical techniques, an operation count
is done and then a comparison is done for the competing techniques. The counts are presented as
follows;
additions :n
multiplications :1+2+3+…+n= n ( n+1 )
2
The above algorithm makes an assumption that each term a j x j is calculated independently based
on the remaining terms of the given polynomial.
The next step is to perform the terms x j recursively such that:
x j= x . x j−1
We then calculate { x2 , x3 , x4 , x5 , … , xn } which will cost (n−1) times.
The algorithm becomes;
poly=a0 +a1 x
power=x
for j=2:n

power=x . power
poly= poly+ aj . power
end
poly= poly+ aj x j
end
From the algorithm, the total cost of operations becomes;
additions :n
multiplications :n+n−2=2 n−1
Supposing that n is moderately large then we would expect a value less than p(x). For instance, if
we have n as being equal to 20, the 1st method will have 210 multiplications while the 2nd one
will have 39 multiplications.
Next, we consider now a nested multiplication. We have;
n=2: p ( x )=a0 +x (a1 +a2 x)
n=3 : p ( x ) =a0 + x (a1 + x ( a2 +a3 x ) )
n=4 : p ( x ) =a0 +x (a1 + x (a2 + x (a3+ a4 x)))
The above have 2, 3, and 4 multiplications respectively. The values are actually less as compared
to the preceding method which have the multiplications as 3, 5, and 7 respectively.
The general algorithm can be thought of as follows;
p ( x )=a0 + x ( a1+ x ( a2+ x ( a3+ a4 x ) )+ x (an−1 + an x ) …)¿

The above needs about n multiplications which is actually a half of what we have for the
preceding method. The general algorithm can be written as follows;
poly=a0
for j=n−1 :−1:0
poly=aj +x . poly
end
From all the above methods, the number of additions is seen to be n; however, the number of
multiplications significantly vary for the large value of n.
Conclusion
Polynomial algorithms can be applied in several sectors in the world. The polynomial methods
are useful in designing, predicting, and showing the different types of changes that can occur for
instance, predicting the demand change with changes in price and supply. Accurately designed
roads, dams, houses and several other structures are easily done through polynomial formulas.
Computers and several other forms of technology are designed and programmed using the
polynomials. Statisticians applying polynomials in the necessary conclusions tend to be more
accurate.
The polynomials should thus be used so that mathematically accurate conclusions and accurate
modelling for proper display and interpretation can be realized. Governments can thus use
conclusions and polynomially designed programs to deliver services to the citizens and even
personal businessmen.

Short statement about contributions/Reflections from each group member
1st group member
Polynomials when well applied, can enable various sectors in the world; technological,
engineering, social, academicals and very many other sectors come up with a well laid down
strategies resulting to effective outcome. The Horner’s Rule, Dorn’s Method, parallel method
and Estrin’s Method give definite and accurate solutions towards the rising problems and the
dynamic issues of the world. The research about polynomials should thus continue in order to
ensure that better technology is realized with long lasting infrastructure.
2nd group member
Polynomials should be applied in our day to day activities. This will enable us plan well for the
money and the possession we have in control, for instance, when a driver apply well the
polynomial rules, he/she will be able to determine without losses the distance and payment to be
made. Those going for shopping can also plan well what they need to avoid overspending,
economists are able to calculate trends and patterns; these help in making future plans and
preparations that could otherwise lead to ambush. Technologically, the polynomial evaluation
algorithm functions enables a more resilient, long lasting and adorable quality items that can take
the world to other levels.
3rd group member
It was really very interesting working on this topic. I came to realize that polynomials have lots
of applications in the real life. Our lives depend or undergo some sort of polynomials. The cost,
demand and even the supply functions greatly apply the concept of polynomials. The engineers,
medicine, economics among other disciplines have great applications of polynomials. I do

encourage my fellow students to take the topic on polynomials more serious and fully understand
on how to apply it in our day to day life.
References

Cahen, P.-J., & Chabert, J.-L. (2017). Integer-Valued Polynomials. American Mathematical
Society, 5(2), 45-61.
Gohberg, I., Lancaster, P., & Rodman, L. (2009). Matrix Polynomials:Classics in Applied
Mathematics. Society for Industrial and Applied Mathematics, 4(1), 58-76.
Higham, N. (2002). Accuracy and Stability of Numerical Algorithms. SIAM, 5(6), 25-36.
Pan, Y. J. (2016). On means of calculating values of polynomials. Russian Math. Surveys, 105–
136.
Xu, S. (2013). E cient Polynomial Evaluation Algorithm and Implementation on FPGA.ffi
Journal of Mathematics, 6(3), 2-8.