Determine the maximum of two integers.

[Dik T. Winter]

> > Not in ones-complement. You /do/ realise that ones-complement has two
> > zeros, don't you?

>
> [Nit: *may* have two zeros. As far as C is concerned, the "other zero"
> may be trap representation which is not "negative zero".]

Indeed. There are (or perhaps have been) machines where it *was* a
trap representation.

 

[Eric Sosman]

Now you know better than to invoke a macro with arguments that have side
effects. (Fortunately, the name is all-caps, which is a strong hint.)

How often would you really want to compute the maximum of a++ and b--?

x = MAX(x, get_next_x());

random_variate_distributed_as_x_squared
= MAX(rand(), rand()) / (RAND_MAX + 1.0);

 

[Mark McIntyre]

In C (which is the topic of this newsgroup), -0 is an expression which
evaluates to positive zero.

I disagree that the context is even slightly unclear, since I was
expressly discussing ones-complement representations, but its not worth
worrying about.

 

[Mark McIntyre]

I hope you see that you may be talking at cross-purposes.

Yes, but the crossing was not mine. I was expressly referring to ones
complement where the OP's idea could fail. I had separately addressed
twos complement where the OP's idea worked, and went on to mention
sign-magnitude, in which the OP's solution would also fail.

In a C newsgroup it is
reasonable to interpret -0 as a C expression.

Only without context. In the context of ones complement, the argument
falls, unless one is being pathological.

 

[Ben Bacarisse]

Yes,

Then it seems odd to keep the discussion going. When I see cross
purpose discussion I want to clear up the confusion.

but the crossing was not mine. I was expressly referring to ones
complement where the OP's idea could fail. I had separately addressed
twos complement where the OP's idea worked, and went on to mention
sign-magnitude, in which the OP's solution would also fail.


Only without context. In the context of ones complement, the argument
falls, unless one is being pathological.

I would say it is pathological, in comp.lang.c, to ignore the
possibility that Jacob meant -0 to be a C expression. The only
unambiguous way to talk about negative zero is to use the term
"negative zero".

 

[Mark McIntyre]

Then it seems odd to keep the discussion going. When I see cross
purpose discussion I want to clear up the confusion.

I didn't see any, until someone else jumped in.

>

I would say it is pathological, in comp.lang.c, to ignore the
possibility that Jacob meant -0 to be a C expression.

I disagree. Given context, the meaning was definitely clear.

My strong belief is that JN saw a posting by me, saw what he assumed was
a trivial error, leapt at the chance to mock my post, and in his
excitement did not bother to check the context or his facts.

The only
unambiguous way to talk about negative zero is to use the term
"negative zero".

-0 /is/ negative zero. I can't concieve of any other meaning for it. It
even /reads/ as negative zero. If I didn't want the negative symbol
there, I'd have left it out.

 

[jameskuyper]

Mark McIntyre wrote:
....

-0 /is/ negative zero. I can't concieve of any other meaning for it. It
even /reads/ as negative zero. If I didn't want the negative symbol
there, I'd have left it out.

Nontheless, it does have at least one other meaning. In a C context,
it is the unary minus operator acting on an integer literal with a
value of 0 and a type of 'int', giving a value of positive zero, not
negative zero. There are lots of people who've never heard of negative
zero, who would correctly conclude, from an incorrect argument, that
this was an odd way of expressing the same value as 0. Many of those
who have heard of negative zeros would incorrectly expect the
expression -0 to evaluate to negative zero in a C context. However,
the correct C interpretation of that expression is well known to many
of us who post on this newsgroup, and at least some of us routinely
expect that most things that they see on this newsgroup that could be
interpreted as C expressions are intended to be so interpreted. If
you're going to use -0 to represent negative zero, I strongly
recommend using wording that clarifies the fact that you're not
talking about the C expression -0.

 

[David Thompson]

The following function determines the maximum of two integers. It
works on my machine.

If (a[0] - a[1]) is negative, what's the first bit of: (unsigned)(a[0]
- a[1])? Is it 0 or 1?

<G mode=clinton> It depends partly on what "is" means. </>

If you mean the C expression a[0] - a[1] where both are type 'int',
that is negative IF a[0] < a[1] AND the subtraction doesn't overflow,
or equivalently the difference is within the range of 'int'. If the C
subtraction is negative, then the high bit of the conversion (by cast)
to 'unsigned' is reliably 1 IF 'unsigned int' has at least one more
magnitude bit than '(signed) int'; this is very common, but is not
required by the standard. Overflow (of a signed type) is Undefined
Behavior in the standard and formally anything can happen, the
canonical example of which in this newsgroup is that it may cause
demons to fly out your nose; in practice on most real implementations
you'll just get the wrong answer -- which is bad enough.

If you mean the mathematical integer a[0] - a[1], that is negative if
and only if a[0] < a[1]. But your C code does not reliably compute it,
and in general neither does any C program, since mathematical integers
are unbounded (loosely, infinite) and any C implementation must be
finite -- and even if it wasn't required to be, or in some other
language that formally isn't, any actual implementation still is.

