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

Question

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?

"Sometimes"? Consistently? For what input? We like [minimal complete examples](https://stackoverflow.com/help/mcve) here. — Beta, Aug 07 '19 at 16:17
You're relying on exact equality of floating-point numbers. That's a bad idea and often goes wrong. When it goes wrong, you probably get a ... stack overflow — Useless, Aug 07 '19 at 16:17
@Useless: long double has a very big precision: it can't be an overflow. — Matteo, Aug 07 '19 at 16:22
And: stack overflow is not floating-point overflow. It means your recursion doesn't terminate in a reasonable number of levels. — Useless, Aug 07 '19 at 16:26
1/ Don't use floating point. Or 2/ decide on the level of precision you really need, choose an appropriate value for `epsilon`, and use the expression I already showed you. Oh, and it might be worth reading [this](https://stackoverflow.com/q/588004/212858) other question for background. — Useless, Aug 07 '19 at 16:29
Handy reading: [Is floating point math broken?](https://stackoverflow.com/questions/588004/is-floating-point-math-broken) and [What Every Computer Scientist Should Know About Floating-Point Arithmetic](https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html) — user4581301, Aug 07 '19 at 17:02
Recommended reading: [What Every Computer Scientist Should Know About Floating-Point Arithmetic](https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html) , [Is floating point math broken?](https://stackoverflow.com/q/588004/5910058) , [Sometimes Floating Point Math is Perfect](https://randomascii.wordpress.com/2017/06/19/sometimes-floating-point-math-is-perfect/) . Please read and comprehend all 3, then try again. — Jesper Juhl, Aug 07 '19 at 17:36

score 1 · Answer 1 · edited Aug 07 '19 at 16:55

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.

edited Aug 07 '19 at 16:55

Alecto Irene Perez

10,321
23
46

answered Aug 07 '19 at 16:24

lenik

23,228
4
34
43

Error: 'root' was not declared in this scope – Matteo Aug 07 '19 at 16:26
Error: expected ',' or ';' before 'return' – Matteo Aug 07 '19 at 16:29
sorry for syntax, i'm writing python code most of the time – lenik Aug 07 '19 at 16:32

score 1 · Answer 2 · edited Jun 20 '20 at 09:12

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

It compiles to a loop, and the asker seemed to want to do things recursively — Alecto Irene Perez, Aug 07 '19 at 17:04

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

2 Answers2

Fast solution using cmath library:

Fast solution using `cmath` library: