Your task is to design algorithms to solve the following problems. For full cred

Question

Your task is to design algorithms to solve the following problems. For full credit, your algorithm must run in logarithmic time. Root-finding Given a number n Greaterthanorequalto 1 and a (user-specified) error tolerance e, you want to approximate the squareroot of n to within error tolerance e. Specifically, you want to return an x Squareroot n that satisfies |x^2 - n| lessthanorequalto e. For example, to compute the squareroot of n = 2 with e = 0.01, an acceptable answer would be x = 1.414, because 1.414^2 = 1.999396. Note that x = 1.415 is also acceptable, as 1.415^2 = 2.002225, but you only need to return a single answer. Assume that you can't perform any arithmetic functions other than addition, subtraction, multiplication, and division. Write for an efficient algorithm to solve this problem. Briefly justify a good asymptotic bound on the runtime of your algorithm in terms of n (i.e., give a runtime in terms of n assuming a fixed value of e). BONUS: Provide an asymptotic bound on the runtime of your algorithm in terms of e, for a fixed value of n. Prove your result.

Explanation / Answer

#include <stdio.h>

float squareRoot(float n)
{

float x = n; // initial approximation
float y = 1;
float e = 0.000001; /* e decides the accuracy level*/
while(x*x - n > e)
{
x = (x + y)/2;
y = n/x;
}
return x;
}

/* Driver program to test above function*/
int main()
{
int n = 50;
printf ("Square root of %d is %f ", n, squareRoot(n));
return 0;
}

//----------------------------------------output---------------------------------------------

sh-4.2$ main                                                                                                                                                                    

Square root of 50 is 7.071068

For each while loop the input decreases by x/2 + n/2*x. The time complexity in terms of n is O(log2 n)

In terms of error e, the time complexity bound is O(1/e). If e is increased, the number of iterations will be less to achieve the accuracy. If e is less, iterations will increase to get the accuracy.

  

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.