Problem regarding recursive method

Question

For a code of mine, I need to test if a number is a perfect square at compilation time, so I wrote the following method:
https://code.sololearn.com/c68lM7510DMh/?ref=app

The idea is that every perfect square number can be written as a sum of odd numbers from 1 to N.
However, I can't really get it to work, wondering what I am missing (something stupid, as usual, I suppose) and how I can get it working? I would appreciate if someone looked into this.

Answer 1

For isSquare( 10, 1 ) num goes below 0
num > 0 is always true except for when num == 0 because num is an unsigned, it wraps back around to 2^64 - 1 and has to go down to 0 again, probably many times.
This takes a bit too long, therefore the timeout.
You can fix this by changing the type to signed.

num for isSquare( 4, 1 ) and isSquare( 9, 1 ) both reach 0, therefore the result should be true, right?
But since we still have to retrace our steps due to the recursion the value is being negated several times.

isSquare( 4, 1 ) is recalled 3 times. So you return !!!num ( false becomes true )
isSquare( 9, 1 ) is recalled 4 times. So you return !!!!num ( false stays false )

I fixed it by removing the !( ... ) and returning num == 0 ( or !num ) when num > 0 is false.

Lastly I think giving i a default value makes the function a bit easier to call.

So the fixed function would be like this:

constexpr bool isSquare( long long num, long long i = 1 )
{
return num > 0 ? isSquare( num - i, i + 2 ) : !num;
}

Answer 2

I love how a solved discussion is featured on the home page...glad it was solved though :) Good luck with the code Naitomea !

Answer 3

Ah, I see. I didn't even think about that multiple negates could stay there, but it makes sense now that you pointed it out.
Plus I'm somewhat smiling about the "a bit too long". 😊

Thanks for your help again, now I'll be able to finish my code!

Answer 4

I really like such compile time solutions, it is a wonderful C++ feature. Thx for this inspiring input.

BUT, how can one check whether the execution is done at complie time, not at runtime? constexpr seems not to make this guarantee.

Answer 5

K Locher I would go about it like I did in the finished version:

https://code.sololearn.com/c6wLiTHv6RT1/?ref=app

Using <chrono> (link below) to take the time.
It works better in an actual IDE though, SL still has the time limit, in an IDE you can test for way higher ranges.
Alternately, you could use the <ctime> header, or what Dennis suggested.

http://www.cplusplus.com/reference/chrono/

Answer 6

@K Locher
One way you can check this is by using static_assert

For example, say we have a function isBigger, it's definition being:

constexpr bool isBigger( int a, int b )
{
return a > b;
}

And then use:
static_assert( isBigger( 7, 6 ), "" ) to check if it's really constexpr

If the code compiles( which it does ), the function is constexpr.

----

static_assert( isBigger( 5, 6 ), "" )
If the code throws an error saying static assertion failed, the function is constexpr.

----

int a = 5;
static_assert( isBigger( a, 6 ) , " " );
If the code says something along the lines of non-constant condition used, the function is not constexpr.

Answer 7

Thanks Zeke Williams, I already finished it, it was just a small Euler exercise where all what was missing was this function.

sword Of The God It is kind of a mix of math and programming related task. You can view it here: https://projecteuler.net/problem=171
There are a lot more exercises like this on the website.

Answer 8

sword Of The God The exercise is in the link I put up above, my finished solution is visible in my profile.

Answer 9

@Dennis
Great! Thanks for this detailed explanation.

Answer 10

is it a math exercice?

Answer 11

Naitomea thanks ,give this euler exercice please

Answer 12

Wow! What a great use of recursion 👌

I made a code myself inspired by yours. I thought that this will reduce the run-time by half, which is useful for very large numbers.

https://code.sololearn.com/W25k0m2WJN09/?ref=app

Answer 13

how to run this codes?...

Answer 14

can someone say me what is the difference between friendly and default specifier in c++?? ND which should more preferably used in terms of privacy??

Answer 15

hi I need porgram to have 400 line cod inC++ how con send me tnxx

Answer 16

4444

Answer 17

class root {
public satic void main(string[] arguments ) {
int number =225
system.out.println ("the square root of + number
+ " is "
+ math.sqrt (number) ) ;
}
}