size and range of int in c

[Dik T. Winter]

> But you could test it for a few numbers within a certain limit of float
> and declare it works in that range. If you suggest to me there might be
> a subtle bug only on 2.339058309583905890 then we might as well give
> up....

Well, you know, actually such things *do* happen. You will probably know
about Intels floating poit bug which was just such kind of bug. I know
of a bug in Cray hardware multiplication where for some pairs of non-zero
input numbers the half-precision product would be zero. Partial testing
does not prove it works also with the non-tested inputs.

 

[Eric Sosman]

Well, you know, actually such things *do* happen. You will probably know
about Intels floating poit bug which was just such kind of bug. I know
of a bug in Cray hardware multiplication where for some pairs of non-zero
input numbers the half-precision product would be zero. Partial testing
does not prove it works also with the non-tested inputs.

Many years ago I ran across just such a problem with the
software floating-point simulator on a machine: I found a
pair of numbers whose as-computed product was three times
what it should have been. Change any bit in the sign or
fraction part of either number (the bug was exponent-blind),
and the product came out correctly.

(Disclaimer: I didn't spot the bug all by myself. A very
sharp-eyed quality assurance person first noticed that the
rate of descent of one of my simulated aircraft went 4, 8, 36,
16, 20, 72, 28, ... feet per second. He reported the original
bug against my code; I tracked it back to the F-P simulator.)

So as Dik says: Actually, such things *do* happen.

 

[Nick]

I know this Dijkstra quote get trotted out a lot, but is it actually
true? Computers don't actually deal in infinite sets. So in principle
I can enumerate all cases. This may be practically impossible for
large or complex programs but it can be done in some cases. Therefore
the "never" above (which isn't in Dijkstra's quote) is not true.

You would still have to prove that you had enumerated over the entire set
of "inputs".

E.g. for a Unix program, there's no way that you could enumerate over the
entire set of possible combinations for argv[] and environ[] and kernel
state and hardware state and ..., so you would need to demonstrate that
the variables over which you had enumerated represented the entire set of
factors which could affect the program's behaviour.

For a C function e.g. "int foo(int x)", you could enumerate over the range
of "int" (provided that it's no larger than 32 bits; won't work on ILP64),
but you would still need to demonstrate that the function doesn't depend
upon global variables.

Or contained any static variables.

 

[Keith Thompson]

Or contained any static variables.

Or depend on any static variables declared outside the function but in
the same translation unit. Or depend on any static variables declared
in other functions or in other translation units that it might access
indirectly. Or depend on any other state that might persist from one
call to another, such as external files, random numbers, or the phase
of the moon.

 

[Nick]

Or depend on any static variables declared outside the function but in
the same translation unit.

I tend to think of those as "global" variables - they are global to all
functions in the translation unit. They're not properly global, of
course.

Or depend on any static variables declared
in other functions or in other translation units that it might access
indirectly. Or depend on any other state that might persist from one
call to another, such as external files, random numbers, or the phase
of the moon.

Or any sort of undefined behaviour (depending on hidden state) that is
only triggered by a particular combination of inputs.

Consider a function that opens, then closes /twice/ a file if passed a
value of 912.

On the machine I was using a few years ago (and it might be true on this
one), this would crash iff called with 912 twice. Call it with one 912
in among any other inputs and you'd be fine.

Totally undefined of course - but that's most certainly a bug.

I'm sure you can do something equally horrible with the might mix of
mallocs and frees on many implementations (indeed, I strongly suspect my
painful experience with fopen was due to malloc/free calls in the
background).

 

[Nick Keighley]

Yes. And lightning strikes twice. Meanwhile in the real world we test
certain fringe conditions, guards to prevent them being extended and
some reasonable middle of the road ones.

yes, but that puts Dijkstra's quote firmly back in place. Such testing
cannot prove the absence of bugs.

If there are HW issues then you can give up straight away.

but it's such /fun/ debugging software on broken hardware!


--
After a couple of projects that I've done in scheme, after many years
of
C (and assembler), I've come to the conclusion that even *starting* a
program in C is an exercise in premature optimization.
(Andrew Reilly comp.lang.scheme)

 

[Dik T. Winter]

>
> Yes. And lightning strikes twice. Meanwhile in the real world we test
> certain fringe conditions, guards to prevent them being extended and
> some reasonable middle of the road ones.

Yeah. Only you do not know without extensive study of the program what the
fringe conditions are. Both the BSD versions of Adventure and Zork had a
bug due to an incorrect bit in a table entry, and in Adventure it could be
fatal.

> If there are HW issues then you can give up straight away.

Yes, you have to work around it. The bug in the Cray instruction I found
with a program that tested large numbers for primality and consistently told
all Mersenne numbers were prime where the program concluded later that it
was saying that due to a bug in the program. Now when I first encountered
that message how am I supposed to believe all thousands previous announcements
of the program?

 

[stan]

Yes things do happen.

But the point is you can prove your function works for a certain range
of discrete inputs.

Actually that proves the function gives the outputs you got for the
inputs you gave in the state you tested. You can't draw any rational
conclusions about other inputs. You might have a warm and fuzzy
feeling, but that's still speculative thinking; not a proof. Proof is
a really strong word with a well defined meaning. Testing can't
eliminate the possibility you have undefined behavior that gives
changing outputs under changing states either. It's possible one or
more of the values you provided as input will fail later. Sooner or
later everyone chases an intermittent bug.

 

[Richard Bos]

Yeah. Only you do not know without extensive study of the program what the
fringe conditions are. Both the BSD versions of Adventure and Zork had a
bug due to an incorrect bit in a table entry, and in Adventure it could be
fatal.

Did they? Now I'm curious. Particularly if it was the _same_ bug, which
(those programs being from rather different provenance) Shouldn't
Happen. Do tell.

Richard

 

[Dik T. Winter]

>
> Did they? Now I'm curious. Particularly if it was the _same_ bug, which
> (those programs being from rather different provenance) Shouldn't

No they were not the same.

> Happen. Do tell.

In BSD Adventure go down the volcano and go in a direction that is not
mentioned in the description.
In BSD Zork try opening some of the things that inherently cannot be
opened.

 

[Richard Tobin]

In BSD Adventure go down the volcano and go in a direction that is not
mentioned in the description.
In BSD Zork try opening some of the things that inherently cannot be
opened.

And BSD Rogue had a bug (the "weird trap bug") due to incorrect setting
of a bit field.

-- Richard