By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,383 Members | 2,070 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,383 IT Pros & Developers. It's quick & easy.

Determine the maximum of two integers.

P: n/a
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?
#include <limits.h>

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)];
}
Thank you for your time
Nov 18 '07 #1
Share this Question
Share on Google+
29 Replies


P: n/a
lovecreatesbea...@gmail.com wrote:
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?
#include <limits.h>

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)];
}
Thank you for your time
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.

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.

By the way, this isn't a C question. Ask in comp.programming next time.
Nov 18 '07 #2

P: n/a
On Sun, 18 Nov 2007 12:33:32 +0000, Mark McIntyre wrote:
lovecreatesbea...@gmail.com wrote:
>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?
#include <limits.h>

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)];
}
Thank you for your time

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,
-0 is positive zero, and when the subtraction generates that, there are
no extra problems.

The subtraction is only allowed to give negative zero when both n1 and n2
are zero, and one or both of them is negative. In this case, the cast to
unsigned gives plain zero, meaning a[0] would be returned, which is a
valid option when n1 == n2. Negative zero is not smaller or larger than
positive zero for C integers, even though other systems may differ.
and it will fail on any other sort of representation, for
example excess-N.
Such a representation is not allowed.

The code may also fail if unsigned int has padding bits, by the way, for
at least two reasons. Firstly, there is no guarantee that
UINT_MAX INT_MAX. Secondly, the behaviour of the right-shift is
undefined.
Nov 18 '07 #3

P: n/a
�Harald van Dijk wrote:
-0 is positive zero, and when the subtraction generates that, there are
no extra problems.
You sure? The bitpattern of -0 is all-ones I think.
>and it will fail on any other sort of representation, for
example excess-N.

Such a representation is not allowed.
By a conforming C compiler.
The code may also fail if unsigned int has padding bits, by the way, for
at least two reasons. Firstly, there is no guarantee that
UINT_MAX INT_MAX. Secondly, the behaviour of the right-shift is
undefined.
I belive UINT_MAX must be at least equal to INT_MAX however?
Nov 18 '07 #4

P: n/a
On Nov 18, 3:07 pm, Mark McIntyre <markmcint...@spamcop.netwrote:
I belive UINT_MAX must be at least equal to INT_MAX however?
UINT_MAX >= INT_MAX >= 32767

x >= y does not guarantee x y.
Nov 18 '07 #5

P: n/a
On Sun, 18 Nov 2007 13:07:55 +0000, Mark McIntyre wrote:
�Harald van Dijk wrote:
>-0 is positive zero, and when the subtraction generates that, there are
no extra problems.

You sure? The bitpattern of -0 is all-ones I think.
The bit pattern of -0 is all zeroes, since -0 is plain old zero. The bit
pattern of ~0 is all ones, and that is allowed to be negative zero. You
can't create negative zero except by bit manipulation; it's simply not
allowed, even if it would make sense for the processor.
>>and it will fail on any other sort of representation, for example
excess-N.

Such a representation is not allowed.

By a conforming C compiler.
Yes.
>The code may also fail if unsigned int has padding bits, by the way,
for at least two reasons. Firstly, there is no guarantee that UINT_MAX
INT_MAX. Secondly, the behaviour of the right-shift is undefined.

I belive UINT_MAX must be at least equal to INT_MAX however?
Correct.
Nov 18 '07 #6

P: n/a
vi******@gmail.com wrote:
On Nov 18, 3:07 pm, Mark McIntyre <markmcint...@spamcop.netwrote:
>I belive UINT_MAX must be at least equal to INT_MAX however?

UINT_MAX >= INT_MAX >= 32767

x >= y does not guarantee x y.
I'm aware of that. Hence the words "at least equal".

Nov 18 '07 #7

P: n/a
�Harald van Dijk wrote:
On Sun, 18 Nov 2007 13:07:55 +0000, Mark McIntyre wrote:
>�Harald van Dijk wrote:
>>-0 is positive zero, and when the subtraction generates that, there are
no extra problems.
You sure? The bitpattern of -0 is all-ones I think.

The bit pattern of -0 is all zeroes, since -0 is plain old zero. The bit
pattern of ~0 is all ones, and that is allowed to be negative zero. You
can't create negative zero except by bit manipulation; it's simply not
allowed, even if it would make sense for the processor.
Euh, I think we're at cross purposes.
-0 is negative zero
+0 is positive zero, plain old zero.

Not a C question however.
FUs set to

http://en.wikipedia.org/wiki/Ones_co....27_complement

:-)
Nov 18 '07 #8

P: n/a
On Sun, 18 Nov 2007 14:42:35 +0000, Mark McIntyre wrote:
�Harald van Dijk wrote:
>On Sun, 18 Nov 2007 13:07:55 +0000, Mark McIntyre wrote:
>>�Harald van Dijk wrote:
-0 is positive zero, and when the subtraction generates that, there
are no extra problems.
You sure? The bitpattern of -0 is all-ones I think.

The bit pattern of -0 is all zeroes, since -0 is plain old zero. The
bit pattern of ~0 is all ones, and that is allowed to be negative zero.
You can't create negative zero except by bit manipulation; it's simply
not allowed, even if it would make sense for the processor.

Euh, I think we're at cross purposes. -0 is negative zero
+0 is positive zero, plain old zero.
In C (which is the topic of this newsgroup), -0 is an expression which
evaluates to positive zero. Always, regardless of the representation of
integers. It was obvious that you meant negative zero, and I did address
the message as if you had said negative zero later on, but -0 is not a
good notation for it here.
Nov 18 '07 #9

P: n/a
Mark McIntyre wrote:
�Harald van Dijk wrote:
>-0 is positive zero, and when the subtraction generates that, there
are no extra problems.

You sure? The bitpattern of -0 is all-ones I think.
You think?

Gosh McIntyre!

-0 is minus zero is zero!

And that is a bit pattern of all ZEROS!

~0 is a bit pattern of all ones!

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
Nov 18 '07 #10

P: n/a
On Sun, 18 Nov 2007 17:55:21 +0100, in comp.lang.c , jacob navia
<ja***@nospam.comwrote:
>Mark McIntyre wrote:
>?Harald van D?k wrote:
>>-0 is positive zero, and when the subtraction generates that, there
are no extra problems.

You sure? The bitpattern of -0 is all-ones I think.

You think?
I certainly did.
>Gosh McIntyre!
Slainte Navia! Is this a weird new form of greeting in your part of
the world?
>-0 is minus zero is zero!
Not in ones-complement. You /do/ realise that ones-complement has two
zeros, don't you?
>And that is a bit pattern of all ZEROS!
Zero is all bits zero. We can agree about that
Minus zero is therefore the complement of that.
ie all-bits-one.
This is the definition of ones-complement.

Of course, its extremely possible that the Maths depts of several
universities are wrong.
>~0 is a bit pattern of all ones!
Possibly.
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan
Nov 18 '07 #11

P: n/a
Mark McIntyre wrote:
>
On Sun, 18 Nov 2007 17:55:21 +0100, in comp.lang.c , jacob navia
<ja***@nospam.comwrote:
Mark McIntyre wrote:
?Harald van D?k wrote:
-0 is positive zero,
and when the subtraction generates that, there
are no extra problems.

You sure? The bitpattern of -0 is all-ones I think.
You think?
I don't see in this thread anywhere
if it has been established
that one's complement representation
is any more relevant than sign and magnitude.
-0 is minus zero is zero!

Not in ones-complement.
It depends on what you mean.

It is unspecified whether a negative zero
becomes a normal zero when stored in an object.

--
pete
Nov 18 '07 #12

P: n/a
Mark McIntyre <ma**********@spamcop.netwrites:
On Sun, 18 Nov 2007 17:55:21 +0100, in comp.lang.c , jacob navia
<ja***@nospam.comwrote:
>>Mark McIntyre wrote:
>>?Harald van D?k wrote:
-0 is positive zero, and when the subtraction generates that, there
are no extra problems.

You sure? The bitpattern of -0 is all-ones I think.

You think?

I certainly did.
>>-0 is minus zero is zero!

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".]

I hope you see that you may be talking at cross-purposes. Both the
notation "-0" and the phrase "minus zero" are ambiguous to the extent
that without a little clarification you could go on arguing forever
over nothing.

The standard uses the term "negative zero". In a C newsgroup it is
reasonable to interpret -0 as a C expression. It is also reasonable
(though ambiguous) to voice that as "minus zero". Thus what Jacob
Navia wrote is not wrong.

--
Ben.
Nov 18 '07 #13

P: n/a
Harald van Dijk wrote:
On Sun, 18 Nov 2007 13:07:55 +0000, Mark McIntyre wrote:
[...]
>You sure? The bitpattern of -0 is all-ones I think.

The bit pattern of -0 is all zeroes, since -0 is plain old zero. The bit
It appears to me, you talk about different things, or I might be rather
confused. As seen by the translator, -0 is unitary zero, which has
little to do with negative zero.

On a 1-complement machine, negative zero would have bit pattern ~0, but
on a sign- and magnitude machine, the MSB is 1, while the rest of the
bits would be 0.

bool is_negative_zero(int d)
{
if (d == 0)
{ /* zero & ~0 */
/* 1-complement -0: 1111...1 & 1111...1 = 1 */
/* 1-complement 0: 0000...0 & 1111...1 = 0 */
/* sign/magnitude -0:1000...0 & 1111...1 = 1000...0 */
/* sign/magnitude 0:0000...0 & 1111...1 = 0 */
if (d & ~0)
return true;
}
return false;
}
pattern of ~0 is all ones, and that is allowed to be negative zero. You
can't create negative zero except by bit manipulation; it's simply not
allowed, even if it would make sense for the processor.
Right, *if* negative zero is supported by the implementation, then a
negative zero can only be created as a result of bitwise op.

--
Tor <bw****@wvtqvm.vw | tr i-za-h a-z>
Nov 18 '07 #14

P: n/a
Mark McIntyre <ma**********@spamcop.netwrites:
On Sun, 18 Nov 2007 17:55:21 +0100, in comp.lang.c , jacob navia
<ja***@nospam.comwrote:
>>Mark McIntyre wrote:
>>?Harald van D?k wrote:
-0 is positive zero, and when the subtraction generates that, there
are no extra problems.

You sure? The bitpattern of -0 is all-ones I think.

You think?

I certainly did.
>>Gosh McIntyre!

Slainte Navia! Is this a weird new form of greeting in your part of
the world?
>>-0 is minus zero is zero!

Not in ones-complement. You /do/ realise that ones-complement has two
zeros, don't you?
Ones complement? I think you are missing the point. "-0" IS "minus zero"
e.g the expression. This optimizes to ... nothing.
>
>>And that is a bit pattern of all ZEROS!

Zero is all bits zero. We can agree about that
Minus zero is therefore the complement of that.
ie all-bits-one.
This is the definition of ones-complement.

Of course, its extremely possible that the Maths depts of several
universities are wrong.
>>~0 is a bit pattern of all ones!

Possibly.
Nov 18 '07 #15

P: n/a
"lovecreatesbea...@gmail.com" wrote:
The following function determines the maximum of two
integers.
Not portably. What is it meant to do that (a < b) doesn't?
It works on my machine.
Which has little to do with the price of eggs. :-)
>
If (a[0] - a[1]) is negative,
Consider INT_MAX - INT_MIN.
what's the first bit of:
(unsigned)(a[0] - a[1])? Is it 0 or 1?

#include <limits.h>

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)];
Tip: If you're using sizeof and CHAR_BIT, then there's a
99.9999% chance you've already got it wrong.
}
http://groups.google.com/group/comp....eee18e55ea156c

--
Peter
Nov 18 '07 #16

P: n/a
lovecreatesbea...@gmail.com wrote:
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?
#include <limits.h>

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)];
}
Thank you for your time
Why so complicated?

#define MAX(A,B) ((A) (B) ? (A) : (B))

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
Nov 18 '07 #17

P: n/a
Peter Nilsson wrote:
>
"lovecreatesbea...@gmail.com" wrote:
The following function determines the maximum of two
integers.

Not portably. What is it meant to do that (a < b) doesn't?
It works on my machine.

