| abstract | - pete-3.c is one of the nine entries an anonymous "Pete" submitted to Bignum Bakeoff, and the smallest entry that produces a large number. It uses the left shift operator <<, which in the fictional Bignum Bakeoff machine may be defined as \(a \ll b = a \cdot 2^b\) for nonnegative \(a\) and \(b\). (Its behavior is more complex in standard C implementations.) Presumably to save space, Pete did not use parentheses. Unfortunately, << is left-associative, and \(a \ll b\) grows much faster relative to \(b\) than to \(a\). So the returned value becomes \(9 \cdot (2^9)^{163} \cdot 2^{99} \approx 2.33 \cdot 10^{472}\), between a centillion and googolding. A large amount of space is therefore wasted on a number smaller than 1 << 1600. If the operator was instead right-to-left associative, the output would grow at a roughly tetrational rate with respect to the number of 9's. The full decimal expansion of this number is 23292479355228506120629103772205782521188556601365594768126262808438806540095385289219152367764951472483434579932913443405761122010738810864711712947727372583238365228030815708368105772248573097826643896491485324536255232791227961592036609194479127526553544504755505641588760449935355381277623598581929299236167791999017226178068796899131268137948410262725752057313568787813656536514657337239890061615130555787285358522635888992125632724527232536411274866890787299237298176.
|
