Contest: C BIGNUM BAKEOFF
David Moews
----- -- -----
The object of the BIGNUM BAKEOFF is to write a C program of 512 characters
or less (excluding whitespace) that returns as large a number as possible
from main(), assuming C to have integral types that can hold arbitrarily
large integers. E-mail entries to dmo...@xraysgi.ims.uconn.edu by Dec 31.
Sample entry
------ -----
To: dmo...@xraysgi.ims.uconn.edu
From: jo...@doe.com
Subject: BIGNUM BAKEOFF entry
Here is my program:
----------------------------------
int ipow(int a, int b)
{ return b ? a*ipow(a,b-1) : 1; }
int ipowstack(int a, int b)
{ return b ? ipow(a,ipowstack(a,b-1)) : 1; }
int main(void)
{ return ipowstack(999,999); }
----------------------------------
It returns a number equal to an exponential tower of 999s, 999 numbers high.
Rules in detail
----- -- ------
1. Programs are to be written in C90, i.e., the 1990 C standard,
ANSI/ISO 9899-1990, subject to the following constraints:
(a) No use of floating constants, float, double, long double, or other
floating types.
(b) No use of implementation-defined, locale-specific, or undefined
behavior, except for behavior defined in 7. below.
(d) No use of character constants or string literals.
(e) No use of bit-fields.
(f) No looking at argc, argv, or the environment.
Programs should be deterministic and self-contained.
(g) No use of / or % where the right-hand operand---call it b---
satisfies ((int)b) < 0.
(h) No use of the standard library, except for size_t, ptrdiff_t,
NULL, offsetof(), jmp_buf, setjmp(), longjmp(), div_t, ldiv_t,
calloc(), free(), malloc(), realloc(), bsearch(), qsort(),
abs(), div(), labs(), ldiv(), memcpy(), memmove(), strcpy(),
strncpy(), strcat(), strncat(), memcmp(), strcmp(), strncmp(),
memchr(), strchr(), strcspn(), strpbrk(), strrchr(), strspn(),
strstr(), strtok(), memset(), and strlen().
2. Programs must be 512 characters or less, not counting whitespace
characters. Whitespace characters are space, tab, newline, formfeed,
and return.
3. The number output by the program is the number returned from main().
If your program cannot be proved to return from main(), it will not win.
4. The program which returns the number with largest absolute value from
main() will win. If there is a set of programs for which it cannot
be determined which program in the set returns the biggest number,
all programs in the set will win jointly.
5. Entrants can submit as much explanatory text as they wish in order to
prove their program returns from main(), explain how big the number it
returns is, or for any other reason.
6. Entries must be e-mailed to dmo...@xraysgi.ims.uconn.edu and received
before 23:59:59 PST, December 31, 2001. When your entry is received
it will be acknowledged by e-mail.
7. Programs will be treated as if compiled and run on a virtual machine
with an unlimited amount of memory and infinite-sized integers. In detail:
(a) All integral types T (char, signed char, unsigned char, short int,
unsigned short int, int, unsigned int, long int, and unsigned long
int) satisfy sizeof(T) == 1.
(b) char is signed by default.
(c) All signed integral types can hold an integer of arbitrarily large
magnitude, either positive, negative, or zero. Integers are
represented in 2s-complement form and can therefore be viewed as bit
strings extending infinitely far to the left:
47 = ...0000000000010111
5 = ...0000000000000101
-3 = ...1111111111111101
-5 = ...1111111111111011
(d) Unsigned integral types hold the same bit strings as the signed
integral types, but they are thought of as unsigned.
(e) Conversions from signed to unsigned integral types, either implicit
or via casts, preserve the bit string representation of the converted
number. For the purposes of section 6.2.1.5 of the standard,
a long int cannot represent all values of an unsigned int.
(f) Unary +, unary -, binary +, binary -, binary *, ==, and != act in the
usual mathematical way on signed integral types. For a and b signed,
a / b always returns the greatest integer less than or equal to a
divided by b if b>0, and is undefined if b<=0. As
required by the C standard, a % b equals a - (a/b)*b. On unsigned
integral types, these operators act as if operands were cast to
signed and the result was cast back to unsigned.
(g) <, <=, >, and >= order operands of a signed integral type according
to their mathematical values. For an unsigned integral type, the
ordering is lexicographic on the bit strings, i.e.,
-1 > -2 > -3 > -4 > ... > 4 > 3 > 2 > 1 > 0.
(h) For ~, binary &, |, and ^, the value of the result is computed bit by
bit using the bit string representation.
(i) Let POW(2,b) be 2 raised to the bth power. For a and b of signed
integral type, a << b is a*POW(2,b) if b>=0, a/POW(2,-b) if b<0,
and a >> b is a*POW(2,-b) if b<=0, a/POW(2,b) if b>0. For a and b
of unsigned integral type, the result is the same as if a and b were
cast to signed and the result was cast back to unsigned.
(j) size_t will be treated as being the same as unsigned int.
ptrdiff_t will be treated as being the same as int.
--
David Moews dmo...@xraysgi.ims.uconn.edu
Mark Duell
news:9v403c$o3u$1...@lydian.ccrwest.org...
> Rules in brief
> ----- -- -----
>
> The object of the BIGNUM BAKEOFF is to write a C program of 512 characters
> or less (excluding whitespace) that returns as large a number as possible
> from main(), assuming C to have integral types that can hold arbitrarily
> large integers. E-mail entries to dmo...@xraysgi.ims.uconn.edu by Dec 31.
I hate to reply to this, but I just have to ask why this program isnt valid:
int main( void )
{
int x=1;
while( 1 ) {
for( x==1; x==80; x++)
prinf( "9" );
printf( "\n" );
x=1;
} do
}
81 characters, but I'll be surprised if there arent any minor errors (its
quite late).
Cheers,
Mark Duell
Michael Brown
news:9v403c$o3u$1...@lydian.ccrwest.org...
> prove their program returns from main(), explain how big the number it
> returns is, or for any other reason.
Well, having to say how big it is rules me out ... Here's what I came up with
though. Feel free to reuse the idea if you think it's good ...
<<<<<<<< BEGIN >>>>>>>>
#define M(k) = L(k, k);
int x;
int L(j, n)
{
n ? Pow(j*x, j*x) : for(i = 1;i <= Pow(j, j); i++) InnerLoop(i, n-1)
return x
}
main()
{
x = 10000;
M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(M(x)))))))))))))))
)))))))))))))))))
}
<<<<<<<< END >>>>>>>>
Basically raises x to the power of itself over x! number of times, and then
repeats the whole thing multiple times. I can't even start to figure out how big
the number is :(
Michael
Mike Oliver
> I hate to reply to this, but I just have to ask why this program isnt valid:
[Program snipped; see article]
Well, it isn't valid for at least one technical reason -- the number
is supposed to be the *return* value of the program, not printed
to stdout. Plus I don't think that trailing "do" is syntactically
correct.
But certainly you can create a valid entry that'll return a number
whose decimal expansion is 80 9's in a row. The winning entry
will obviously be *much* bigger than that.
Mike Oliver
> Well, it isn't valid for at least one technical reason -- the number
> is supposed to be the *return* value of the program, not printed
> to stdout. Plus I don't think that trailing "do" is syntactically
> correct.
>
> But certainly you can create a valid entry that'll return a number
> whose decimal expansion is 80 9's in a row. The winning entry
> will obviously be *much* bigger than that.
Oh, I misread your program -- I guess you mean it to print lines
of 80 9's indefinitely. But then it never *returns*, so it's
not a valid entry.
Bart Kowalski
news:9v403c$o3u$1...@lydian.ccrwest.org...
> ----- -- -----
>
> The object of the BIGNUM BAKEOFF is to write a C program of 512 characters
> or less (excluding whitespace) that returns as large a number as possible
> from main(), assuming C to have integral types that can hold arbitrarily
> large integers. E-mail entries to dmo...@xraysgi.ims.uconn.edu by Dec 31.
[snip details]
Um, sorry if I'm ruining the fun, but given the specified implementation
would the following work?
int main()
{
return (unsigned)-1>>1;
}
Bart.
Dann Corbit
news:9v403c$o3u$1...@lydian.ccrwest.org...
I win. What an idiotic contest, and why post it to news:sci.math or
news:comp.lang.c when newsgroups like news:comp.programming.contests exist
for that expressed purpose?
Perhaps you were unaware that in C '9' is an int constant, not a character
constant.
-------- begin winning contest entry: -------
#include <stdio.h>
int main(void){while(1)putchar('9');return 0;}
-------- end winning contest entry: -------
Now go away.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. FAQ: ftp://cap.connx.com/pub/Chess%20Analysis%20Project%20FAQ.htm
Mike Kent
>
> Rules in brief
> ----- -- -----
>
> The object of the BIGNUM BAKEOFF is to write a C program of 512 characters
> or less (excluding whitespace) that returns as large a number as possible
> from main(), assuming C to have integral types that can hold arbitrarily
> large integers.
/* You will get entries like this: */
/*Ackerman */
int a(int i, int j){return (!i)?1+j:((!j)?a(i-1,1):a(i-1,a(i,j-1)));}
int A(int i){return a(i,i);} /* diagonalize */
int B(int i) {int j; int k=i; for (j=0:j<A(i);j++) k=A(k); return k; }
int C(int i) {int j; int k=i; for (j=0:j<B(i);j++) k=B(k); return k; }
...
int G(int i) {int j; int k=i; for (j=0:j<F(i);j++) k=F(k); return k; }
int main(){return G(G(G(G(...(9)...)))); }
/* and the nunber of nested G()'s and 9's {and whether to stop at G,
or at F, or go on to H or whatever], will be adjusted to give
exactly 512 characters */
/* except that someone will realize that function pointers aren't
forbidden, and that they can be used to _vastly_ improve on the
above */
/* and the rule used to determine the winner will be */
Bart Kowalski
news:9v43n...@enews1.newsguy.com...
> I win. What an idiotic contest, and why post it to news:sci.math or
> news:comp.lang.c when newsgroups like news:comp.programming.contests exist
> for that expressed purpose?
>
> Perhaps you were unaware that in C '9' is an int constant, not a character
> constant.
>
> -------- begin winning contest entry: -------
> #include <stdio.h>
> int main(void){while(1)putchar('9');return 0;}
> -------- end winning contest entry: -------
You call something idiotic and you haven't even read the rules that you
haven't bothered to snip from your post. Talk about ruthless!
- You can't use the standard library except for the mentioned functions.
- You have to return the value from main(), not print it.
- Your program has to terminate.
Bart.
Mark Duell
news:3C159453...@math.ucla.edu...
I knew it wouldnt work. And the trailing do was a flashback to do { }
while() loops, forgetting that when you reverse it you drop the do.
Mark Duell
Ioannis
>
> Rules in brief
> ----- -- -----
>
> The object of the BIGNUM BAKEOFF is to write a C program of 512 characters
> or less (excluding whitespace) that returns as large a number as possible
> from main(), assuming C to have integral types that can hold arbitrarily
> large integers. E-mail entries to dmo...@xraysgi.ims.uconn.edu by Dec 31.
>
> Sample entry
> ------ -----
> To: dmo...@xraysgi.ims.uconn.edu
> From: jo...@doe.com
> Subject: BIGNUM BAKEOFF entry
>
> Here is my program:
> ----------------------------------
> int ipow(int a, int b)
> { return b ? a*ipow(a,b-1) : 1; }
> int ipowstack(int a, int b)
> { return b ? ipow(a,ipowstack(a,b-1)) : 1; }
> int main(void)
> { return ipowstack(999,999); }
> ----------------------------------
> It returns a number equal to an exponential tower of 999s, 999 numbers high.
>
> Rules in detail
> ----- -- ------
[snip rules]
This ought to be fun :*)
int a(int k,int m,int n)
{if (k==1) return(m+n);
else {if (n==1) return m;
else return(a(k-1,m,a(k,m,n-1)));}}
int main(void)
{int m;m=9999999999999999999999999999999999999+
9999999999999999999999999999999999999+
9999999999999999999999999999999999999+
9999999999999999999999999999999999999+
9999999999999999999999999999999999999+
9999999999999999999999999999999999999+
9999999999999999999999999999999999999+
9999999999999999999999999999999999999+
9999999999999999999999999999999999999+
9999999;
return a(m,m,m);}
I think that the above would be pretty hard to beat:*). It terminates
since 'a' is the well-known three-argument recursive Ackermann function:
a(1,m,n)=m+n
a(2,m,n)=m*n
a(3,m,n)=m^n
a(4,m,n)=n@m, i.e. m^(m^(m^(...^m))) (n-times)
a(5,m,n)=(((m@m)@m)...)@m (n-times)
etc.
The value of m in main should be the maximum number of 9's so that the
total length of the program is exactly 512 characters long.
In particular, the example program given in the rules calculates
a(4,999,999)
> --
> David Moews dmo...@xraysgi.ims.uconn.edu
--
Ioannis
http://users.forthnet.gr/ath/jgal/
_______________________________________
"The best way to predict reality, is
to know exactly what you _don't_ want."
[Addendum to Murphy's Laws #738]
Dann Corbit
news:EQgR7.7603$Us5.1...@news20.bellglobal.com...
Implementation defined behavior.
> - Your program has to terminate.
Wait one trillion years, and hit <CTRL-C>
BTW:
*plonk*
Mike Oliver
> /* and the rule used to determine the winner will be */
>
>> 4. The program which returns the number with largest absolute value from
>> main() will win. If there is a set of programs for which it cannot
>> be determined which program in the set returns the biggest number,
>> all programs in the set will win jointly.
That seems a plausible prediction, and it means that the rule has
an unfortunate ambiguity. Probably it should have said "if the
judges are unable to determine...", but it doesn't. It says
"cannot be determined", leaving open the question of by whom or
by what methods, or what will be considered sufficient evidence
that the problem cannot be resolved.
The Scarlet Manuka
news:3C15A4...@ath.forthnet.gr...
[snip]
> return a(m,m,m);}
>
> I think that the above would be pretty hard to beat:*). It terminates
> since 'a' is the well-known three-argument recursive Ackermann function:
[...]
> The value of m in main should be the maximum number of 9's so that the
> total length of the program is exactly 512 characters long.
But is this optimal?
I suspect that you might be better with 8 less digits in m, and
returning
a(a(m, m, m), m, m)
Of course you can iterate this further.
I wonder where the best tradeoff is... it might even be best to
define a function b(k) = a(k, k, k) and return b(b(b(...b(m)...))).
The derivation of the optimal number of calls to b is left as an
exercise for the VERY diligent student!
--
The Scarlet Manuka
Richard Heathfield
Slight improvement:
#include <limits.h>
int main(void)
{
return INT_MAX;
}
I suspect these are both maximally winning entries.
--
Richard Heathfield : bin...@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
Zoran Cutura
The returned number will simply be in the range of INT_MIN to
INT_MAX, even though the value you hoped to produce should be
way bigger than INT_MAX on a usual system.
--
Z (Zoran....@daimlerchrysler.com)
"LISP is worth learning for the profound enlightenment experience
you will have when you finally get it; that experience will make you
a better programmer for the rest of your days." -- Eric S. Raymond
Mike Oliver
> The returned number will simply be in the range of INT_MIN to
> INT_MAX, even though the value you hoped to produce should be
> way bigger than INT_MAX on a usual system.
I think you missed rule 7.
Tim Woodall
David Moews <dmo...@xraysgi.ims.uconn.edu> wrote:
There are some fundamental problems here with infinities.
unsigned int max = ~0; /* an infinite number of ones */
int maxint = max; /* What does this equal? is it +ve or -ve? */
I can't be bothered to look up in the standard but ISTR that if a unsigned
int value can be represented in an int value then the value of the int
value is the same as the value of the unsigned int value if the unsigned int
is assigned to the int.
But all unsigned int values can be represented as int values.
int othermaxint = (max >> 1); /* what about this? */
so:
int main(void) { return (unsigned int)~0; }
or
int main(void) { return ((unsigned int)~0 >> 1); }
ought to give a return value of +inf or possibly -inf for the first one.
If you want a value one less than infinity :-)
int main(void) { return (unsigned int)-2; }
or if the top bit has to be 0
int main(void) { return ((unsigned int)-3 >> 1); }
Does the second pair of programs lose to the first pair?
Regards,
Tim.
--
God said, "div D = rho, div B = 0, curl E = - @B/@t, curl H = J + @D/@t,"
and there was light.
http://locofungus.2y.net/ http://www.locofungus.btinternet.co.uk/
Ioannis
[snip]
> But is this optimal?
>
> I suspect that you might be better with 8 less digits in m, and
> returning
>
> a(a(m, m, m), m, m)
>
> Of course you can iterate this further.
>
> I wonder where the best tradeoff is... it might even be best to
> define a function b(k) = a(k, k, k) and return b(b(b(...b(m)...))).
> The derivation of the optimal number of calls to b is left as an
> exercise for the VERY diligent student!
What you suggest certainly _sounds_ plausible:
If one defines: b(m)=a(m,m,m) then your query amounts to:
What is the minimum m1 < m2, such that d(d(m1)) >= d(m2) ?
Seems very likely that such a m1 exists, but I doubt anybody can prove
it rigorously. In fact, I would be curious to see just _how_ the judges
will decide which programs will produce a larger integer:
the one with m=999...9 (t 9's) and d(m) or
the one with m=999...9 (t-3 9's) and d(d(m)) or
the one with m=999...9 (t-6 9's) and d(d(d(m))) or
...
The numbers returned above, d(m), d(d(m)), d(d(d(m))) will be so huge,
that _any_ virtual machine will have problems representing them. And I
don't quite see how any human can possibly compare them. Let alone any
"diligent student"...:*)
> --
> The Scarlet Manuka
Bart Kowalski
news:3C15AE64...@eton.powernet.co.uk...
> Bart Kowalski wrote:
> >
> > "David Moews" <dmo...@xraysgi.ims.uconn.edu> wrote in message
> > news:9v403c$o3u$1...@lydian.ccrwest.org...
> > > Rules in brief
> > > ----- -- -----
> > >
> > > The object of the BIGNUM BAKEOFF is to write a C program of 512 characters
> > > or less (excluding whitespace) that returns as large a number as possible
> > > from main(), assuming C to have integral types that can hold arbitrarily
> > > large integers. E-mail entries to dmo...@xraysgi.ims.uconn.edu by Dec 31.
> >
> > [snip details]
> >
> > Um, sorry if I'm ruining the fun, but given the specified implementation
> > would the following work?
> >
> > int main()
> > {
> > return (unsigned)-1>>1;
> > }
>
> Slight improvement:
>
> #include <limits.h>
> int main(void)
> {
> return INT_MAX;
> }
>
> I suspect these are both maximally winning entries.
That was my first guess, but one rule says that you're not supposed to
use the standard library.
Bart.
Bart Kowalski
> "Bart Kowalski" <m...@nospam.com> wrote in message
> news:EQgR7.7603$Us5.1...@news20.bellglobal.com...
>
> Wait one trillion years, and hit <CTRL-C>
>
> BTW:
> *plonk*
LOL! You're plonking me because I have pointed out flaws in your
supposedly "winning" entry? How cute. It's quite amusing to see such
childish behavior in clc.
Bart.
Daniel Haude
Richard Heathfield <bin...@eton.powernet.co.uk> wrote
in Msg. <3C15AE64...@eton.powernet.co.uk>
| Bart Kowalski wrote:
| >
| > Um, sorry if I'm ruining the fun, but given the specified implementation
| > would the following work?
| >
| > int main()
| > {
| > return (unsigned)-1>>1;
| > }
|
| Slight improvement:
|
| #include <limits.h>
| int main(void)
| {
| return INT_MAX;
| }
|
| I suspect these are both maximally winning entries.
They are, because they return infinity by definition (see rule 7).
And they prove the utter stupidity of the contest. I think the contest
would be funnier if the language had to be English, not C, and you
couldn't use digits (just words) and "well-known" math speak such as
"plus", "times", "raised to the power of" etc.
--Daniel
--
"The obvious mathematical breakthrough would be development of an easy
way to factor large prime numbers." -- Bill Gates, "The Road Ahead"
- Kees van der Bent -
> Um, sorry if I'm ruining the fun, but given the specified implementation
> would the following work?
>
> int main()
> {
> return (unsigned)-1>>1;
> }
K&R 2nd (I don't have the standard) page 206 states:
"The value of E1>>E2 is E1 right-shifted E2 bit positions.
The right shift is equivalent to division by 2^E2 if E1 is
unsigned or if it has a non-negative value; otherwise the
result is implementation-defined."
Your solution assumes 2-s complement negative numbers and I guess
that's why it is implementation-defined. Maybe someone having
access to the C standard could comment on that.
Sorry for ruining the fun.
Kees
Richard Heathfield
INT_MAX isn't in the standard library. It's in a standard header.
Headers are not libraries.
Richard Heathfield
No need. The rules as originally posted *specifically* allow and indeed
mandate this assumption of two's complement integer representation.
>
> Sorry for ruining the fun.
I think you'll have to try harder. :-)
- Kees van der Bent -
> Rules in brief
> ----- -- -----
>
> The object of the BIGNUM BAKEOFF is to write a C program of 512 characters
> or less (excluding whitespace) that returns as large a number as possible
> from main(), assuming C to have integral types that can hold arbitrarily
> large integers. E-mail entries to dmo...@xraysgi.ims.uconn.edu by Dec 31.
<snip>
> 6. Entries must be e-mailed to dmo...@xraysgi.ims.uconn.edu and received
> before 23:59:59 PST, December 31, 2001. When your entry is received
> it will be acknowledged by e-mail.
What's so special about 23:59:59 PST, December 31, 2001 (wrt 23:59:58
for example) that I not allowed to submit my winning entry in this
second?
Kees
Carl McGuire
"David Moews" <dmo...@xraysgi.ims.uconn.edu> wrote in message
news:9v403c$o3u$1...@lydian.ccrwest.org...
> ----- -- -----
>
> The object of the BIGNUM BAKEOFF is to write a C program of 512 characters
> or less (excluding whitespace) that returns as large a number as possible
> from main(), assuming C to have integral types that can hold arbitrarily
> large integers. E-mail entries to dmo...@xraysgi.ims.uconn.edu by Dec 31.
>
>
>
> ------ -----
> To: dmo...@xraysgi.ims.uconn.edu
> From: jo...@doe.com
> Subject: BIGNUM BAKEOFF entry
>
> Here is my program:
> ----------------------------------
> int ipow(int a, int b)
> { return b ? a*ipow(a,b-1) : 1; }
> int ipowstack(int a, int b)
> { return b ? ipow(a,ipowstack(a,b-1)) : 1; }
> int main(void)
> { return ipowstack(999,999); }
> ----------------------------------
> It returns a number equal to an exponential tower of 999s, 999 numbers
high.
>
Mine's the same but the last line is changed to
{ return ipowstack(999,999)+1; }
I beat you anyway!
Carl ;-)
Eric Nordmeyer
Good point, I was about to mention that. Thank you!
Working exactly helps once in a while if you're a programmer.
Eric
Bruce Wheeler
Actually, they both make use of implementation-defined behavior, and
therefore don't qualify :-).
Quoting from N869, as I don't have C90.
5.1.2.2.3 Program termination
[#1] If the return type of the main function is a type
compatible with int, a return from the initial call to the
main function is equivalent to calling the exit function
with the value returned by the main function as its
argument;9) reaching the } that terminates the main function
returns a value of 0. If the return type is not compatible
with int, the termination status returned to the host
environment is unspecified.
7.20.4.3 The exit function
[#5] Finally, control is returned to the host environment.
If the value of status is zero or EXIT_SUCCESS, an
implementation-defined form of the status successful
termination is returned. If the value of status is
EXIT_FAILURE, an implementation-defined form of the status
unsuccessful termination is returned. Otherwise the status
returned is implementation-defined.
The test clearly needed to be better specified.
We need to return 0, EXIT_FAILURE, or EXIT_SUCCESS, so we take the one
with the largest absolute value.
My entry is:
#include <stdlib.h>
int myAbs(int x)
{
return x > 0 ? x : -x;
}
int main(void)
{
int aS = myAbs(EXIT_SUCCESS);
int aF = myAbs(EXIT_FAILURE);
return aS > aF ? aS : aF;
}
Also, based on 7.20.4.3, I'm not sure the problem allows any solution,
though, as in all cases, 'an implementation-defined form of the status
... is returned' .
Regards,
Bruce Wheeler
Bart Kowalski
> Bart Kowalski wrote:
> >
> > That was my first guess, but one rule says that you're not supposed to
> > use the standard library.
>
> INT_MAX isn't in the standard library. It's in a standard header.
> Headers are not libraries.
Ah yes. That must be why all the headers appears under the clause
"Library" in the standard.
Bart.
Bart Kowalski
news:3c16236e...@news.siemens.at...
> On Tue, 11 Dec 2001 06:57:40 +0000, Richard Heathfield
> <bin...@eton.powernet.co.uk> wrote:
>
> >Bart Kowalski wrote:
> >>
> >> "David Moews" <dmo...@xraysgi.ims.uconn.edu> wrote in message
> >> news:9v403c$o3u$1...@lydian.ccrwest.org...
> >> > Rules in brief
> >> > ----- -- -----
> >> >
> >> > The object of the BIGNUM BAKEOFF is to write a C program of 512
characters
> >> > or less (excluding whitespace) that returns as large a number as possible
> >> > from main(), assuming C to have integral types that can hold arbitrarily
> >> > large integers. E-mail entries to dmo...@xraysgi.ims.uconn.edu by Dec
31.
> >>
> >> [snip details]
> >>
> >> Um, sorry if I'm ruining the fun, but given the specified implementation
> >> would the following work?
> >>
> >> int main()
> >> {
> >> return (unsigned)-1>>1;
> >> }
> >
> >Slight improvement:
> >
> >#include <limits.h>
> >int main(void)
> >{
> > return INT_MAX;
> >}
> >
> >I suspect these are both maximally winning entries.
> >
>
> therefore don't qualify :-).
I think not.
> (b) No use of implementation-defined, locale-specific, or
> undefined behavior, except for behavior defined in 7. below.
...
Under 7:
> (i) Let POW(2,b) be 2 raised to the bth power. For a and b of
> signed integral type, a << b is a*POW(2,b) if b>=0, a/POW(2,-b)
> if b<0, and a >> b is a*POW(2,-b) if b<=0, a/POW(2,b) if b>0.
> For a and b of unsigned integral type, the result is the same
> as if a and b were cast to signed and the result was cast back
> to unsigned.
So since it's allowed by the rules, we can use it.
Bart.
Bart Kowalski
> > therefore don't qualify :-).
>
> I think not.
Oops! Ignore my previous post. Didn't read carefully.
Bart.
Richard Hayden
int x;
int main(void) {
x = 9;
t = 9;
while (x <
9999999999999999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999) {
x = x + 1;
t = t * POW(t, POW(t,
9999999999999999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999));
}
return t;
}
Ignore wordwrap.
509 characters long.
"David Moews" <dmo...@xraysgi.ims.uconn.edu> wrote in message
news:9v403c$o3u$1...@lydian.ccrwest.org...
> Rules in brief
> ----- -- -----
>
> The object of the BIGNUM BAKEOFF is to write a C program of 512 characters
> or less (excluding whitespace) that returns as large a number as possible
> from main(), assuming C to have integral types that can hold arbitrarily
> large integers. E-mail entries to dmo...@xraysgi.ims.uconn.edu by Dec 31.
>
>
>
> Sample entry
> ------ -----
> To: dmo...@xraysgi.ims.uconn.edu
> From: jo...@doe.com
> Subject: BIGNUM BAKEOFF entry
>
> Here is my program:
> ----------------------------------
> int ipow(int a, int b)
> { return b ? a*ipow(a,b-1) : 1; }
> int ipowstack(int a, int b)
> { return b ? ipow(a,ipowstack(a,b-1)) : 1; }
> int main(void)
> { return ipowstack(999,999); }
> ----------------------------------
> It returns a number equal to an exponential tower of 999s, 999 numbers
high.
>
>
>
> Rules in detail
> ----- -- ------
>
> 1. Programs are to be written in C90, i.e., the 1990 C standard,
> ANSI/ISO 9899-1990, subject to the following constraints:
>
> (a) No use of floating constants, float, double, long double, or other
> floating types.
> (b) No use of implementation-defined, locale-specific, or undefined
> behavior, except for behavior defined in 7. below.
> 6. Entries must be e-mailed to dmo...@xraysgi.ims.uconn.edu and received
> before 23:59:59 PST, December 31, 2001. When your entry is received
> it will be acknowledged by e-mail.
>
> integral types, these operators act as if operands were cast to
> signed and the result was cast back to unsigned.
> (g) <, <=, >, and >= order operands of a signed integral type
according
> to their mathematical values. For an unsigned integral type, the
> ordering is lexicographic on the bit strings, i.e.,
>
> -1 > -2 > -3 > -4 > ... > 4 > 3 > 2 > 1 > 0.
>
> (h) For ~, binary &, |, and ^, the value of the result is computed bit
by
> bit using the bit string representation.
> (i) Let POW(2,b) be 2 raised to the bth power. For a and b of signed
> integral type, a << b is a*POW(2,b) if b>=0, a/POW(2,-b) if b<0,
> and a >> b is a*POW(2,-b) if b<=0, a/POW(2,b) if b>0. For a and b
> of unsigned integral type, the result is the same as if a and b
were
> cast to signed and the result was cast back to unsigned.
> (j) size_t will be treated as being the same as unsigned int.
> ptrdiff_t will be treated as being the same as int.
> --
> David Moews
dmo...@xraysgi.ims.uconn.edu
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.306 / Virus Database: 166 - Release Date: 04/12/2001
Richard Heathfield
Your logic escapes me. Are you seriously contending that headers are
libraries?
Bart Kowalski
> Bart Kowalski wrote:
> >
> > "Richard Heathfield" <bin...@eton.powernet.co.uk> wrote in message
> > news:3C1615C8...@eton.powernet.co.uk...
> > > Bart Kowalski wrote:
> > > >
> > > > That was my first guess, but one rule says that you're not supposed to
> > > > use the standard library.
> > >
> > > INT_MAX isn't in the standard library. It's in a standard header.
> > > Headers are not libraries.
> >
> > Ah yes. That must be why all the headers appears under the clause
> > "Library" in the standard.
>
> Your logic escapes me. Are you seriously contending that headers are
> libraries?
No, I'm just arguing that when someone refers to "The Standard Library"
they probably mean all declarations and definitions made available
through one or more standard headers. If that wasn't the case then NULL
wouldn't have been mentioned in the list of exceptions.
Bart.
Bruce Wheeler
That's okay. I know what it's like to post too quickly!
I had typed in:
int main(void)
{
int aS = myAbs(EXIT_SUCCESS);
int aF = myAbs(EXIT_FAILURE);
return aS > aF ? aS : aF;
}
I typed that in too quickly. I was returning the absolute value
of the exit status, and not the exit status itself.
My corrected entry :-)
#include <stdlib.h>
int myAbs(int x)
{
return x > 0 ? x : -x;
}
int main(void)
{
int aS = myAbs(EXIT_SUCCESS);
int aF = myAbs(EXIT_FAILURE);
return aS > aF ? EXIT_SUCCESS : EXIT_FAILURE;
}
Regards,
Bruce Wheeler
Nis Jorgensen
<ke...@feastures.com> wrote:
>
>> 6. Entries must be e-mailed to dmo...@xraysgi.ims.uconn.edu and received
>> before 23:59:59 PST, December 31, 2001. When your entry is received
>> it will be acknowledged by e-mail.
>
>
>
>What's so special about 23:59:59 PST, December 31, 2001 (wrt 23:59:58
>for example) that I not allowed to submit my winning entry in this
>second?
It has to be recieved before that time, not submitted. Thus, nothing
specifically disallows you from submitting it later.
--
Nis Jorgensen
Amsterdam
Please include only relevant quotes, and reply below the quoted text. Thanks
Dave Seaman
Bart Kowalski <m...@nospam.com> wrote:
>"Richard Heathfield" <bin...@eton.powernet.co.uk> wrote in message
>news:3C164EA8...@eton.powernet.co.uk...
>> Bart Kowalski wrote:
>> > "Richard Heathfield" <bin...@eton.powernet.co.uk> wrote in message
>> > news:3C1615C8...@eton.powernet.co.uk...
>> > > Bart Kowalski wrote:
>> > > > That was my first guess, but one rule says that you're not supposed to
>> > > > use the standard library.
>> > > INT_MAX isn't in the standard library. It's in a standard header.
>> > > Headers are not libraries.
>> > Ah yes. That must be why all the headers appears under the clause
>> > "Library" in the standard.
>> Your logic escapes me. Are you seriously contending that headers are
>> libraries?
>No, I'm just arguing that when someone refers to "The Standard Library"
>they probably mean all declarations and definitions made available
>through one or more standard headers. If that wasn't the case then NULL
>wouldn't have been mentioned in the list of exceptions.
That is especially true in C++, where "The Standard Library" most
definitely does include things like class declarations, function
templates, implementation-defined constants, and other things that are
contained in header files. We have the word of Bjarne Stroustrup on
that.
The notion of a "standard library" as implemented by some language
processor may be much more general than the traditional notion of a
"library file" as maintained by a particular linking loader.
--
Dave Seaman dse...@purdue.edu
Amnesty International calls for new trial for Mumia Abu-Jamal
<http://www.amnestyusa.org/abolish/reports/mumia/>
Dave Seaman
Nis Jorgensen <n...@dkik.dk> wrote:
>On Tue, 11 Dec 2001 15:54:19 +0100, - Kees van der Bent -
><ke...@feastures.com> wrote:
>>> 6. Entries must be e-mailed to dmo...@xraysgi.ims.uconn.edu and received
>>> before 23:59:59 PST, December 31, 2001. When your entry is received
>>> it will be acknowledged by e-mail.
>>What's so special about 23:59:59 PST, December 31, 2001 (wrt 23:59:58
>>for example) that I not allowed to submit my winning entry in this
>>second?
>It has to be recieved before that time, not submitted. Thus, nothing
>specifically disallows you from submitting it later.
I think the question was, why are entries accepted at 1.001 seconds
before midnight, but not at 0.999 seconds before midnight?
Mike Oliver
> It has to be recieved before that time, not submitted. Thus, nothing
> specifically disallows you from submitting it later.
Right, you can submit it later. Just not for the *first* time.
Mike Oliver
>
> On Tue, 11 Dec 2001 06:57:40 +0000,
> Richard Heathfield <bin...@eton.powernet.co.uk> wrote
> in Msg. <3C15AE64...@eton.powernet.co.uk>
> | int main(void)
> | {
> | return INT_MAX;
> | }
> |
> | I suspect these are both maximally winning entries.
>
> They are, because they return infinity by definition (see rule 7).
The intent of rule 7, as I read it, is that an integer variable is
supposed to be able to hold a *mathematical* integer. Therefore
there is no INT_MAX, and (unsigned)(-1)>>1 is simply -1 again.
> And they prove the utter stupidity of the contest.
Nonsense. The INT_MAX one might show that the specific details
of the rules weren't thought through perfectly. (Even that
I'm not sure about; maybe there's some little clause I missed
that excludes it.
But the idea of the contest is valid and interesting, and I'm curious
to see how it comes out.
Norm Dresner
Ioannis <jg...@ath.forthnet.gr> wrote in message
news:3C15A4...@ath.forthnet.gr...
> This ought to be fun :*)
>
> int a(int k,int m,int n)
> {if (k==1) return(m+n);
> else {if (n==1) return m;
> else return(a(k-1,m,a(k,m,n-1)));}}
> int main(void)
> {int m;m=9999999999999999999999999999999999999+
> 9999999999999999999999999999999999999+
> 9999999999999999999999999999999999999+
> 9999999999999999999999999999999999999+
> 9999999999999999999999999999999999999+
> 9999999999999999999999999999999999999+
> 9999999999999999999999999999999999999+
> 9999999999999999999999999999999999999+
> 9999999999999999999999999999999999999+
> 9999999;
> return a(m,m,m);}
>
> I think that the above would be pretty hard to beat:*). It terminates
> since 'a' is the well-known three-argument recursive Ackermann function:
>
> a(1,m,n)=m+n
> a(2,m,n)=m*n
> a(3,m,n)=m^n
> a(4,m,n)=n@m, i.e. m^(m^(m^(...^m))) (n-times)
> a(5,m,n)=(((m@m)@m)...)@m (n-times)
> etc.
>
> The value of m in main should be the maximum number of 9's so that the
> total length of the program is exactly 512 characters long.
>
> In particular, the example program given in the rules calculates
> a(4,999,999)
>
> Ioannis
>
Wouldn't a program that computed, say,
a( a( n1 , n2 , n3 ) , a( n4 , n5 , n6 ) , a( n7 , n8 , n9 ) )
for suitably chosen integers compute an even larger number? And we don't
have to limit it to the above, we could get rediculously large numbers using
a( a( a( ...
for a few suitably chosen levels of "recursion" in the arguments to get some
whopping big numbers and still stay within the 512 character limit?
Norm
CBFalconer
>
> On Tue, 11 Dec 2001 15:54:19 +0100, - Kees van der Bent -
>
> >> before 23:59:59 PST, December 31, 2001. When your entry is received
> >> it will be acknowledged by e-mail.
> >
> >What's so special about 23:59:59 PST, December 31, 2001 (wrt 23:59:58
> >for example) that I not allowed to submit my winning entry in this
> >second?
>
> It has to be recieved before that time, not submitted. Thus, nothing
> specifically disallows you from submitting it later.
The original is gone from here, but at any rate:
unsigned int u; /* initialized to zero, see standard */
int main(void)
{
u--; /* wraps to UINT_MAX, see standard */
return u; /* unlimited, see rules */
}
NOTE: since int is unlimited, it must be able to express the value
of UINT_MAX
so my entry is:
"unsigned int u;int main(void){return --u;}"
123456789012345678901234567890123456789012
or 42 chars. We can probably elide " int" and the space before
--, for 37 chars. The only standard failing is that it returns a
value whose effects are undefined, but this is enforced by the
rules.
--
Chuck F (cbfal...@yahoo.com) (cbfal...@XXXXworldnet.att.net)
Available for consulting/temporary embedded and systems.
(Remove "XXXX" from reply address. yahoo works unmodified)
mailto:u...@ftc.gov (for spambots to harvest)
Derrick Coetzee
>
> Nonsense. The INT_MAX one might show that the specific details
> of the rules weren't thought through perfectly. (Even that
> I'm not sure about; maybe there's some little clause I missed
> that excludes it.
>
> But the idea of the contest is valid and interesting, and I'm curious
> to see how it comes out.
Even if INT_MAX IS allowed, the contest didn't modify the headers in its
rules. It will still equal 2^31-1, not the largest arbitrary-precision
integer, which of course would consume an infinite amount of memory. :-)
-Derrick Coetzee
Derrick Coetzee
>>Rules in detail
>>----- -- ------
For God's sake, CLIP!
> I win. What an idiotic contest, and why post it to news:sci.math or
> news:comp.lang.c when newsgroups like news:comp.programming.contests exist
> for that expressed purpose?
It's actually a very mathematical contest, since the C ints have been
turned into arbitrary-precision integers (integers as defined in math,
basically.)
> Perhaps you were unaware that in C '9' is an int constant, not a character
> constant.
Don't accuse others of being idiotic when you don't know what the hell
you're talking about. '9' is a character constant, having an value of
type char that is implementation-dependent but usually the ASCII value
> #include <stdio.h>
> int main(void){while(1)putchar('9');return 0;}
As others have said, read the rules. You're supposed to return it from
main().
> Now go away.
Gladly.
-Derrick Coetzee
Derrick Coetzee
> Mike Kent wrote:
>
>
>>/* and the rule used to determine the winner will be */
>>
>>
>>>4. The program which returns the number with largest absolute value from
>>> main() will win. If there is a set of programs for which it cannot
>>> be determined which program in the set returns the biggest number,
>>> all programs in the set will win jointly.
>>>
>
> That seems a plausible prediction, and it means that the rule has
> an unfortunate ambiguity. Probably it should have said "if the
> judges are unable to determine...", but it doesn't. It says
> "cannot be determined", leaving open the question of by whom or
> by what methods, or what will be considered sufficient evidence
> that the problem cannot be resolved.
>
As long as nobody loses anything from it though, which they won't since
all such entries win, no one will complain unless they're silly.
-Derrick Coetzee
Ben Pfaff
> Dann Corbit wrote:
>
> > Perhaps you were unaware that in C '9' is an int constant, not a character
> > constant.
>
> Don't accuse others of being idiotic when you don't know what the hell
> you're talking about. '9' is a character constant,
Yes.
> having an value of type char
No. A character constant always has type int.
--
"It wouldn't be a new C standard if it didn't give a
new meaning to the word `static'."
--Peter Seebach on C99
Tak-Shing Chan
> Derrick Coetzee <ne...@moonflare.com> writes:
>> '9' is a character constant,
>
> Yes.
>
>> having an value of type char
>
> No. A character constant always has type int.
Derrick sounds like a typical ``C/C++'' programmer <g,d&r>.
Tak-Shing
Dann Corbit
news:3uvR7.158762$WW.99...@bgtnsc05-news.ops.worldnet.att.net...
[snip]
> Wouldn't a program that computed, say,
> a( a( n1 , n2 , n3 ) , a( n4 , n5 , n6 ) , a( n7 , n8 , n9 ) )
> for suitably chosen integers compute an even larger number? And we don't
> have to limit it to the above, we could get rediculously large numbers
using
> a( a( a( ...
> for a few suitably chosen levels of "recursion" in the arguments to get
some
> whopping big numbers and still stay within the 512 character limit?
Ackermann with that size of input will not be returning any time soon.
If you want really big numbers, why not iterated exponentials (related to
the Archimedean Cycles idea)? But then again, "assuming that the OS has
integers of infinite size" is sort of like the old joke:
'The USDA once wanted to make cows produce milk faster, to improve the dairy
industry.
So, they decided to consult the foremost biologists and
recombinant DNA technicians to build them a better cow.
They assembled this team of great scientists, and gave them
unlimited funding. They requested rare chemicals, weird
bacteria, tons of quarantine equipment, there was a
God-awful typhus epidemic they started by accident,
and, 2 years later, they came back with the "new, improved cow."
It had a milk production improvement of 2% over the
original.
They then tried with the greatest Nobel Prize winning chemists
around. They worked for six months, and, after requisitioning
tons of chemical equipment, and poisoning half the small town
in Colorado where they were working with a toxic cloud from
one of their experiments, they got a 5% improvement in milk output.
The physicists tried for a year, and, after ten thousand cows were
subjected to radiation therapy, they got a 1% improvement in output.
Finally, in desperation, they turned to the mathematicians. The
foremost mathematician of his time offered to help them with the problem.
Upon hearing the problem, he told the delegation that they could come back
in the morning and he would have solved the problem. In the morning,
they came back, and he handed them a piece of paper with the
computations for the new, 300% improved milk cow.
The plans began:
"A Proof of the Attainability of Increased Milk Output from Bovines:
Consider a spherical cow......"
Chet Murthy, Cornell'
The whole idea is poorly conceived, ill designed, and posted to the entirely
wrong forum.
news:comp.programming.contests is the obvious place for that piece of plop
to have landed.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. FAQ: ftp://cap.connx.com/pub/Chess%20Analysis%20Project%20FAQ.htm
Mike Oliver
> unsigned int u; /* initialized to zero, see standard */
>
> int main(void)
> {
> u--; /* wraps to UINT_MAX, see standard */
> return u; /* unlimited, see rules */
> }
> NOTE: since int is unlimited, it must be able to express the value
> of UINT_MAX
Come on, guys, then intent of the rules is clear. By rule 7 according
to any reasonable reading, there is no such thing as UINT_MAX or INT_MAX;
an int is supposed to be able to contain a *mathematical* integer,
and there's no largest such. (There are infinite *quantities* in any
number of ways, but none of them is a largest integer.)
The rules probably are not written perfectly; they should have explicitly
changed the standard to say that INT_MAX and UINT_MAX are banned and
that any attempt to assign or cast a negative value to an unsigned
results in an arithmetic exception, or some such. But the intent
is clear and the question is interesting; I hope there'll be people
who will actually try the contest and that some non-obvious conclusions
will come out of it.
Dann Corbit
news:3C16BBDB...@math.ucla.edu...
> CBFalconer wrote:
> > unsigned int u; /* initialized to zero, see standard */
> >
> > int main(void)
> > {
> > u--; /* wraps to UINT_MAX, see standard */
> > return u; /* unlimited, see rules */
> > }
> > NOTE: since int is unlimited, it must be able to express the value
> > of UINT_MAX
>
> Come on, guys, then intent of the rules is clear. By rule 7 according
> to any reasonable reading, there is no such thing as UINT_MAX or INT_MAX;
Then it's not a C compiler. Why bother to specify a language at all?
> an int is supposed to be able to contain a *mathematical* integer,
> and there's no largest such. (There are infinite *quantities* in any
> number of ways, but none of them is a largest integer.)
Where are we going to store this thing? Nobody can actually write a program
to accomplish such as thing as you propose.
> The rules probably are not written perfectly; they should have explicitly
> changed the standard to say that INT_MAX and UINT_MAX are banned and
> that any attempt to assign or cast a negative value to an unsigned
> results in an arithmetic exception, or some such. But the intent
> is clear and the question is interesting;
The intent is neither clear nor interesting. THIS MESSAGE IS OFF TOPIC IN
news:comp.lang.c and TOPICAL in news:comp.programming.contests.
> I hope there'll be people
> who will actually try the contest and that some non-obvious conclusions
> will come out of it.
The entire thing is absolutely idiotic. If you want a mathematical exercise
to find the function which grows the fastest, that would be interesting and
topical in news:sci.math.
If, on the other hand, you had questions about implementation details for an
actual C function, that might be interesting and topical in
news:comp.lang.c.
What you have is neither. Your post, by its very nature, is
self-contradictory and now you are modifying the rules on the fly to make it
seem less nonsensical. It does not matter, because it still is not a well
formed notion. It will be impossible to do what you deem in the C language,
and so you are really left with a paper specification for some non-C-like
language that you will have to invent as you go along. The signature of the
main function returns int, and you are not allowed to modify native types,
even in C++. Therefore, the largest actual implementation will have an
integral type no larger than INT_MAX, and that is the largest value which is
possible to return by the language standard itself.
By the way, there are C++ number classes that can be used to actually
*compute* large values. That might actually be interesting, if there were
some content to the contest. As it is, we have self-contradictory, vacuous
stupidity. The goal is not interesting. The method is not interesting, and
it is off-topic for both newsgroups to which you have posted it.
GO AWAY!
Mike Oliver
> What you have is neither. Your post, by its very nature, is
> self-contradictory and now you are modifying the rules on the fly to make it
> seem less nonsensical.
I dare say you lost track of your posters at some point. I am not
the originator of the contest, and am not empowered to modify its rules,
on the fly or otherwise.
> It does not matter, because it still is not a well
> formed notion. It will be impossible to do what you deem in the C language,
> and so you are really left with a paper specification for some non-C-like
> language that you will have to invent as you go along.
To me, a mathematician, the language looks quite C-like indeed, although
I agree that it's not exactly C. It is, so to speak, what C "would have been"
if it had been implemented for machines with unlimited storage.
The contest is an exploration of what the Busy Beaver function would
look like if it were defined, not in terms of Turing machines, but
in terms of idealized-C-machines. I think that's kind of interesting.
You don't. Fine. Don't read the thread.
Mike Oliver
> Let's put aside UINT_MAX. Why is code above
> (or even simpler "return (unsigned)-1;") is not a "solution"?
> In reality the rules are incorrect and a problem does not have any
> sense.
The rules may not be precisely correct; I haven't analyzed them
in detail and don't know the reasons for all the choices that
were made. In conception, though, the problem makes a lot
of sense, and the reason that "return (unsigned)-1;" is not
a solution is that you're supposed to interpret strings
that, past some point on the left, consist entirely of 1's,
*only* as negative numbers. There *is* no (unsigned)-1.
Richard Heathfield
>
> Mike Oliver wrote:
>
> >
> > Nonsense. The INT_MAX one might show that the specific details
> > of the rules weren't thought through perfectly. (Even that
> > I'm not sure about; maybe there's some little clause I missed
> > that excludes it.
> >
> > But the idea of the contest is valid and interesting, and I'm curious
> > to see how it comes out.
>
> Even if INT_MAX IS allowed, the contest didn't modify the headers in its
> rules.
Agreed.
> It will still equal 2^31-1,
Only if that's the largest int value the system can hold, which we are
assured is not the case.
> not the largest arbitrary-precision
> integer,
If ints are arbitrary-precision, then INT_MAX is required to define the
largest of them.
> which of course would consume an infinite amount of memory. :-)
Yes. That's why the whole thing is pointless. The implementation can't
exist.
James Waldby
> David Moews wrote:
> > Rules in brief
...
> > 6. Entries must be e-mailed to dmo...@xraysgi.ims.uconn.edu and received
> > before 23:59:59 PST, December 31, 2001.
> What's so special about 23:59:59 PST, December 31, 2001 (wrt 23:59:58
> for example) that I not allowed to submit my winning entry in this
> second?
Of course that second is special because it's the last of
the year 2001 (assuming there's no leap second this year -
there was one at the end of 1998, when the last two
seconds of the year were 23:59:59 and 23:59:60) - but
that's not the reason. The reason for saying "23:59:59 PST,
December 31, 2001" is that it's well-defined (although
UTC would be more definite) in contrast to "midnight,
December 31, 2001" which in English ambiguously refers
to both the very start and very end of 31 Dec 2001.
Mike Oliver
> The rules may not be precisely correct; I haven't analyzed them
> in detail and don't know the reasons for all the choices that
> were made. In conception, though, the problem makes a lot
> of sense, and the reason that "return (unsigned)-1;" is not
> a solution is that you're supposed to interpret strings
> that, past some point on the left, consist entirely of 1's,
> *only* as negative numbers. There *is* no (unsigned)-1.
OK, I took a closer look at the rules and it seems that
this is not exactly true. There *is* an unsigned -1,
and it equals ...111111, and apparently the only distinction
between it and the signed -1 is that it compares greater
than any unsigned number whose leftward tail consists of 0's,
whereas if you were comparing signed ints, it would compare less.
However the rules say that you're supposed to return an int.
If you cast (unsigned)(-1) back to int so that you can
return it, you're just going to get -1 again. So that's
the answer to everyone who had this idea.
Ben Pfaff
> However the rules say that you're supposed to return an int.
> If you cast (unsigned)(-1) back to int so that you can
> return it, you're just going to get -1 again.
WTF are you talking about? That's not what will happen in C, and
if you're not talking about C, please talk about it somewhere
else.
In C, the value of (unsigned)-1 is INT_MAX. Casting it back to
int won't change that value.
--
"I ran it on my DeathStation 9000 and demons flew out of my nose." --Kaz
Nicolas Bray
On Tue, 11 Dec 2001, Dann Corbit wrote:
> > Come on, guys, then intent of the rules is clear. By rule 7 according
> > to any reasonable reading, there is no such thing as UINT_MAX or INT_MAX;
>
> Then it's not a C compiler.
Who said anything about a compiler? Or compiling? Or actually running any
programs?
> Why bother to specify a language at all?
How else could there be a contest?
> > an int is supposed to be able to contain a *mathematical* integer,
> > and there's no largest such. (There are infinite *quantities* in any
> > number of ways, but none of them is a largest integer.)
>
> Where are we going to store this thing? Nobody can actually write a program
> to accomplish such as thing as you propose.
Of course! Was this even a question?
> > The rules probably are not written perfectly; they should have explicitly
> > changed the standard to say that INT_MAX and UINT_MAX are banned and
> > that any attempt to assign or cast a negative value to an unsigned
> > results in an arithmetic exception, or some such. But the intent
> > is clear and the question is interesting;
>
> The intent is neither clear nor interesting.
The first paragraph of the post was:
The object of the BIGNUM BAKEOFF is to write a C program of 512 characters
or less (excluding whitespace) that returns as large a number as possible
from main(), assuming C to have integral types that can hold arbitrarily
large integers.
This seems perfectly clear to me. If you do not find the contest
interesting then you are certainly entitled to your opinion but enough
mathematicians and theoretical computer scientists disagree with you(in
that this is essentially the well-known busy beaver problem) that I think
you should consider that your opinion rather than objective fact.
> THIS MESSAGE IS OFF TOPIC IN news:comp.lang.c
David Moews no doubt imagined (apparently incorrectly) that some people in
comp.lang.c might find it interesting. I suppose it was slightly off-topic
but I hardly see that justifying poor behaviour such as yours.
> and TOPICAL in news:comp.programming.contests.
I'm not quite sure but I imagine that that newsgroup is intended for
programs which could actually be run.
> GO AWAY!
David Moews contributed a rather interesting(if slightly off-topic in
comp.lang.c) subject. You've contributed a lot of very childish
behaviour. I suggest you take your own advice.
Nick
Ben Pfaff
> On Tue, 11 Dec 2001, Dann Corbit wrote:
>
> > > Come on, guys, then intent of the rules is clear. By rule 7 according
> > > to any reasonable reading, there is no such thing as UINT_MAX or INT_MAX;
> >
> > Then it's not a C compiler.
>
> Who said anything about a compiler? Or compiling? Or actually running any
> programs?
We only discuss C programs in comp.lang.c. If you want to
discuss other things, please find some other place to do it.
Dann's question is perfectly reasonable. He's clearly getting
exasperated and thus being a little less polite than usual, but
that's understandable given the off-topic nature of the thread.
CBFalconer
David Moews wrote:
>
> I have received and accepted your entry. However, I point out that by
> rule 7, it returns -1, which is not an especially big number:
>
> unsigned int u;
>
> initializes u to 0, which has the representation
>
> ....0000000000000000000.
>
> --u;
>
> then changes the value of u to
>
> ....1111111111111111111.
>
> This is the 2s-complement representation of -1, so converting u back
> to an integer yields the value -1, which is what is returned from
> main().
The following two quotes are from the C99 standard:
[#9] The range of nonnegative values of a signed integer
type is a subrange of the corresponding unsigned integer
type, and the representation of the same value in each type
is the same.28) A computation involving unsigned operands
can never overflow, because a result that cannot be
represented by the resulting unsigned integer type is
reduced modulo the number that is one greater than the
largest value that can be represented by the resulting type.
and, later:
If an int can represent all values of the original type, the
value is converted to an int; otherwise, it is converted to
an unsigned int. These are called the integer
promotions.42) All other types are unchanged by the integer
promotions.
Any discussion of 2's complement representation is not germane,
the standard does not impose it. The 'as if' rule however, does
impose certain actions, including the above.
Fallacies are not due to the standard, but to the set of rules you
proposed.
If you really insist, we can return:
u--;
return (u >> 1);
which ensures a leading zero bit. The shift is always legal,
being performed on an unsigned quantity. The implicit conversion
to int must be possible in any conforming implementation.
if there remains any argument about the sizes, we can also
if ((int)u > (int)(u >> 1)) return u;
else return (u >> 1);
however this involves undefined behaviour in the (int) u
evaluation.
Since you published the original in c.l.c, and I posted my reply
there, I assume your permission to publish this correspondence
there unless I hear otherwise.
For reference, the following is from my original reply:
> The original is gone from here, but at any rate:
>
> unsigned int u; /* initialized to zero, see standard */
>
> int main(void)
> {
> u--; /* wraps to UINT_MAX, see standard */
> return u; /* unlimited, see rules */
> }
> NOTE: since int is unlimited, it must be able to express the value
> of UINT_MAX
>
Mike Oliver
> In C, the value of (unsigned)-1 is INT_MAX. Casting it back to
> int won't change that value.
Nope. It's UINT_MAX. Cast it back to int, and you get -1 again.
Ben Pfaff
> Ben Pfaff wrote:
>
> > In C, the value of (unsigned)-1 is INT_MAX. Casting it back to
> > int won't change that value.
>
> Nope. It's UINT_MAX.
Er, yes, what was I thinking. Sorry about that.
The conversion to unsigned adds UINT_MAX+1, so -1+UINT_MAX+1 is
UINT_MAX.
> Cast it back to int, and you get -1 again.
No, you either get an implementation-defined result or an
implementation-defined signal is raised.
From C99:
6.3.1.3 Signed and unsigned integers
When a value with integer type is converted to another
integer type other than _Bool, if the value can be
represented by the new type, it is unchanged.
Otherwise, if the new type is unsigned, the value is
converted by repeatedly adding or subtracting one more than
the maximum value that can be represented in the new type
until the value is in the range of the new type.49)
Otherwise, the new type is signed and the value cannot be
represented in it; either the result is
implementation-defined or an implementation-defined signal
is raised.
Mike Oliver
> Mike Oliver <oli...@math.ucla.edu> writes:
>> > Cast it back to int, and you get -1 again.
>
> No, you either get an implementation-defined result or an
> implementation-defined signal is raised.
Fine. Then the entry is invalid by rule 1(b).
Nicolas Bray
On 11 Dec 2001, Ben Pfaff wrote:
> Dann's question is perfectly reasonable. He's clearly getting
> exasperated and thus being a little less polite than usual, but
> that's understandable given the off-topic nature of the thread.
Dann's first post to the thread(which came an hour after the original
post) began with "I win. What an idiotic contest," and ended with "Now go
away.". He obviously exasperates easily.
Richard Bos
> To me, a mathematician, the language looks quite C-like indeed,
That is only because you, a mathematician, have no fscking clue about
how computation is done in the real world. Perhaps, if you wish to
inflict your silly notions of what computing should be like on people
who know how it is actually done, it would be a good idea to first
consider _why_ computing != mathematics?
> I think that's kind of interesting. You don't. Fine. Don't read the thread.
Wrong. It is _not about C_. Therefore, it is off-topic here. Now go
away.
Richard
Mike Oliver
>> I think that's kind of interesting. You don't. Fine. Don't read the thread.
>
> Wrong. It is _not about C_. Therefore, it is off-topic here. Now go
> away.
You know, I haven't been able to dig up a comp.lang.c charter (looked
in news.groups and didn't find it) but it seems unlikely to me that
the contest is clearly off-topic, unless the charter clearly excludes
either contests or physically-unrealizable models. It is clear that
detailed knowledge of C and its standard is key to making a competitive
entry, so there is at least some connection. It's not like people
who crosspost to sci.logic any argument that they think is "logical".
Also I took a look at comp.lang.c, and it's not as though the
thread is dominating discussion, not by any means. Moreover the
large majority of the posts are in subthreads generated by people
trying to prove that the contest is stupid or off-topic or both.
If those people could have restrained their net.fascist impulses a
little, the thread would have been a very small fraction of
today's traffic.
Nick Keighley
> Zoran Cutura wrote:
>
> > The returned number will simply be in the range of INT_MIN to
> > INT_MAX, even though the value you hoped to produce should be
> > way bigger than INT_MAX on a usual system.
>
> I think you missed rule 7.
since rule 7 states that int is infinitly large INT_MAX will be infinitly
large.
--
Nick Keighley
Chris Torek
[pretty much everything snipped here; but more later]
In article <3C1709AF...@yahoo.com>
CBFalconer <cbfal...@worldnet.att.net> wrote:
>Any discussion of 2's complement representation is not germane,
>the standard does not impose it.
I thought the original problem proposal required two's complement.
>If you really insist, we can return:
> u--;
> return (u >> 1);
>which ensures a leading zero bit. ...
Right.
>> so my entry is:
>> "unsigned int u;int main(void){return --u;}"
>> 123456789012345678901234567890123456789012
>> or 42 chars. We can probably elide " int" and the space before
>> --, for 37 chars. The only standard failing is that it returns a
>> value whose effects are undefined, but this is enforced by the
>> rules.
The "void" is unneeded, if you are willing to use the deprecated
form of the definition.
We can shorten this even more if we are allowed integral constants:
int main(){return~0U>>1;}
which is just 25 characters, plus a newline.
--
In-Real-Life: Chris Torek, Wind River Systems (BSD engineering)
El Cerrito, CA, USA Domain: to...@bsdi.com +1 510 234 3167
http://claw.eng.bsdi.com/torek/ (not always up) I report spam to abuse@.
"nos...@elf.eng.bsdi.com" *is* my address (one of many actually).
Richard Bos
> On Tue, 11 Dec 2001, Dann Corbit wrote:
>
> > > Come on, guys, then intent of the rules is clear. By rule 7 according
> > > to any reasonable reading, there is no such thing as UINT_MAX or INT_MAX;
> >
> > Then it's not a C compiler.
>
> Who said anything about a compiler? Or compiling? Or actually running any
> programs?
You miss the point. Whether there is a compiler or not is immaterial to
comp.lang.c; Dann's point is that it isn't C any more.
You state:
> The object of the BIGNUM BAKEOFF is to write a C program of 512 characters
^^^^^^^^^^^
If you're not allowed to use INT_MAX, it isn't C.
If you're not allowed to take (unsigned) -1, it isn't C.
If it isn't C, it isn't interesting to comp.lang.c. It may be an
interesting programming exercise, but it isn't an interesting C
programming exercise, because it is not C.
Richard
Richard Bos
> Richard Bos wrote:
> > Mike Oliver <oli...@math.ucla.edu> wrote:
> >> I think that's kind of interesting. You don't. Fine. Don't read the thread.
> >
> > Wrong. It is _not about C_. Therefore, it is off-topic here. Now go
> > away.
>
> You know, I haven't been able to dig up a comp.lang.c charter (looked
> in news.groups and didn't find it)
That shouldn't be surprising to anyone who knows c.l.c, because to all
intents and purposes it doesn't have one. And that means that topicality
here is determined by the consensus of the regulars. Now, as long as I
have been here, this consensus has been that on-topic on c.l.c are ISO
C, and, for historical reasons, K&R C. Not any random variety thereof -
not, in fact, POSIX or MSC or Turbo C, and certainly not a hamstrung,
impossible variety designed for no better reason than that a
badly-thought-out contest doesn't work without it.
> It is clear that detailed knowledge of C and its standard is key
> to making a competitive entry,
No, it isn't; detailed knowledge of C is misleading in your variety of
semi-C, as many c.l.c regulars have clearly demonstrated by applying it
and being told that they're not supposed to do so.
> Also I took a look at comp.lang.c, and it's not as though the
> thread is dominating discussion, not by any means.
Neither is spam. It's still off-topic.
Follow-ups set to a group where this _is_ on-topic.
Richard
Joona I Palaste
on comp.lang.c:
> Also I took a look at comp.lang.c, and it's not as though the
> thread is dominating discussion, not by any means. Moreover the
> large majority of the posts are in subthreads generated by people
> trying to prove that the contest is stupid or off-topic or both.
> If those people could have restrained their net.fascist impulses a
> little, the thread would have been a very small fraction of
> today's traffic.
I'm sick and tired of people who accuse anyone attempting to cling to
a shred of topicality of being a net.fascist. It amazes me to think that
there are real-life people who only know of two extremes: total anarchy
and net.fascism.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"Show me a good mouser and I'll show you a cat with bad breath."
- Garfield
pete
>
> int main(){return~0U>>1;}
>
> which is just 25 characters, plus a newline.
But if UINT_MAX == INT_MAX, as I've read that it may,
then you've only just returned (INT_MAX / 2).
--
pete
Tim Woodall
Mike Oliver <oli...@math.ucla.edu> wrote:
>Daniel Haude wrote:
>>
>> On Tue, 11 Dec 2001 06:57:40 +0000,
>> Richard Heathfield <bin...@eton.powernet.co.uk> wrote
>> in Msg. <3C15AE64...@eton.powernet.co.uk>
>> | #include <limits.h>
>> | int main(void)
>> | {
>> | return INT_MAX;
>> | }
>> |
>> | I suspect these are both maximally winning entries.
>>
>> They are, because they return infinity by definition (see rule 7).
>
>The intent of rule 7, as I read it, is that an integer variable is
>supposed to be able to hold a *mathematical* integer. Therefore
>there is no INT_MAX, and (unsigned)(-1)>>1 is simply -1 again.
>
>> And they prove the utter stupidity of the contest.
>
>Nonsense. The INT_MAX one might show that the specific details
>of the rules weren't thought through perfectly. (Even that
>I'm not sure about; maybe there's some little clause I missed
>that excludes it.
>
>But the idea of the contest is valid and interesting, and I'm curious
>to see how it comes out.
There is one possible way to retrieve the contest without changing the rules.
(NB. I am not a mathematician so I might have got the next bit wrong)
there is an ordering of infinities s.t.
inf + n = inf.
inf ** inf > inf.
inf ** inf ** inf > inf ** inf
so the optimium program is likely to be something along the lines of
int inf = (unsigned)-1;
int pow(int a) { return a ** inf; }; /* obviously ** isn't C */
int main(void) { return pow(pow(pow(pow ... (pow(inf)) ... ))); }
HTH.
HAND.
Tim.
--
God said, "div D = rho, div B = 0, curl E = - @B/@t, curl H = J + @D/@t,"
and there was light.
http://locofungus.2y.net/ http://www.locofungus.btinternet.co.uk/
Tim Woodall
with INT_MAX/2.
Tim
pete
I just emailed my entry.
/* BEGIN intmax.c */
int main(void)
{
int intmax = 1;
do{
intmax <<= 1;
}while(intmax < intmax << 1);
intmax += intmax - 1;
return intmax;
}
/* END intmax.c */
--
pete
Dave Seaman
James Waldby <j-wa...@pat7.com> wrote:
>- Kees van der Bent - wrote:
>> David Moews wrote:
>> > Rules in brief
>> > 6. Entries must be e-mailed to dmo...@xraysgi.ims.uconn.edu and received
>> > before 23:59:59 PST, December 31, 2001.
>> What's so special about 23:59:59 PST, December 31, 2001 (wrt 23:59:58
>> for example) that I not allowed to submit my winning entry in this
>> second?
>Of course that second is special because it's the last of
>the year 2001 (assuming there's no leap second this year -
>there was one at the end of 1998, when the last two
>seconds of the year were 23:59:59 and 23:59:60) - but
>that's not the reason. The reason for saying "23:59:59 PST,
>December 31, 2001" is that it's well-defined (although
>UTC would be more definite) in contrast to "midnight,
>December 31, 2001" which in English ambiguously refers
>to both the very start and very end of 31 Dec 2001.
You could say "24:00:00 PST, December 31, 2001", which is well-defined
and unambiguous. The very beginning of 31 Dec would be "0:00:00 PST,
December 31, 2001".
--
Dave Seaman dse...@purdue.edu
Amnesty International calls for new trial for Mumia Abu-Jamal
<http://www.amnestyusa.org/abolish/reports/mumia/>
Dave Seaman
Richard Bos <in...@hoekstra-uitgeverij.nl> wrote:
>Nicolas Bray <br...@soda.csua.berkeley.edu> wrote:
>> On Tue, 11 Dec 2001, Dann Corbit wrote:
>> > > Come on, guys, then intent of the rules is clear. By rule 7 according
>> > > to any reasonable reading, there is no such thing as UINT_MAX or INT_MAX;
>> > Then it's not a C compiler.
>> Who said anything about a compiler? Or compiling? Or actually running any
>> programs?
>You miss the point. Whether there is a compiler or not is immaterial to
>comp.lang.c; Dann's point is that it isn't C any more.
>You state:
>> The object of the BIGNUM BAKEOFF is to write a C program of 512 characters
> ^^^^^^^^^^^
>If you're not allowed to use INT_MAX, it isn't C.
>If you're not allowed to take (unsigned) -1, it isn't C.
Nonsense. The classic "hello world" program does not use INT_MAX and
does not take (unsigned) -1. Does that mean the "hello world" program is
not C?
It's not necessary to assume that INT_MAX and (unsigned) -1 are not part
of the language we are using. It is only necessary to specify that
programs relevant to this contest will not use those features of the
language.
pete
> You could say "24:00:00 PST, December 31, 2001", which is well-defined
> and unambiguous.
Is that the same thing as "00:00:00 PST, January 01, 2002" ?
--
pete
CBFalconer
>
> On Wed, 12 Dec 2001 07:22:43 -0500,
> pete <pfi...@mindspring.com> wrote:
> >Chris Torek wrote:
> >>
> >> int main(){return~0U>>1;}
> >>
> >> which is just 25 characters, plus a newline.
> >
> >But if UINT_MAX == INT_MAX, as I've read that it may,
> >then you've only just returned (INT_MAX / 2).
> >
> They are the same as you can place INT_MAX in a one to one correspondance
> with INT_MAX/2.
Now there is an answer in the spirit of Dedekind. <g> Don't you
mean the set 0..INT_MAX is isomorphic to 0..INT_MAX/2? For each i
in 0..INT_MAX I can find ....
Rob Sykes
news:3C175D...@mindspring.com:
> Dave Seaman wrote:
>
>> You could say "24:00:00 PST, December 31, 2001", which is
>> well-defined and unambiguous.
This system would, however, allow the next second to be written as
"24:00:01 PST, December 31, 2001". So we would have the 1st second
of the New Year occurring on 2 different days ("00:00:01 PST,
January 1, 2002")
>
> Is that the same thing as "00:00:00 PST, January 01, 2002" ?
>
See above - I think officially 24:00:00 does not exist. 23:59:59 is
followed by 00:00:00 (except for pesky leap seconds of course).
This is (UK) military and railway timetable practice.
--
Rob Sykes
Born again Bairn
'The despair I can live with. It's the hope I can't stand' (Anon.)
Dave Seaman
Yes. (After a brief consideration of, and rejection of, leap seconds as
a possible relevant factor.)
Richard Bos
> In article <3c171ddd...@news.tiscali.nl>,
> Richard Bos <in...@hoekstra-uitgeverij.nl> wrote:
> >If you're not allowed to use INT_MAX, it isn't C.
> >If you're not allowed to take (unsigned) -1, it isn't C.
>
> Nonsense. The classic "hello world" program does not use INT_MAX and
> does not take (unsigned) -1. Does that mean the "hello world" program is
> not C?
Read for comprehension, not for flame fodder, good man. I wrote "not
_allowed_ to use INT_MAX". It really does take a mathematician to
confuse "not allowed to" with "not required to".
Again: in the language we discuss in comp.lang.c, you _are_ allowed to
use INT_MAX. There is a good reason for this. If you wish to postulate
another language, in which you cannot use some of the more fundamental
properties of C, feel free to do so, but do so on your own group.
After all, I don't post a mathematical puzzle to sci.math, and then,
when people point out the flaws in it, start claiming that to solve it
multiplication and the number 4 are out of bounds, do I?
> It's not necessary to assume that INT_MAX and (unsigned) -1 are not part
> of the language we are using. It is only necessary to specify that
> programs relevant to this contest will not use those features of the
> language.
Doesn't matter. You're still using a crippled, uninteresting version of
C, which is still off-topic on comp.lang.c.
If you're really so interested in the puzzle instead of in showing your
ignorance of C programming, why don't you just specify a limited number
of mathematical symbols instead, and keep it where it belongs?
Richard
pete
7.(a)
All integral types T (char, signed char, unsigned char,
short int, unsigned short int, int, unsigned int,
long int, and unsigned long int) satisfy sizeof(T) == 1.
7.(e)
For the purposes of section 6.2.1.5 of the standard,
a long int cannot represent all values of an unsigned int.
After rereading the rules, I guess you're OK.
--
pete
CBFalconer
Shifts on ints can run into undefined behavior, especially at
overflow time. If ints can be any size, (not really possible, but
part of the preconditions) this never terminates.
pete
>
> In article <3C175D...@mindspring.com>,
> pete <pfi...@mindspring.com> wrote:
> >Dave Seaman wrote:
>
> >> You could say "24:00:00 PST, December 31, 2001",
> >> which is well-defined
> >> and unambiguous.
What year would that be?
>
> >Is that the same thing as "00:00:00 PST, January 01, 2002" ?
>
> Yes. (After a brief consideration of, and rejection of,
> leap seconds as
> a possible relevant factor.)
What year would that be?
--
pete
Dave Seaman
Rob Sykes <NOro...@john-richard.co.uk> wrote:
>pete <pfi...@mindspring.com> wrote in
>news:3C175D...@mindspring.com:
>> Dave Seaman wrote:
>>> You could say "24:00:00 PST, December 31, 2001", which is
>>> well-defined and unambiguous.
>This system would, however, allow the next second to be written as
>"24:00:01 PST, December 31, 2001". So we would have the 1st second
>of the New Year occurring on 2 different days ("00:00:01 PST,
>January 1, 2002")
That notation is not valid, any more than "December 32, 2001" is valid.
It doesn't mean there is anything wrong with "24:00:00", any more than
there is anything wrong with "December 31".
Dave Seaman
>> In article <3C175D...@mindspring.com>,
>> pete <pfi...@mindspring.com> wrote:
>> >Dave Seaman wrote:
>> >> You could say "24:00:00 PST, December 31, 2001",
>> >> which is well-defined
>> >> and unambiguous.
>What year would that be?
2001, like it says.
>> >Is that the same thing as "00:00:00 PST, January 01, 2002" ?
>> Yes. (After a brief consideration of, and rejection of,
>> leap seconds as
>> a possible relevant factor.)
>What year would that be?
2002, like it says.
There is no contradiction. Is 2 a member of the closed interval [1,2],
or is it a member of the closed interval [2,3]?
Answer: Yes.
pete
>
> pete wrote:
> >
> > pete wrote:
> > >
> > > Chris Torek wrote:
> > > >
> > > > int main(){return~0U>>1;}
> > > >
> > > > which is just 25 characters, plus a newline.
> > >
> > > But if UINT_MAX == INT_MAX, as I've read that it may,
> > > then you've only just returned (INT_MAX / 2).
> >
> > I just emailed my entry.
> >
> > /* BEGIN intmax.c */
> >
> > int main(void)
> > {
> > int intmax = 1;
> >
> > do{
> > intmax <<= 1;
> > }while(intmax < intmax << 1);
> > intmax += intmax - 1;
> > return intmax;
> > }
> >
> > /* END intmax.c */
>
> Shifts on ints can run into undefined behavior, especially at
> overflow time.
But the rules stated two's compliment, and also the answer with
the greatest magnitude, so I think they might be looking for
the two's compliment limit of INT_MIN, instead of INT_MAX.
My revised entry:
/* BEGIN intmin.c */
int main(void)
{
int intmin = 0x4000;
while(intmin < intmin << 1)
intmin <<= 1;
return intmin << 1;
}
/* END intmin.c */
> If ints can be any size, (not really possible, but
> part of the preconditions) this never terminates.
I interpreted all that stuff as being a non-c.l.c way
of saying that it would be run on a Death Station 9000.
Assuming that this might be a two's compliment system
where (INT_MIN != -INT_MAX - 1),
I'll try to come up with something else.
--
pete
Tim Woodall
int p(int x){return 1<<x;}int main(void){return p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(
p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(
p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(
p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(
p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(~0U)))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))));}
And here is the program I used to generate it.
[tim@twlinux test]$ cat main.c
#include <stdio.h>
#include <string.h>
char s[1024]="~0U";
char t[1024];
char r[1024];
int main(void)
{
int a=0;
while(strlen(t)<=512)
{
a++;
strcpy(r,t);
sprintf(t,"p(%s)",s);
strcpy(s,t);
sprintf(t,"int p(int x){return 1<<x;}int main(void){return p(%s);}",s);
}
printf("%s",r);
fprintf(stderr,"%d %d\n",strlen(r),a);
return 0;
}
You can probably do better with a program like:
int a(int x){return 1<<x;}int b(int x){return a(a(a(a(a(a(a(x))))))));}
int main(void){return b(b(b(b(b(b....b(~0U))))))...));}
Regards,
pete
>
> In article <Xns91758DE5DBBBr...@192.168.0.253>,
> Rob Sykes <NOro...@john-richard.co.uk> wrote:
> >pete <pfi...@mindspring.com> wrote in
> >news:3C175D...@mindspring.com:
>
> >> Dave Seaman wrote:
>
> >>> You could say "24:00:00 PST, December 31, 2001", which is
> >>> well-defined and unambiguous.
>
> >This system would, however, allow the next second to be written as
> >"24:00:01 PST, December 31, 2001". So we would have the 1st second
> >of the New Year occurring on 2 different days ("00:00:01 PST,
> >January 1, 2002")
>
> That notation is not valid, any more than "December 32, 2001"
> is valid.
> It doesn't mean there is anything wrong with "24:00:00", any more than
> there is anything wrong with "December 31".
Yes it does.
There are 31 days in December.
1 is the first, and 31 is the thirtyfirst.
There are 24 hours in a day.
12 am is the first hour
11 pm is the twentyfourth
There's no more hours left on that day.
The next hour is 12 am the next day.
There are 24 hours in a day.
00 is the first hour
23 is the twentyfourth
There's no more hours left on that day.
The next hour is 00 the next day.
--
pete
pete
>
> In article <3C175D...@mindspring.com>,
> pete <pfi...@mindspring.com> wrote:
> >Dave Seaman wrote:
> >> well-defined and unambiguous.
I challenge that claim.
> >?
> After a brief consideration of, and rejection of,
That's all the proof I need.
--
pete
Tim Woodall
Tim Woodall <t...@pauli.locofungus.org> wrote:
>I _think_ the following program calculates aleph-152.
>
>int p(int x){return 1<<x;}int main(void){return p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(
>p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(
>p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(
>p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(
>p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(~0U)))))))))))))))))))))))))))))))))
>))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
>))))))))))))))))))))))))))))))))))))))))));}
>
Why do I always think of the hardest way to do things :-)
int p(int x){return 1<<x;}int main(void){int i,c=~0U;if(c<0)c=~0U>>1;for(i=0;
i<p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p
(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(
p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p
(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(9)))))))))))))))))))))))))))))))))
)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))));i++)c=p(c);return c;}
Obviously calculates aleph-(enormous) by the same manner and the program
obviously terminates. Also compiles with gcc -Wall without any warnings
and handles the what is (int)~0U :-)
Joona I Palaste
on comp.lang.c:
> Why do I always think of the hardest way to do things :-)
> int p(int x){return 1<<x;}int main(void){int i,c=~0U;if(c<0)c=~0U>>1;for(i=0;
> i<p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p
> (p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(
> p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p
> (p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(9)))))))))))))))))))))))))))))))))
> )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
> ))))))))))))))))))))))))));i++)c=p(c);return c;}
> Obviously calculates aleph-(enormous) by the same manner and the program
> obviously terminates. Also compiles with gcc -Wall without any warnings
> and handles the what is (int)~0U :-)
${DEITY}, that's one mighty big number. I suppose that if we were to
write that number in base-googolplex, using one hydrogen atom as each
digit, there wouldn't be enough matter in the known Universe to display
the result.
Richard Bos
> But the rules stated two's compliment,
Two's compliment? Is that something like "Hey, you're looking very three
tonight!"?
Richard, g,d,r
Joona I Palaste
on comp.lang.c:
> Tim Woodall <t...@pauli.locofungus.org> scribbled the following
> on comp.lang.c:
>> Why do I always think of the hardest way to do things :-)
>> int p(int x){return 1<<x;}int main(void){int i,c=~0U;if(c<0)c=~0U>>1;for(i=0;
>> i<p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p
>> (p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(
>> p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p
>> (p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(9)))))))))))))))))))))))))))))))))
>> )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
>> ))))))))))))))))))))))))));i++)c=p(c);return c;}
>> Obviously calculates aleph-(enormous) by the same manner and the program
>> obviously terminates. Also compiles with gcc -Wall without any warnings
>> and handles the what is (int)~0U :-)
> ${DEITY}, that's one mighty big number. I suppose that if we were to
> write that number in base-googolplex, using one hydrogen atom as each
> digit, there wouldn't be enough matter in the known Universe to display
> the result.
Actually, come to think of it, (10**(10**100))**n, where n is the
number of hydrogen atoms in the known Universe, is also quite a big
number. Any theoretical mathematics buffs here? Which is bigger, Tim's
number or mine?
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"To doo bee doo bee doo."
- Frank Sinatra
hack
Dave Seaman <dse...@seaman.cc.purdue.edu> wrote:
>
>I think the question was, why are entries accepted at 1.001 seconds
>before midnight, but not at 0.999 seconds before midnight?
Perhaps because people used to the am/pm system would not understand the
notion of 24:00:00 (midnight ending a given date, as opposed to 00:00:00
which denotes the midnight preceding a given date). This is also why US
insurance policies tend to expire at 12:01am. The 12-hour am/pm system
has no unambiguous denotation for midnight (and its unambiguous denotation
for noon, namely 12:00noon, is rarely used: 12:00pm is used by convention
instead even though it's literally nonsense).
Michel.
pete
It's when a pair of eighteen year olds are dressed to the nines.
--
pete
Rob Sykes
news:9v7tci$5...@seaman.cc.purdue.edu:
> In article <Xns91758DE5DBBBr...@192.168.0.253>,
> Rob Sykes <NOro...@john-richard.co.uk> wrote:
>>pete <pfi...@mindspring.com> wrote in
>>news:3C175D...@mindspring.com:
>
>>> Dave Seaman wrote:
>
>>>> You could say "24:00:00 PST, December 31, 2001", which is
>>>> well-defined and unambiguous.
>
>>This system would, however, allow the next second to be written
>>as "24:00:01 PST, December 31, 2001". So we would have the 1st
>>second of the New Year occurring on 2 different days ("00:00:01
>>PST, January 1, 2002")
>
> That notation is not valid, any more than "December 32, 2001"
> is valid. It doesn't mean there is anything wrong with
> "24:00:00", any more than there is anything wrong with
> "December 31".
>
Ok, you could say that a:x:y is valid when
00 <= a <= 23, 00 <= x,y <= 59
and
a = 24, x = y = 00
The last term is an obvious excrescence and it still allows
you to express a single date/time in two ways. It's not
needed.
Chances are there's a standard somewhere which defines which
day any given midnight 'belongs to'. That'll help :-)
Rob Sykes
news:Xns9175AC0953C6Cr...@192.168.0.253:
> dse...@seaman.cc.purdue.edu (Dave Seaman) wrote in
> news:9v7tci$5...@seaman.cc.purdue.edu:
>
>> In article <Xns91758DE5DBBBr...@192.168.0.253>,
>> Rob Sykes <NOro...@john-richard.co.uk> wrote:
>>>pete <pfi...@mindspring.com> wrote in
>>>news:3C175D...@mindspring.com:
>>
>>>> Dave Seaman wrote:
>>
>>>>> You could say "24:00:00 PST, December 31, 2001", which is
>>>>> well-defined and unambiguous.
>>
>>>This system would, however, allow the next second to be written
>>>as "24:00:01 PST, December 31, 2001". So we would have the 1st
>>>second of the New Year occurring on 2 different days ("00:00:01
>>>PST, January 1, 2002")
>>
>> That notation is not valid, any more than "December 32, 2001"
>> is valid. It doesn't mean there is anything wrong with
>> "24:00:00", any more than there is anything wrong with
>> "December 31".
>>
>
> Chances are there's a standard somewhere which defines which
> day any given midnight 'belongs to'. That'll help :-)
>
All the references I've just checked up (summaries of ANSI X3.30)
allow both 00:00:00 and 24:00:00 to express the two midnights
connected to each day.
"As every day both starts and ends with midnight, the two notations
00:00 and 24:00 are available to distinguish the two midnights that
can be associated with one date. This means that the following two
notations refer to exactly the same point in time:
1995-02-04 24:00 = 1995-02-05 00:00"
In case an unambiguous representation of time is required, 00:00 is
usually the preferred notation for midnight and not 24:00. Digital
clocks display 00:00 and not 24:00."
http://www.cl.cam.ac.uk/~mgk25/iso-time.html
I'm b*gg*r*d. I thought 24:00 and gone the way of the dodo.