Produce the most digits of an irrational number with only 64 KB of memory

Question

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 (2¹⁶ = 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.

Answer 1

Python - 10^10157831 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, 2⁵²⁴²⁸⁸! is about 10^10157831.

Answer 2

Python - 10¹⁵⁷⁸³¹ 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 = 10¹⁰⁰⁰⁰, 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 10¹⁰⁰ digits (let alone 10¹⁰⁰⁰⁰), due to there only being about 10⁸⁰ particles in the observable universe and only about 10²¹ 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... × 10¹⁵⁷⁸³¹, assuming we can get all the way to 2⁵²⁴²⁸⁸ - 1 without running into memory issues with the bignum storage.

Answer 3

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

Answer 4

PEP/8 - 1.29 * 10¹²⁹⁰⁴⁹ ≈ 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.

Answer 5

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.