Problem with a recursive function (check if a number is a perfect square)

▲
-2
▼

I'm trying to write, in CodeBlocks, a recursive function that check if a natural number (a long double) is a perfect square. This function called "Square" takes in input, by reference, the long double S and n (setted in the beginning at 1), a bool T and the long double to compare.

Here the code:

void Square(long double& S, long double& n, bool& T,long double k){
        S=S+2*n+1;
        n++;
        if(S==k){
             T=true;
        }

        if(S>k){
            T=false;

        }

        if(S<k){
            Square(S,n,T,k);
        }
}

And in the main function:

long double S,n,k;

bool T=false;

for(long double b=1;b<50000;b++){

    for(long double a=1;a<b;a++){

        S=1;
        n=1;
        T=false;

        k=12*a*b*b*b-3*a*a*a*a;

        Square(S,n,T,k);

        if(T==true){
            cout<<a<<"    "<<b<<"   "<<k<<endl;
        }
    }
}

Sometimes occours this error: "Process returned -1073741571 (0xC00000FD)" (for example when (a = 108 and b = 121) and the program stops. Any help?

c++
codeblocks
asked on Stack Overflow Aug 7, 2019 by Matteo • edited Aug 7, 2019 by Matteo

2 Answers

▲
1
▼

Try this:

#include <cmath>

bool isPerfectSquare( long num ) {
    long root = long(sqrt(float(num)));
    return root * root == num;
}

You'll get True if num is a perfect square or False if not.

answered on Stack Overflow Aug 7, 2019 by lenik • edited Aug 7, 2019 by J. Antonio Perez
▲
1
▼

You're probably getting a stack overflow error (which is when you use up the entirety of a thread's stack, and it crashes). If you compile with optimizations enabled, the compiler should be able to optimize Square so that it's tail-recursive, which will prevent the stack overflow error.

That being said, we can make Square shorter and friendlier to optimization by removing the references, and just calculating the multiplication directly (which is very cheap):

bool is_square(long long k, long long n = 0) {
    if(n * n >= k)
        return n * n == k;
    else
        return is_square(k, n + 1);
}

With optimization turned on (use the -O2 compiler flag for gcc and clang, or /Ox for msvc), this compiles to a simple loop:

is_square(long long, long long):
        mov     rax, rsi
        imul    rax, rsi
        cmp     rdi, rax
        jle     .L3
.L2:
        add     rsi, 1
        mov     rax, rsi
        imul    rax, rsi
        cmp     rax, rdi
        jl      .L2
.L3:
        cmp     rdi, rax
        sete    al
        ret

Fast solution using cmath library:

#include <cmath>

bool is_square(long long k) {
    long double real_root = sqrt((long double)k); 
    long long integral_root = llround(real_root);
    return integral_root * integral_root == k;
}
answered on Stack Overflow Aug 7, 2019 by J. Antonio Perez • edited Jun 20, 2020 by Community

User contributions licensed under CC BY-SA 3.0