Terminating a C loop when maximum hardware limit reached

Question

In response to the SO question C: f>0 vs Perl: $f>0?, the use of overflow to terminate the loop is referred to as "poor programming practice". Paraphrased:

Your c code is actually exiting because of poor programming practice. You're relying on fib being a long long int, which has an upper limit of 9.22337204 × 10^18. When you loop around to the 93rd iteration fib becomes 1.22001604 × 10^19, which overflows and becomes negative.

Substantially the same code:

cat >fib.c <<EOF
#include <stdio.h>
int main(){
   for (long long int temp, i=1, prev=0, fib=1; fib>0 ; i++, temp=fib, fib+=prev, prev=temp)
      printf("%lli: %lli\n", i, fib); 
   }
EOF
gcc -std=c99 -ofib fib.c
./fib

The code was intended to be a one time "throw-away" program which was evidenced by the use of single letter variable names in the original version. The use of the overflow being indicated by fib becoming negate was used to terminate the loop.

Without knowing in advance what the maximum number of iterations the hardware architecture could handle what would be good "programming practice" to terminate the loop knowing that long long int is limited yet desiring as many values as possible?

Answer 1

Use unsigned rather than signed because once there is overflow the effect is undefined. Whereas with unsigned there is no overflow but modulo arithmetic plus it produces an additional value.

cat >fib2.c <<EOF
// Fibinocci numbers
#include <stdio.h>
int main(){
   for (unsigned long long ii=1, fib=1, prev=0, temp;
         fib>=prev;  // Wrap indicates max value per implementation
         ii++, temp=fib, fib+=prev, prev=temp)
      printf("%llu: %llu\n", ii, fib);
   }
EOF
gcc -std=c99 -ofib2 fib2.c
./fib2

Answer 2

Good programming practice is knowing that your loop is going to exit. In your case, the exit condition is fib <= 0. Thinking about the algorithm, is fib ever going to be non-positive?

You want to exit after some sort of condition. For sequences like this you usually terminate the loop after either a fixed number of iterations (i.e. "generate the first 50 Fibonacci numbers") or when your values get big enough (i.e. "generate all Fibonacci numbers smaller than 50000").

If you really do want to generate an infinite number of values in an infinite sequence, you need to take your variable types into consideration. Obviously you wouldn't use a boolean value, because its range is tiny. Similarly, even long long int isn't enough because it's finitely bounded. If you want to go beyond the range of your variable types, you need to come up with custom variables or find a library that provides that functionality. For C, you would probably use GMP.

In this case, your loop only exits because of inherent software limitations. It does not give the same results on different platforms, nor would it give the same results for different implementations with different languages (as you saw when you tried to code the same thing in Perl). This would be considered a poor programming practice, as the results are fairly non-deterministic and lead to confusion.