+ 36

# Problem regarding recursive method

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.

4th Jul 2018, 7:10 PM
+ 36
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; }
4th Jul 2018, 8:53 PM
Dennis
+ 10
I love how a solved discussion is featured on the home page...glad it was solved though :) Good luck with the code Naitomea !
6th Jul 2018, 4:49 PM
Zeke Williams
+ 9
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!
4th Jul 2018, 9:18 PM
+ 6
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.
6th Jul 2018, 8:20 PM
K Locher
+ 6
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/
6th Jul 2018, 8:28 PM
+ 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.
6th Jul 2018, 8:32 PM
Dennis
+ 5
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.
6th Jul 2018, 6:31 PM
+ 5
sword Of The God The exercise is in the link I put up above, my finished solution is visible in my profile.
6th Jul 2018, 6:36 PM
+ 5
@Dennis Great! Thanks for this detailed explanation.
6th Jul 2018, 8:40 PM
K Locher
+ 4
is it a math exercice?
6th Jul 2018, 6:07 PM
Numpy
+ 4
Naitomea thanks ,give this euler exercice please
6th Jul 2018, 6:33 PM
Numpy
+ 2
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
7th Jul 2018, 2:27 PM
777
+ 1
how to run this codes?...
7th Jul 2018, 8:01 AM
Shoaib Robot
+ 1
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??
8th Jul 2018, 11:57 AM
Bisnu😎
- 2
hi I need porgram to have 400 line cod inC++ how con send me tnxx
8th Jul 2018, 1:40 PM
Àšád ŸöśÛfi
- 4
4444
7th Jul 2018, 1:02 AM
Nguyễn Ty
- 8
class root { public satic void main(string[] arguments ) { int number =225 system.out.println ("the square root of + number + " is " + math.sqrt (number) ) ; } }
6th Jul 2018, 11:07 PM
Happiness Okeke