4
\$\begingroup\$

Constraints:

  1. Calculate any notable irrational number such as pi, e, or sqrt(2) to as many decimal digits as possible. If using a number not mentioned in the list above, you must cite how and where this number is used.

  2. The memory used to store data in variables that the program reads from at any time in its computation may not exceed 64 kilobytes (216 = 65 536 bytes). However, the program may output as much data as it likes, provided it does not re-read the outputted data. (Said re-reading would count toward the 64 KB limit.)

  3. The maximum size for code (either source or object code can be measured) is also 64 kilobytes. Smaller code is allowed, but does not provide more memory for computation or a better score.

  4. The program must not accept any input.

  5. Any format for output is allowed, as long as the digits are represented in decimal. Only the fractional portion of the number will be taken into account, so both 3.14159... and 14159... are both equivalent answers, the latter one being represented as "the fractional part of pi".

  6. The number of decimal digits past the decimal point that your program outputs is your score. Highest score wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ Mathematica 17684 ascii digits MemoryConstrained[N[Pi, 17684], 2^16], not very clever, just a baseline \$\endgroup\$ – Dr. belisarius Nov 26 '13 at 3:46
  • \$\begingroup\$ I meant to warn against library functions for calculating the number, but forgot. i.e. when calculating sqrt(2) all library functions except sqrt are allowed. \$\endgroup\$ – hildred Nov 26 '13 at 3:59
  • \$\begingroup\$ Well, that stupid one doesn't use any library function. In fact, it doesn't use any function except for chopping the result. Not all languages are created equal. \$\endgroup\$ – Dr. belisarius Nov 26 '13 at 4:04
  • \$\begingroup\$ Do you mean that maximum internal RAM usage is 2^16 bytes, or do you mean maximum memory usage total, of any type? Because if you meant the latter, an upper bound already exists that you can't get any finer than about 19728 digits because the output buffer alone will take that much memory. \$\endgroup\$ – Joe Z. Nov 26 '13 at 4:49
  • 1
    \$\begingroup\$ mostly the former, in that your output does not count against your memory usage, but it can not be read back in during the main program. \$\endgroup\$ – hildred Nov 26 '13 at 4:53
7
\$\begingroup\$

Python - 1010157831 digits

This solution depends on a bending of the rules that doesn't count function return output as "used memory".

import sys

def trunc_factstring(n):
    return (factstring(n-1) * (n-1))[:-1] + "1"

def factstring(n):
    return "0" if n == 0 else factstring(n-1) * n

sys.stdout.write("0.")
a = 0
while True:
    a += 1
    sys.stdout.write(trunc_factstring(a))

Prints 0.1100010000000000000000010000..., the Liouville constant, until the program runs out of memory.

At any number a = n, the number of decimal places outputted is n!. Unlike my last solution, this one would run out of total memory before a reached even 100.

According to Wolfram Alpha, 2524288! is about 1010157831.

\$\endgroup\$
  • \$\begingroup\$ Kudos to @Cruncher for reminding me to do this. :P \$\endgroup\$ – Joe Z. Nov 27 '13 at 22:25
  • \$\begingroup\$ As This challenge was Inspired by an account I read about Involving calculating Pi on an early computer where there was an improvement to the alogarithm where he switched from using two variables that were half the size of memory to one that could use all (or almost all) the memory, you are hereby fined 75% memory, but you are still in the lead. Congratulations. \$\endgroup\$ – hildred Nov 27 '13 at 22:39
  • \$\begingroup\$ Due to the way factorials work, you can just divide the top exponent by 4 to get the number of digits you can print out with one quarter of the available memory. \$\endgroup\$ – Joe Z. Nov 28 '13 at 1:30
  • \$\begingroup\$ @Cruncher I said memory, not score which has a more significant impact. \$\endgroup\$ – hildred Nov 28 '13 at 15:53
  • 1
    \$\begingroup\$ In terms of how this analogizes to the early computer, imagine the computer printing out numbers on a tape, and you using a tape copier to copy the printed output rather than making the computer print out more things. \$\endgroup\$ – Joe Z. Dec 2 '13 at 21:57
8
\$\begingroup\$

Python - 10157831 digits

import sys

sys.stdout.write("0.")
a = 0
while True:
    a += 1
    sys.stdout.write(str(a))

Prints 0.1234567891011121314151617181920..., which is the Champernowne constant in base 10, until the program runs out of memory.

When the program's counter a reaches a specific number x, it has printed out at least x digits (as every number has at least one digit), and more on the order of x log x digits. For x = 1010000, the binary data required to represent a would be about 4.1 kilobytes, which is well below the allotted limit.

Interesting to note - any computer running this program would run out of total memory long before it ever printed off even 10100 digits (let alone 1010000), due to there only being about 1080 particles in the observable universe and only about 1021 bytes of memory available for storage on all of Earth's data computing devices.

Wolfram Alpha says that the total number of digits printed is actually about 4.09776347957... × 10157831, assuming we can get all the way to 2524288 - 1 without running into memory issues with the bignum storage.

\$\endgroup\$
  • \$\begingroup\$ what happens when a wraps around? does it go negative or throw an exception? \$\endgroup\$ – hildred Nov 26 '13 at 6:29
  • \$\begingroup\$ Python integers go on forever. \$\endgroup\$ – Joe Z. Nov 26 '13 at 6:41
  • \$\begingroup\$ If you don't believe me, try running print 2 ** 524288 - 1 in a Python shell, which is the largest number that can be represented raw in 64 KB of memory. \$\endgroup\$ – Joe Z. Nov 26 '13 at 6:45
  • \$\begingroup\$ @JoeZ. If you want even more output use the binary representation. \$\endgroup\$ – Howard Nov 26 '13 at 11:03
  • \$\begingroup\$ The problem specified decimal, I believe. \$\endgroup\$ – Joe Z. Nov 26 '13 at 11:05
4
\$\begingroup\$

Python, infinitely many digits.

This computes a decimal expansion of the surreal number ε*x where x is the Champernowne constant.

from sys import stdout

stdout.write('0.')
while 1:
    stdout.write('0')
a = 0
stdout.write('.')
while 1:
    a += 1
    stdout.write(`a`)

also...

Sage, 0 digits

The bad news is that Sage's memory footprint is significantly larger than 64k. The good news is that I have a provably optimal solution.

#this is a comment
\$\endgroup\$
  • \$\begingroup\$ By the time the computer runs out of memory, it'll only have printed a decimal equivalent to 0. \$\endgroup\$ – Joe Z. Nov 28 '13 at 20:28
  • 1
    \$\begingroup\$ @JoeZ. not so! it'll print infinitely many zeros before it starts consuming memory. After that, it prints out about 10^157831 characters of Champernowne. (also... this is a joke) \$\endgroup\$ – boothby Nov 28 '13 at 21:27
  • \$\begingroup\$ I meant by the time the computer runs out of total memory, not just memory that counts toward the 64 KB limit. :P \$\endgroup\$ – Joe Z. Nov 28 '13 at 21:45
  • \$\begingroup\$ (And yeah, eventually I realized. :S) \$\endgroup\$ – Joe Z. Nov 28 '13 at 21:46
  • \$\begingroup\$ Nice problem abuse. \$\endgroup\$ – AJMansfield Nov 28 '13 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.