Thursday, July 10, 2014

Problem 50 - Postscript

I have been working out a solution to the next problem, problem 88, and I figured I wanted a pretty capable language for my solution to that one, so I decided to free up such a language. Now, the language i had free to do this freeing up with was Postscript. Prior to this project, my main experiences with Postscript had been writing an interpreter for a subset of the language, and using the language way back when in my initial 24 hour run to solve problem 7. Now, however, I used Postscript to free up C, which means that I used it to solve problem 50. Once I got into the swing of things, the stack-basedness wasn't too bad, the main issues that arose were due to my inability to parse error messages, causing bugs to be hard to remove (and, as would be expected when using an unfamiliar programming paradigm, bugs abounded). This problem gave me a chance to write an implementation of my smarter sieve method from my analysis before...though in my attempt to also generate an independent isPrime method, I messed up at first (an independent isPrime method cannot assume the input number is not divisible by 2 or 3, it actually needs to check that!). But anyway, other than lots of little mistakes like that, things weren't too bad. Postscript isn't the most blazingly fast language though, so even with a number of optimizations that were not present in my C solution to problem 50, the solution below runs in about 50 seconds on my machine, whereas my C solution ran in about 0.5s. But either way, it runs in under a minute, so it is acceptable. Now, to solve problem 88 in C.
%Implementation of "Smartest Sieve" from Sieve Timing :)
%Assumes symbol /primes is defined
/isPrime {
    /x exch def
    /ip true def
    /i 0 def
    /for2 {
        /p primes i get def
        x p mod 0 eq {
            /ip false def
        } {
            p p mul x le {
                /i i 1 add def
                for2
            } if
        } ifelse
    } def
    for2   
    ip     
} def

/primeSieve {
    /N exch def
    /primes N array def
    primes 0 2 put
    primes 1 3 put
    primes 2 5 put
    /primeLength 3 def
    /n 7 def
    /for1 {
        n isPrime {
            primes primeLength n put
            /primeLength primeLength 1 add def
        } if
        /n 2 n mul 3 mod 2 mul n add def
        n N lt {
            for1
        } if
    } def
    for1
} def

%Assumes symbol /primes is defined
/partialSum {
    /sum 0 def
    /high exch def
    /low exch def
    /k low def
    /for3 {
        /sum sum primes k get add def
        /k k 1 add def
        k high lt {
            for3
        } if
    } def
    for3
    sum
} def

/BOUND 1000000 def
%Method defines symbols /primes and /primeLength
%We do not use any return value
BOUND primeSieve
/ans 0 def
/maxChainLength 1 def
/lindex 0 def
/for4 {
    lindex primeLength lt {
        /hindex lindex maxChainLength add def
    hindex primeLength lt {
        /psum lindex hindex partialSum def
        /for5 {
            hindex primeLength lt psum BOUND lt and {
                psum isPrime {
                    /ans psum ans max def
                    /maxChainLength hindex lindex sub def
                } if
                /psum psum primes hindex get add def
                /hindex hindex 1 add def
                for5
            } if
        } def
        for5
        /lindex lindex 1 add def
        for4
    } if
    } if
} def
for4

ans pstack pop

No comments:

Post a Comment