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

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.

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:
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;
}

User contributions licensed under CC BY-SA 3.0