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.
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:
(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
> 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).
> 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.
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
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 :(
Mark Duell wrote: > 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 wrote: > 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.
> 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?
> 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.
> 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:
> (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.
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: -------
> 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 */
> 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.
> 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.
> > 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.
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.
> 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.
> 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)
-- Ioannis http://users.forthnet.gr/ath/jgal/ _______________________________________ "The best way to predict reality, is to know exactly what you _don't_ want."
> > 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.
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.
> 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 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.
> "David Moews" <dmo...@xraysgi.ims.uconn.edu> wrote in message > news:9v403c$o3u$1@lydian.ccrwest.org... >> 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.
> 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 > }
> 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 :(
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.Cut...@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
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.
On 10 Dec 2001 19:55:24 -0800, 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?
>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.
>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:
> (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.
-- God said, "div D = rho, div B = 0, curl E = - @B/@t, curl H = J + @D/@t," and there was light.
> 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
-- Ioannis http://users.forthnet.gr/ath/jgal/ _______________________________________ "The best way to predict reality, is to know exactly what you _don't_ want."
> > > 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?
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.
On Tue, 11 Dec 2001 06:57:40 +0000, Richard Heathfield <bin...@eton.powernet.co.uk> wrote in Msg. <3C15AE64.370C9...@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"
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; > }
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.
> > > "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?
> 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.
No need. The rules as originally posted *specifically* allow and indeed mandate this assumption of two's complement integer representation.
