%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
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.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment