5
\$\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\$
6
  • 2
    \$\begingroup\$ Mathematica 17684 ascii digits MemoryConstrained[N[Pi, 17684], 2^16], not very clever, just a baseline \$\endgroup\$ Nov 26, 2013 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, 2013 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\$ Nov 26, 2013 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, 2013 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, 2013 at 4:53

5 Answers 5

9
\$\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\$
5
  • \$\begingroup\$ Kudos to @Cruncher for reminding me to do this. :P \$\endgroup\$
    – Joe Z.
    Nov 27, 2013 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, 2013 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, 2013 at 1:30
  • \$\begingroup\$ @Cruncher I said memory, not score which has a more significant impact. \$\endgroup\$
    – hildred
    Nov 28, 2013 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, 2013 at 21:57
9
\$\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\$
8
  • \$\begingroup\$ what happens when a wraps around? does it go negative or throw an exception? \$\endgroup\$
    – hildred
    Nov 26, 2013 at 6:29
  • \$\begingroup\$ Python integers go on forever. \$\endgroup\$
    – Joe Z.
    Nov 26, 2013 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, 2013 at 6:45
  • \$\begingroup\$ @JoeZ. If you want even more output use the binary representation. \$\endgroup\$
    – Howard
    Nov 26, 2013 at 11:03
  • \$\begingroup\$ The problem specified decimal, I believe. \$\endgroup\$
    – Joe Z.
    Nov 26, 2013 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\$
5
  • 1
    \$\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, 2013 at 20:28
  • 2
    \$\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, 2013 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, 2013 at 21:45
  • \$\begingroup\$ (And yeah, eventually I realized. :S) \$\endgroup\$
    – Joe Z.
    Nov 28, 2013 at 21:46
  • \$\begingroup\$ Nice problem abuse. \$\endgroup\$ Nov 28, 2013 at 22:11
3
\$\begingroup\$

PEP/8 - 1.29 * 10129049 ≈ 10↑↑2.71 digits

; BIGINT IS A LITTLE ENDIAN ~~BINARY CODED DECIMAL~~ BASE 10,000 NUMBER (1 WORD -> 0-10K)
; INDEX and INTLEN are ptr's, so INDEX++; needs to increse INDEX by 2

INC:      ANDX 0, I        ; INDEX = 0;
INCLOOP:  LDA BIGNUM, X    ; ...
          ADDA 1, I        ; ...
          STA BIGNUM, X    ; BIGNUM[INDEX]++;
          CPA 10, I        ; if (BIGNUM[INDEX] != 10){
          BRNE PRINT       ;     goto PRINT;
          ANDA 0, I        ; ...
          STA BIGNUM, X    ; BIGNUM[INDEX] = 0;
          CPX INTLEN, D    ; ...
          BRNE NOADLEN     ; if (INDEX == INTLEN){
          LDA INTLEN, D    ;     ...
          ADDA 2, I        ;     ...
          STA INTLEN, D    ;     INTLEN++;}
NOADLEN:  ADDX 2, I        ; INDEX++;
          BR INCLOOP       ; goto INC;

PRINT:    LDX INTLEN, D    ; INDEX = INTLEN;
          ADDX 2, I        ; INDEX++;
PRINLOOP: SUBX 2, I        ; INDEX--;
          DECO BIGNUM, X   ; print("%d", BIGNUM[INDEX]);
          CPX 0, I         ; if (INDEX != 0)
          BRNE PRINLOOP   ;     goto PRINLOOP;

          BR INC         ; goto INC

          ;LDA INTLEN, D    ; ...
          ;CPA 32, I        ; if (INTLEN < 32)
          ;BRLT INC         ;     goto INC
          ;STOP             ; STOP

INTLEN:  .WORD 0
BIGNUM:  .BLOCK 0x0010 ; BASICALLY THE REST OF RAM,
                       ; BUT THE COMPILER DOES NOT LIKE BIG NUMBERS
.END

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

PEP/8 is an interesting language, not just to say that I don't think it's ever been used on codegolf before. It's an assembly language used for teaching students the basics. It contains only low-level word operation, lacking even multiplication. I implemented a big num, containing only print and increment functionality, and let it feed on all of RAM. Pep8 limits itself to 64K, for all of it's code, heap, stack, and 'OS'. I can fit up to 10K in a single Word without having to do any conversion to base 10. Addresses past 0XFC50 (in the OS section) are not writeable, though this seems to be undocumented behavior.

For the number of digits, there are 9 1-length digits, 90 2-length, 900 3-length, meaning if you output digits of up to length N, you output is approx (10^N)/9 + N(10^N) digits total.

\$\endgroup\$
1
\$\begingroup\$

Mathematica - 1,139,793 digits

MemoryConstrained[x=0;While[True,WriteString[$Output, ++x]],2^16]

Prints the Champernowne constant, until the program reaches 64K of memory usage. Instead of any theory, I just ran it, and piped it to a file.

Mathematica has some quirks, the first I noticed is that I could not verify Dr. belisarius's 17684 digit output. So I'll assume that Mathematica has some sort of system-dependence. The other quirk I noticed is that byte sizes take large steps.

MaxMemoryUsed[N[Sqrt[2], 17118]]

Takes 7600 bytes, and

MaxMemoryUsed[N[Sqrt[2], 17119]]

Takes 66696 bytes.

\$\endgroup\$

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.