Square Root

[jasongog]

I was wondering if i can make a program which finds the square root of a number without using sqrt().
Can anyone help me?

[TheIdeasMan]

Yes you can.

Have you looked on wiki to see how to use a binomial series to calc a square root?

Have you written any pseudo code? A recipe for how you are going to do the problem.

Do you have any code at all?

[amchinese]

Of course you can.
On my Math book, there is a method, that is to try digitals one by one.
For example, suppose you want to get sqrt(101). Because 0^2=0,10^2=100, 20^2=400 and so on, sqrt(101) is between 10 and 20(for, (sqrt(101))^2 is between 10^2 and 20^2). And then you try next digital.
For computer programming, I suggest you to use binary digits for faster compute.

[Stormboy]

Yes its perfectly possible to do that. The easiest way I know of is to use the "Bakhshali approximation". The one I implemented gives results accurate to 5 decimal places.

Here is the one I made (its not very efficient but it does the work):

#include <iostream>

//We use the Bakhshali approximation method
float sqroot(float s)
{
    int pSq = 0; //This will be the nearest perfect square to s
    int N = 0; //This is the sqrt of pSq
    
    //Find the nearest perfect square to s
    for(int i = static_cast<int>(s); i > 0; i--)
    {
        for(int j = 1; j < i; j++)
        {
            if(j*j == i)
            {
                pSq = i;
                N = j;
                break;
            }
        }
        if(pSq > 0)
            break;
    }
    
    float d = s-pSq;
    float P = d/(2.0*N);
    float A = N+P;
    float sqrt_of_s = A-((P*P)/(2.0*A));
    return sqrt_of_s;
    
}

int main()
{
    float num;
    std::cout << "Enter a num: ";
    std::cin >> num;
    float sqroot_of_num = sqroot(num);
    std::cout << "sqrt(" << num << ") = " << sqroot_of_num << std::endl;
    return 0;
}

[jasongog]

Thank you.

[TheIdeasMan]

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Exponential_identity

This is the wiki page, I was thinking of the Taylor series, but this is better & easy to implement.

It would be great for you to have a go at this - we look forward to seeing your code. Hopefully Stormboy hasn't just done your homework for you.

[SorinAlex]

http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi

[TheIdeasMan]

@SorinAlex

Interesting about the last 2 methods using asm, Cubbi posted some source code the other day which showed the normal sqrt using the sqrt instruction.

Cubbi wrote:

sqrt: https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/fpu/e_sqrtf.c;h=e928529a906bb7e9fa7097dc54c5cd8657d115f4;hb=HEAD

[TheIdeasMan]

@jasongog

Can you figure out how to put these together, to do the exponential formula?

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Exponential_identity

http://www.cplusplus.com/reference/cmath/exp/
http://www.cplusplus.com/reference/cmath/log/
http://www.cplusplus.com/reference/cmath/pow/

I know the maths is tough at your age, but if you can figure this out it would be great.

[jasongog]

@TheIdeasMan: It is not for homework. It was for curiosity.

[jasongog]

I understood Stormboy's code except one thing.
What does static_cast<int>(s) do?

[TheIdeasMan]

Have a read of this:

http://www.cplusplus.com/doc/tutorial/typecasting/

int i = static_cast<int>(s)

It changes s from a float to an int then assigns it to i

[Zhuge]

@jasongog: Why did you delete your post? Now I can only guess what question was being answered.

[jasongog]

So i can do static_cast<string> (num) to convert an int to a string?