Program to calculate square root c++

Question

I am making a C++ program to calculate the square root of a number. This program does not use the "sqrt" math built in operation. There are two variables, one for the number the user will enter and the other for the square root of that number. This program does not work really well and I am sure there is a better way to do so:

Here is my full code:

#include <iostream>
using namespace std;

int main(){
  int squareroot = 0;
  int number;

  cout << "enter a number sp that i can calculate its squareroot" << endl;

  cin >> number;

  while (squareroot * squareroot != number){

      squareroot+=0.1;

}
cout << "the square root is" << squareroot << endl;
return 0;
 }

I know there must be a better way. Pls help. Looked through Google but don't understand the complex programs there as I am still a beginner.

Thanks in advance.

Answer 1

Below explanation is given for the integer square root calculation:

In number theory, the integer square root of a positive integer n is the positive integer m which is the greatest integer less than or equal to the square root of n

The approach your started is good but needs several correction to make it work:

1. you are working with int you want to add 1 to squareroot not 0.1

2. you want to stop your calculation when you squareroot * squareroot is equal or greater than number. Think about the case were the number is 26, you don't have an integer that multiplies itself to 26.

3. in the case of number equal to 26, do you want to return 5 or 6? After your while loop the value of squareroot will be 6 so you might want to reverse it to 5 (if squareroot * squareroot is different than number)

Below the exemple:

#include <iostream>
using namespace std;

int main(){
  int squareroot = 0;
  int number;

  cout << "enter a number sp that i can calculate its squareroot" << endl;

  cin >> number;

  while (squareroot * squareroot < number){
      squareroot+=1;
  }

  if (squareroot * squareroot != number) --squareroot;

  cout << "the square root is" << squareroot << endl;
  return 0;
}

Below a more efficient and elegant way of calculating the square root using binary search principle. O(log(n))

int mySqrt(int x) {
    if (x==0) return 0;
    int left = 1;
    int right = x/2 + 1;
    int res;

    while (left <= right) {
        int mid = left + ((right-left)/2);
        if (mid<=x/mid){
            left = mid+1;
            res=mid;
        }
        else {
            right=mid-1;
        }
    }

    return res;
}

Answer 2

This function uses Nested Intervals (untested) and you can define the accuracy:

#include <math.h>
#include <stdio.h>

double mySqrt(double r) {
  double l=0, m;
  do {
     m = (l+r)/2;
     if (m*m<2) {
        l = m;
     } else {
        r = m;
     }
  } 
  while(fabs(m*m-2) > 1e-10);      
  return m;
}

See https://en.wikipedia.org/wiki/Nested_intervals

Answer 3

This function will calculate the floor of square root if A is not a perfect square.This function basically uses binary search.Two things you know beforehand is that square root of a number will be less or equal to that number and it will be greater or equal to 1. So we can apply binary search in that range.Below is my implementation.Let me know if you don't understand anything in the code.Hope this helps.

int sqrt(int A) {
    if(A<1)return 0;
    if(A==1)return 1;

    unsigned long long start,end,mid,i,val,lval;
    start = 1;
    end = A;
    while(start<=end){
        mid = start+(end-start)/2;
        val = mid*mid;
        lval = (mid-1)*(mid-1);

        if(val == A)return mid;     
        else if(A>lval && A<val) return mid-1;
        else if(val > A)end = mid;
        else if(val < A)start = mid+1;
    }
}

Answer 4

The problem with your code, is that it only works if the square root of the number is exactly N*0.1, where N is an integer, meaning that if the answer is 1.4142 and not 1.400000000 exactly your code will fail. There are better ways , but they're all more complicated and use numerical analysis to approximate the answer, the easiest of which is the Newton-Raphson method.

you can use the function below, this function uses the Newton–Raphson method to find the root, if you need more information about the Newton–Raphson method, check this wikipedia article. and if you need better accuracy - but worse performance- you can decrease '0.001' to your likening,or increase it if you want better performance but less accuracy.

float mysqrt(float num)   {  
    float x = 1;

    while(abs(x*x - num) >= 0.001 )
        x = ((num/x) + x) / 2;

    return x;

}  

if you don't want to import math.h you can write your own abs():

float abs(float f) {
    if(f < 0)
        f = -1*f;
    return f;
}

Answer 5

Square Root of a number, given that the number is a perfect square.

The complexity is log(n)

/**
 * Calculate square root if the given number is a perfect square.
 * 
 * Approach: Sum of n odd numbers is equals to the square root of n*n, given 
 * that n is a perfect square.
 *
 * @param number
 * @return squareRoot
 */
public static int calculateSquareRoot(int number) {

    int sum=1;
    int count =1;
    int squareRoot=1;
    while(sum<number) {
        count+=2;
        sum+=count;
        squareRoot++;
    }
    return squareRoot;
}

Answer 6

#include <iostream>
using namespace std;
int main()
{
    double x = 1, average, s, r;
    cout << "Squareroot a Number: ";
    cin >> s;
    r = s * 2;
    for ( ; ; ) //for ; ; ; is to run the code forever until it breaks
    {
        average = (x + s / x) / 2;
        if (x == average)
        {
            cout << "Answer is : " << average << endl;
            return 0;
        }
        x = average;
    }
}

You can try my code :D the method that i used here is the Babylonian Squareroot Method which you can find it here https://en.wikipedia.org/wiki/Methods_of_computing_square_roots