Talk:NULL

Prime Factoring Issue

It should be noted that NULL depends on factoring large numbers. Thus, implementations of a certain group of large programs, however valid, would be infeasable.

--Stux 03:25, 23 Sep 2005 (GMT)

It would only be infeasible IFF the programmer designed it to be so - namely, by suddenly using a very large prime number. If the programmer wrote the program always using the lowest possible prime number to encode the instruction, then implementation of ANY large program is.. feasible? Im not sure if feasible is the right word, since I don't believe that the word "feasible" would adequately characterize NULL. The algorithm to determine if a number is prime is relatively straightforward, then it's merely a matter of testing the next n prime numbers after the previous instruction, where n = 14. Again, this is ONLY if the programmer wants to make it "feasible" to program in. Knowing some of my fellow esolang programmers, this won't always be the case. --Wildhalcyon 14:21, 23 Sep 2005 (GMT)

But the size of primes you need increases as you go, such that compiling, say, The Sims 2 into NULL is essentially impossible. --Ihope127 22:49, 22 Oct 2005 (GMT)

Not necessarily. Like Wildhalcyon said, as long as the programmer uses only factors less than 43 (or some other small prime greater than 43), the factoring itself is still quite feasable: just trial factor through all 14 possibilities. However, you do bring an excellent point: running The Sims 2 increases the the integer size linearly (Order n) -- as you add more instructions the storage space you need for the number increases by approx 5 bits (log (2) of 43). For very large programs the number cannot fit in a register and is subject to polynomial time multiplication and division operations. This means that for a 5-million byte number, the first few divisions could easily take at least 625,000 CPU operations on a 64-bit processor. Assuming you have enough memory and don't need to page it to the hard disk. As the number gets smaller, the execution time decreases, kind of like a pyramid. --Stux 18:48, 23 Oct 2005 (GMT)

Reread the spec. You have to keep using increasingly large primes. --Graue 18:54, 23 Oct 2005 (GMT)

Ohhh! A loop is then formed: X is dividedby its smallest prime factor and y is multiplied by it. I see it now! I totally missed it. Indeed the problem is a LOT harder than I thought! My sincerest apologies to you Graue and to Ihope127. --Stux 22:11, 23 Oct 2005 (GMT)

Quantum computers can factor arbitrarily large numbers in polynomial time using Shor's algorithm, so compiling The Sims 2 into NULL isn't impossible, assuming that a practical quantum computer can be constructed. --Slobad 02:24, 3 Dec 2005 (GMT)

Is that "Hello World" number correct?

I run the given Python interpreter, and only get "Hello<nul>".

I added a little instrumentation to the interpreter, and here are the succession of primes in the given program:

3 3 3 17 31 73 127 139 167 227 277 283 283 311 389 449 449 463 491 491 571 631 739 769 773 823 
                ^               ^                   ^   ^                   ^               ^
                H               e                   l   l                   o             <nul>
 
853 947 947 1019 1051 1093
              ^
              ô

(As the other posters pointed out, you can see that the primes must increase for the algorithm to work.)

Fortunately, Python has support for arbitrarily large numbers (although performance would soon become a problem). Still, since you know that you must factor by one of the next 14 prime numbers, it's not quite the exhaustive prime factoring problem you would see in say, cryptographic cipher cracking.

To me the next logical question is, "how do generate the number in the first place?"

--PaulMcG 04:39, 1 Dec 2005 (GMT)

Thank you for pointing out! Maybe the program was incorrectly generated and I could not see any problem at all. I re-generated Hello world program and got this:

50056520978563208516819797718881283032143646116073595166114838703987562227081772
27277884468665934749909633552472002670467760272184148189288786549011066838407636
978909259289001144030816758344442315793 (199 digits)

I used this two-year-old naïve script for generation. --Tokigun 00:56, 11 Dec 2006 (UTC)

I found a problem in python interpreter. It's here:

def factor_g(include_builtin_list = True):
    if include_builtin_list:
        for x in plist: yield x
    k = plist[-1] + 7
    if k % 6 == 2:
        yield k-5
        k -= 2
    while True:
        yield k-1
        yield k+1
        k += 6

When table of primes consist of numbers up to 1019, next trial is 1025, so real prime 1021 is skipped, therefore it gives wrong indexes.

Rust program works fine.

--Ustin.fitc (talk) 10:26, 10 September 2018 (UTC)

Here is fixed code:

def factor_g(include_builtin_list = True):
    if include_builtin_list:
        for x in plist: yield x
    k = plist[-1]
    if k % 6 == 1:
        k += 5
    elif k % 6 == 5:
        yield k + 2
        k += 7
    while True:
        yield k - 1
        yield k + 1
        k += 6

I will also put fixed program to my github. https://github.com/NulAsh/nullrun --Ustin.fitc (talk) 11:27, 10 September 2018 (UTC)