PDS Section
3
Date: 1st feb 2010
Week 4
Part 1.
Fie to submit: primepalin.c
An integer is
said to be a palindrome if it is equal to its reverse. For example,
79197 and
324423 are palindromes. In this task you will be given an integer N, 1
≤ N ≤
1000000. You must find the smallest integer M ≥ N such that M is a
prime number
and M is a palindrome.
For
example, if
N is 31 then the answer is 101.
Input
A
single
integer N, (1 ≤ N ≤ 1000000)
Output
Your
output
must consist of a single integer, the smallest prime palindrome greater
than or
equal to N.
Part 2. File to submit: rootfind.c,
root.out
a) Write
a fundtion double
power (double x, int n) to compute x to the power n.
b)
double nRootBisection(double y, int n)
computes the n-th root of y via bisection method. This
function should make calls to the power( ) function defined in 1.
A root is to be found with a tolerance of 0.000001. Print the number of
iterations required.
Bisection method: Bisection is a numerical algorithm for iteratively
converging on a solution of a function f(x) known to lie inside some
interval [a,b]. The algorithm evaluates the function f(x) at the
midpoint of the interval [a,b], x = (a+b)/2. and then tests
to see in which of the subintervals [a,(a+b)/2] or [(a+b)/2,b] the
solution lies. This procedure is then repeated with the new
interval, as often as needed to locate the solution within the desired
accuracy.
For the problem of finding the n-th root of y, we want to solve
for the value x such that f(x)
= xn - y = 0.
c) Newton-Raphson
algorithm: Another numerical algorithm for converging on
a numerical solution of
f(x) = xn - y = 0 is the Newton-Raphson method. This
algorithm starts with an initial guess for x and then at each
iteration updates the estimated x using the equation: x = (x - f(x)) /
f'(x), where f'(x) is the first derivative. This process is repeated
until the change in x is within the numerical tolerance interval around
zero.
Write the function
double nRootNewton(double y, int n)
to implement this method. Print the root found and the number of iterations required to find a
root with a tolerance of 0.000001.
d) Write
a main( ) function that tests the above functions to calculate
the following:
- Find the value of 2.3175
- Find the 4th root of 630
- Find the 10th root of 2000
- Find the 20th root of 1000000
- and a few more examples