int max(int n1, int n2)
{
int a[2];
a[0] = n1, a[1] = n2;
return a[((unsigned)(a[0] - a[1]) >> sizeof n1 * CHAR_BIT - 1)];

Absolutely nothing is accomplished by copying into a[0,1] and then
using those, and IM(subjective)O it _reduces_ clarity.

The representation of 'unsigned' is allowed to include padding bits,
in which case the shift amount you compute is too high -- and the
result again is undefined behavior, which in practice is likely wrong.

This will work for twos complement and sign-magnitude machines. I doubt
you'll ever encounter any other sort.

It will fail on ones complement machines where the subtraction gave the
value -0, and it will fail on any other sort of representation, for
example excess-N.

No, it will work in C for all allowed integer representations, as long
as the bit-width of unsigned is sufficient as described above. 1sC and
S&M representations can have negative-zero, but the conversion to
unsigned is done based on its _value_ which is still zero, not its
representation. Type-punning through a pointer or union or cheating on
non-prototyped argument type might have problems with non-2sC.

However its a very complicated way to compare two ints. If I found it
during code review, I'd force my developer to remove it.

Overly complicated AND unreliable.

By the way, this isn't a C question. Ask in comp.programming next time.

Well, parts of it are. Besides, it's kind of fun. <G>

- formerly david.thompson1 || achar(64) || worldnet.att.net

 

[dj3vande]

[A]ny C implementation must be
finite -- and even if it wasn't required to be, or in some other
language that formally isn't, any actual implementation still is.

Hmm...

Let's see. void * is required to be a fixed finite size, and to be
able to contain a pointer to any non-register-qualified object without
losing important information. This puts an upper bound on the number
of non-register-qualified objects that a program can use; this bound
depends on the implementation but exists for all implementations.

Similarly, (size_t)-1 is finite and puts a finite upper bound on the
size of any given object a programmer can use. So we have a finite
upper bound of (distinct values of void *)*((size_t)-1)*CHAR_BIT bits
worth of data stored in non-register-qualified objects in a given
program.

For any given implementation, this is obviously not enough to store any
arbitrary member of the (unbounded) set of mathematical integers.

The only loophole I can see in that is that an implementation can
create an unbounded number of register-qualified objects if it can find
somewhere to put them, but the only way to make that number grow
unboundedly is by unbounded recursion (for fixed-depth recursion the
limit is a finite multiple of the (finite) number that are created in
any given scope), and I don't see any way to access a register-
qualified object outside the lexical scope it's defined in, which
doesn't make them all that useful for getting around finiteness-of-size
constraints.

Another possibility: An implementation is not forbidden to have
magical filename arguments for fopen that will allow an unbounded data
queue, so if those existed truly unbounded bignums (and other truly
unbounded data types) could be built around them.

Anything else I'm missing?


dave

 

[David Thompson]

On Sun, 2 Dec 2007 23:50:32 +0000 (UTC),

[A]ny C implementation must be
finite -- and even if it wasn't required to be, or in some other
language that formally isn't, any actual implementation still is.

Hmm...

Let's see. void * is required to be a fixed finite size, and to be
able to contain a pointer to any non-register-qualified object <snip>
Similarly, (size_t)-1 is finite and puts a finite upper bound on the
size of any given object a programmer can use. So we have a finite
upper bound of (distinct values of void *)*((size_t)-1)*CHAR_BIT bits
worth of data stored in non-register-qualified objects in a given
program.

Worse; every byte of every nonregister object representation must be
uniquely addressable by char * and hence void *. So valuesof(void*)
bytes, which is bounded by sizeof(void*)*CHAR_BIT -1/*for nullptr*/.

For any given implementation, this is obviously not enough to store any
arbitrary member of the (unbounded) set of mathematical integers.

The only loophole I can see in that is that an implementation can
create an unbounded number of register-qualified objects if it can find
somewhere to put them, but the only way to make that number grow
unboundedly is by unbounded recursion [but they can't be shared].
Concur.

Another possibility: An implementation is not forbidden to have
magical filename arguments for fopen that will allow an unbounded data
queue, so if those existed truly unbounded bignums (and other truly
unbounded data types) could be built around them.

Actually I forgot about I/O, which was silly considering that a Turing
Machine is (nominally) ALL I/O. Of course ftell/fseek and f[gs]etpos
can only work for a bounded* range, so positioning within such a file
or files will be at least a real pain; the only way obvious to me is a
loop around fread or fwrite in the program, which requires unbounded
state in memory, reducing to the case previously proven above.

And the (obvious) bignum representations and operations I know of
require in general at least bidirectional and sometimes random/direct
positioning to digits. However, there might be other representations
which avoid this; I don't know enough number theory to even know where
to look, although there spring to mind some widely used examples like
frequency-domain audio/video (FFT/etc. and wavelets) and
Chinese-remainder for RSA crypto calculation.

_Maybe_ we can do the positioning in (general) unbounded file A
controlled by a littleendian unbounded integer in unbounded file auxA.
But I wouldn't like to debug it, or even QA it. And it still requires
unbounded cycles to run, and AIUI physics still has a finite limit on
cycles/second -- and also on cycles/energy and I _believe_
energy/universe is still finite (though physics gets pretty weird).

(* As we have known for decades and recently been again reminded,
ftell/fseek is so strongly bounded as to even be a PRACTICAL problem.)

- formerly david.thompson1 || achar(64) || worldnet.att.net