Bizzarre problem - Int vs. uint.

[IceDane]

The following program finds magic squares(Eg, numbers that are perfect squares as well as the sum of all numbers from 1 to n)

#include <stdio.h>

int iscis(unsigned int x)
{
     unsigned int i = 1;
     
     for(;;)
     {
          if(x == 0) return 1;
          if(x - i < 0) return 0;
          
          x -= i;
          
          i++;
     }
}


int main(void)
{
     unsigned int i = 1;
     int counter = 0;
     
     while(counter < 100)
     {
         if(iscis(i*i)) { counter++; printf("%u is a magic square.\n", i*i); i++; }
         else i++;
     
     }
     return 0;
}

If I change the type to int, it works as intended. However, it reaches integer overflow pretty fast, so I decided to extend it to 32bits with unsigned ints. When I do that, the program becomes extremely slow, and the algorithm returns 0 for every number I pass to it.

Output with ints:

1 is a magic square.
36 is a magic square.
1225 is a magic square.
41616 is a magic square.
1413721 is a magic square.
48024900 is a magic square.
1631432881 is a magic square.
0 is a magic square. <-- this is like 5 seconds in..
136331328 is a magic square.
245366628 is a magic square.
572048400 is a magic square.
779315460 is a magic square.
1348648080 is a magic square.
1702915620 is a magic square.
0 is a magic square.
621827745 is a magic square.

Output with unsigned ints:

1 is a magic square.
4 is a magic square.
9 is a magic square.
16 is a magic square.
25 is a magic square.
36 is a magic square.
49 is a magic square.
64 is a magic square.
81 is a magic square.
100 is a magic square.
121 is a magic square.
144 is a magic square.
169 is a magic square.
196 is a magic square.
225 is a magic square.
256 is a magic square.
289 is a magic square.
324 is a magic square.

As is obvious, it's a slowdown by a factor in the thousands..


Any help will be greatly appreciated.

[cas]

If x and i are unsigned, then x - i will never be negative. Thus when you have:

if(x - i < 0) return 0;

it won't return zero, ever. Since you are really checking whether i is greater than x, you can use:

if(x < i) return 0;

Unsigned integers wrap on over/underflow (signed over/underflow is undefined, but will probably wrap on your implementation). That means that when, say, 4 is passed to iscis(), the following will happen:
4 is not zero, so subtract 1 from x (now 3)
3 is not zero, so subtract 2 from x (now 1)
1 is not zero, so subtract 3 from x (now UINT_MAX - 2)

and so on.

If you're using gcc, the -Wextra flag will catch your unsigned comparison to zero bug. Unfortunately, -Wextra will also "catch" some other, perfectly valid code. Whether it's worth using is up to you.

[IceDane]

If x and i are unsigned, then x - i will never be negative. Thus when you have:

if(x - i < 0) return 0;

it won't return zero, ever. Since you are really checking whether i is greater than x, you can use:

if(x < i) return 0;

Unsigned integers wrap on over/underflow (signed over/underflow is undefined, but will probably wrap on your implementation). That means that when, say, 4 is passed to iscis(), the following will happen:
4 is not zero, so subtract 1 from x (now 3)
3 is not zero, so subtract 2 from x (now 1)
1 is not zero, so subtract 3 from x (now UINT_MAX - 2)

and so on.

If you're using gcc, the -Wextra flag will catch your unsigned comparison to zero bug. Unfortunately, -Wextra will also "catch" some other, perfectly valid code. Whether it's worth using is up to you.

Ah, of course. I should have though of that.

Thanks a bunch.