Which has little to do with the price of eggs. :-)

If (a[0] - a[1]) is negative,

Consider INT_MAX - INT_MIN.
what's the first bit of:
(unsigned)(a[0] - a[1])? Is it 0 or 1?

#include <limits.h>

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)];

Tip: If you're using sizeof and CHAR_BIT, then there's a
99.9999% chance you've already got it wrong.
It's OK for an itoa buffer.

char itoa_buff[(sizeof(int) * CHAR_BIT - 1) / 3 + 2] = "";
char utoa_buff[(sizeof(int) * CHAR_BIT ) / 3 + 1] = "";

--
pete
Nov 19 '07 #18

P: n/a
Joe Wright wrote:
>
.... snip ...
>
Why so complicated?

#define MAX(A,B) ((A) (B) ? (A) : (B))
...
m = MAX(a++, b--);

fouls. Now what?

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Try the download section.

--
Posted via a free Usenet account from http://www.teranews.com

Nov 19 '07 #19

P: n/a
CBFalconer wrote:
Joe Wright wrote:
... snip ...
>Why so complicated?

#define MAX(A,B) ((A) (B) ? (A) : (B))

...
m = MAX(a++, b--);

fouls. Now what?
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--?

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Looking for software development work in the San Diego area.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Nov 19 '07 #20

P: n/a
In article <87************@bsb.me.ukBen Bacarisse <be********@bsb.me.ukwrites:
Mark McIntyre <ma**********@spamcop.netwrites:
....
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.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Nov 19 '07 #21

P: n/a
Keith Thompson wrote:
CBFalconer wrote:
>Joe Wright wrote:
... snip ...
>>Why so complicated?

#define MAX(A,B) ((A) (B) ? (A) : (B))

...
m = MAX(a++, b--);

fouls. Now what?

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);

--
Eric Sosman
es*****@ieee-dot-org.invalid
Nov 19 '07 #22

P: n/a
�Harald van Dijk wrote:
On Sun, 18 Nov 2007 14:42:35 +0000, Mark McIntyre wrote:
>�Harald van Dijk wrote:
>>On Sun, 18 Nov 2007 13:07:55 +0000, Mark McIntyre wrote:
�Harald van Dijk wrote:
-0 is positive zero, and when the subtraction generates that, there
are no extra problems.
You sure? The bitpattern of -0 is all-ones I think.
The bit pattern of -0 is all zeroes, since -0 is plain old zero. The
bit pattern of ~0 is all ones, and that is allowed to be negative zero.
You can't create negative zero except by bit manipulation; it's simply
not allowed, even if it would make sense for the processor.
Euh, I think we're at cross purposes. -0 is negative zero
+0 is positive zero, plain old zero.

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.
Nov 20 '07 #23

P: n/a
Ben Bacarisse wrote:
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.
Nov 20 '07 #24

P: n/a
Mark McIntyre <ma**********@spamcop.netwrites:
Ben Bacarisse wrote:
>I hope you see that you may be talking at cross-purposes.

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.
>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.
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".

--
Ben.
Nov 20 '07 #25

P: n/a
Ben Bacarisse wrote:
Mark McIntyre <ma**********@spamcop.netwrites:
>Ben Bacarisse wrote:
>>I hope you see that you may be talking at cross-purposes.
Yes,

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.
>>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.

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.
Nov 20 '07 #26

P: n/a
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.

Nov 20 '07 #27

P: n/a
On Sun, 18 Nov 2007 12:33:32 +0000, Mark McIntyre
<ma**********@spamcop.netwrote:
lovecreatesbea...@gmail.com wrote:
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=clintonIt 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
Dec 2 '07 #28

P: n/a
In article <oa********************************@4ax.com>,
David Thompson <da************@verizon.netwrote:
[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

Dec 3 '07 #29

P: n/a
On Sun, 2 Dec 2007 23:50:32 +0000 (UTC),
dj******@csclub.uwaterloo.ca.invalid wrote:
In article <oa********************************@4ax.com>,
David Thompson <da************@verizon.netwrote:
[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
Dec 24 '07 #30

This discussion thread is closed

Replies have been disabled for this discussion.