Perfect square or not?

Question

This is a code to check if a number is perfect square or not. Why does it work ?

static bool IsSquare(int n)
{
    int i = 1;
    for (; ; )
    {
        if (n < 0)
            return false;
        if (n == 0)
            return true;
        n -= i;
        i += 2;
    }
}

Remington

Answer 1

Because all perfect squares are sums of consecutive odd numbers:

• 1 = 1
• 4 = 1 + 3
• 9 = 1 + 3 + 5
• 16 = 1 + 3 + 5 + 7

and so on. Your program attempts to subtract consecutive odd numbers from n, and see if it drops to zero or goes negative.

You can make an informal proof of this by drawing squares with sides of {1,2,3,4,...} and observe that constructing a square k+1 from square k requires adding 2k+1 unit squares.

Candicandia

Thanks :) I never knew about this. – Remington

@dasblinkenlight - I just saw that.. did it! – Remington

@dasblinkenlight - and yes we can easily prove it by drawing squares.. here is a video explaining it youtube.com/watch?v=2gC5eVRatOQ – Remington

@user1386320: of course you can learn this at school. School programs are different per country and adapted differently by teachers, so it may be bad luck. – Lewert