Article 419797 of sci.math: Path: ccrwest.org!not-for-mail From: dmoews@xraysgi.ims.uconn.edu (David Moews) Newsgroups: sci.math,comp.lang.c Subject: Contest: C BIGNUM BAKEOFF Date: 10 Dec 2001 19:55:24 -0800 Organization: University of Connecticut IMS Lines: 120 Message-ID: <9v403c$o3u$1@lydian.ccrwest.org> NNTP-Posting-Host: lydian.ccrwest.org X-Trace: lydian.ccrwest.org 1008042924 24703 192.203.205.93 (11 Dec 2001 03:55:24 GMT) X-Complaints-To: usenet@ccrwest.org NNTP-Posting-Date: 11 Dec 2001 03:55:24 GMT Xref: ccrwest.org sci.math:419797 comp.lang.c:434668 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 dmoews@xraysgi.ims.uconn.edu by Dec 31. Sample entry ------ ----- To: dmoews@xraysgi.ims.uconn.edu From: john@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 dmoews@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 dmoews@xraysgi.ims.uconn.edu