ECE 175 Computer Programming for Engineering Applications
Homework Assignment 3
Conventions: Name your C programs hwxpy.c where x corresponds to the homework number, and y corresponds
to the problem number. For example, the C program for homework 3, problem 1 should be named as hw3p1.c.
Write comments to your programs. Programs with no comments will receive PARTIAL credit. For each program that you turn in, at least the following information should be included at the beginning of your file as comments
• Author:
• Date created:
• Brief description of the program:
– input(s):
– output(s):
– brief description or relationship between inputs and outputs
Submission Instructions: Use the dropbox on D2L to submit your homework. Submit the hw3p1.c and hw3p2.c files plus the video answering the questions. Also, run your code via Zybooks.
1 Perfect Numbers (35 points)
A positive integer is said to be a perfect number if it equals the sum of its positive divisors (excluding the number itself). As an example, 6 is a perfect number because its divisors, 1, 2, and 3 sum up to 6.
The first four perfect numbers are 6, 28, 496, 8128.
Write a C program that asks the user to enter a number and checks if the number is perfect. Your program should run interactively until the user quits. Try to minimize the program execution time by using the least number of iterations for finding the divisors of the user’s input. Record and report the number of iterations executed for checking if a number is perfect.
Sample Code Execution: Red text indicates information entered by the user
Enter a perfect number:1
Number 1 is not perfect
Number of iterations:0
Do you want to continue (y/n)?y
Enter a perfect number:6
Number 6 is perfect
Number of iterations:3
Do you want to continue (y/n)?y
Enter a perfect number:67
Number 67 is not perfect
Number of iterations:33
Do you want to continue (y/n)?y
Enter a perfect number:496
Number 496 is perfect
Number of iterations:248
Do you want to continue (y/n)?n
Goodbye
2 Polynomial Root Calculation: Problem Description (25 points)
Engineers often need to calculate the roots of a given polynomial. For low-order polynomials, these computations can be done by hand. For higher-order polynomials, these calculations can be cumbersome, if not impossible, without a computer. One method of finding real roots of a polynomial is the Newton-Raphson algorithm.
We wish to write a C program that uses the Newton-Raphson method for calculating the roots of a polynomial. Although this program will not be able to solve for complex roots, it will be able to calculate real roots; maybe later we can adjust the routine to include complex roots. Since it is possible that the polynomial roots are all complex, i.e. no real roots at all, it may be that the Newton-Raphson routine fails to converge.
2.1 Newton-Raphson Algorithm:
Write a program that prompts the user to input the coefficients c0, c1, . . . , c5 of a 5th-order polynomial and an initial value x that serves as a the starting condition for the Newton-Raphson algorithm.
The 5th-order polynomial has the form
y=c5 ·x5 +c4 ·x4 +c3 ·x3 +c2 ·x2 +c1 ·x+c0
We know that the first derivative of y with respect to x is
dy =y′ =5·c5 ·x4 +4·c4 ·x3 +3·c3 ·x2 +2·c2 ·x+c1
dx
We can use this information to find the roots of the polynomial. The basic idea, in the Newton-Raphson method, is as follows:
(a) Given an initial guess x, and polynomial coefficients c, calculate y
(b) Check to see if y is close enough to zero, i.e. within some small tolerance close to zero.
(i) If so then terminate. Algorithm has converged! (ii) If not then continue
(c) Use the current value of x to calculate y′
(d) Create a new guess for x using the update formula x = x − y
y′ (e) Increment a counter to count the number of algorithm iterations
(f) Check to see if the number of iterations has exceeded a predetermined count limit (say 500) (i) If so then terminate. Algorithm has failed!
(ii) If not then return to step a
This same information is described in the flow chart below:
Page 2
Prompt user for inputs
Use current value of x to calculate y
Is y close to zero?
no
Use current value
of x to calculate y′
Update x x=x−y
yes
y′
Report success
Display x as one of the roots
no
Increment a counter to keep track of the number of iterations
Is count too large?
yes Report failure
Stop
If a solution is not found within 500 iterations then terminate your code and report failure. Failure to converge occurs
if the polynomial roots are all complex; for example, if the user enters c = 0,c = 0,c = 0,c = 1,c = 2,c = 3. 543210
√ These coefficients equate to a second order polynomial y = x2 + 2x + 3, with roots x = −1 ± i 2
The search algorithm has converged when y(x) = 0. Since y is a floating point variable it will most likely never actually equal zero. Calculate the polynomial root with a tolerance of ε ≤ 1E − 8
Make sure your program reports out the following:
• The polynomial that the user has entered
• The initial guess that the user has entered
• Whether or not the Newton-Raphson algorithm converged to a solution • If successful, the root of the polynomial that the algorithm found
• The number of iterations that the Newton-Raphson algorithm required to converge to a solution
Also, add any numerical protections to the algorithm that you find necessary HINT: Divide by zero protection?
Page 3
2.2 Test your program
Fill out the following table to test your program
Test Case c5 c4 c3 c2 c1 c0 x0 Converged? Root 1 -2 2? 3? 4? 5? 6? 7? 8? 9?
10 ?
2.3 Sample Code Execution
Sample Code Execution: Red text indicates information entered by the user
This program is to find one root of 5th-order polynomial using Newton-Rhapson method.
c5x^5 + c4x^4 + c3x^3 + c2x^2 + c1x + c0
Enter polynomial coefficients: c5 c4 c3 c2 c1 c0 in this order:
0 0 1 -3 -760 -1500
Your polynomial is 1.0x^3 + -3.0x^2 + -760.0x + -1500.0
Enter initial guess for x: 0
One of the roots of this polynomial is -2.000000
It takes 3 iterations to obtain this answer.
Sample Code Execution: Red text indicates information entered by the user
This program is to find one root of 5th-order polynomial using Newton-Rhapson method.
c5x^5 + c4x^4 + c3x^3 + c2x^2 + c1x + c0
Enter polynomial coefficients: c5 c4 c3 c2 c1 c0 in this order:
0 1 -4 1 36 200
Your polynomial is 1.0x^4 + -4.0x^3 + 1.0x^2 + 36.0x + 200.0
Enter initial guess for x: 8
The algorithm failed; roots may be complex
Sample Code Execution: Red text indicates information entered by the user
This program is to find one root of 5th-order polynomial using Newton-Rhapson method.
c5x^5 + c4x^4 + c3x^3 + c2x^2 + c1x + c0
Enter polynomial coefficients: c5 c4 c3 c2 c1 c0 in this order:
123456
Your polynomial is 1.0x^5 + 2.0x^4 + 3.0x^3 + 4.0x^2 + 5.0x + 6.0
Enter initial guess for x: 50
One of the roots of this polynomial is -1.491798
It takes 23 iterations to obtain this answer.
0
0
1
-3
-760
-1500
0
Yes
0
0
1
-3
-760
-1500
-20
Yes
0
0
1
-3
-760
-1500
50
Yes
0
1
-4
1
36
200
8
?
1
2
3
4
5
6
50
?
0
1
9.7
-23.8
-179.5
285
-20
?
0
1
9.7
-23.8
-179.5
285
-8
?
0
0
0
1
-20
75
0
?
0
0
0
1
-20
75
10
?
0
0
0
1
-20
75
11
?
Page 4
3 Number-to-text Converter (10 points)
You are asked to implement an automated number-to-text conversion system for a phone company. Write a C pro- gram that receives as input an integer and converts each digit to the appropriate text word. The integer can be of variable length, but no larger than 10 digits. Assume that no phone number starts with a zero. Do not use strings, or any function from the string library.
Sample Code Execution: Red text indicates information entered by the user Please enter your phone number: 2345769854
two three four five seven six nine eight five four Test cases: 2345769854, 10004, 20030040
4 Lab 3 (30 points)
Page 5