Question

In this assignment, we will implement a square root approximater and then an nth root approximater. Recall that the nth root of x is the number when raised to the power n gives x. We learned in class that we can use the concepts of binary search to approx imate the square root of a number, and we can continue this logic to approximate the nth square root. Please look at Lecture Notes 03, section 4 for a little more detail. We're going to use the concepts of binary search to try and approximate nding the square root and nding the nth root.

You may not use any library functions for these question, except DecimalFormat.

In this assignment, we will implement a square root approximater and then an nth root approximater. Recall that the nth root of x is the number when raised to the power n gives x. We learned in class that we can use the concepts of binary search to approx imate the square root of a number, and we can continue this logic to approximate the nth square root. Please look at Lecture Notes 03, section 4 for a little more detail. We're going to use the concepts of binary search to try and approximate nding the square root and nding the nth root. You may not use any library functions for these question, except DecimalFormat.

Answer 1

• Since there are no infomation the precision that the root must have, we will caluculate the root to 13 decimal places

Program plan:

Square root of n:

• We will use binary search approach to calculate the sqaure root of n
• intialize a variable low = 0 and another variable high to n.
• declare a double variable root.
• while low<high do the following:
  • Set a variable mid to (low+high )/2
  • if mid*mid is equal to n, then set root = mid and break from loop
  • if mid*mid < n then, the root must be greater than mid. Set low = mid+1
  • if mid*mid > n then, the root must be less than mid, Set high = mid-1
  • Set root = mid
• Now we will caluculate the decimal part of the root to 13 decimal place.
• declare a variable decimal = 0.1
• loop 13 times:
  • while root*root <= n, increment root by decimal
  • divide decimal by 10 and store it to decimal
• the resulting root value is the required root

pth root of n:

• The steps to solve pth root of n follows the same steps as square root algorithm
• Only change, is that we must calculate mid^p in the places we caluculate mid*mid and calculate root^p in the places we calculate root*root
• We will use Math.pow() to calculate mid^p and root^p

Program with sample main():

import java.io.*;
import java.util.*;

class Roots
{
   static double root2(int n){
       int low = 0, high = n;
       int mid;
       double root = 0.0;
       while(low<high){
           mid = (low+high)/2;
           //System.out.println(low);
           //System.out.println(mid);
           //System.out.println(high);
           if(mid*mid==n){
               root = mid;
               break;
           }
           else if(mid*mid<n){
               low = mid+1;
           }
           else{
               high = mid-1;
           }
           root = mid;
       }
       double decimal = 0.1;
       int i = 0;
       while(i<13){
           while(root*root<=n){
               root += decimal;
           }
           root -= decimal;
           decimal /= 10;
           i+=1;
       }
       return root;
   }

   static double rootn(int n, int p){
       int low = 0, high = n;
       int mid;
       double root = 0.0;
       while(low<high){
           mid = (low+high)/2;
           //System.out.println(low);
           //System.out.println(mid);
           //System.out.println(high);
           if(Math.pow(mid,n)==n){
               root = mid;
               break;
           }
           else if(Math.pow(mid,n)<n){
               low = mid+1;
           }
           else{
               high = mid-1;
           }
           root = mid;
       }
       double decimal = 0.1;
       int i = 0;
       while(i<13){
           while(Math.pow(root,n)<=n){
               root += decimal;
           }
           root -= decimal;
           decimal /= 10;
           i+=1;
       }
       return root;

   }
   public static void main(String[] args){
       System.out.print("square root of 28: ");
       System.out.println(root2(28));
       System.out.print("5th root of 28: ");
       System.out.println(rootn(28,5));
   }
}

Sample output: