Corner of Seven

For a possible job in the Seattle area, one of my prospective employers is having me submit some solutions to problems found on Project Euler. While working on a particular issue, I’ve discovered that the method I’ve used for calculating the list of prime numbers performs better than the stock Prime class that is provided by the Ruby Standard Library.

That’s fun to say and all, but I’m sure that there would be people who would like to have some proof of this: see below.

My method, shown above, tends to perform slightly better at the task using the test parameter. So, I figured, why not do some more vigorous verification on it?

After setting up the system to run at multiple data points, I found something peculiar, yet interesting:

Hand-rolled (at 10^3):
Difference in time: 0.000569
mathn (at 10^3):
Difference in time: 0.001286
Hand-rolled (at 10^4):
Difference in time: 0.008029
mathn (at 10^4):
Difference in time: 0.014407
Hand-rolled (at 10^5):
Difference in time: 0.14803
mathn (at 10^5):
Difference in time: 0.165025
Hand-rolled (at 10^6):
Difference in time: 2.823072
mathn (at 10^6):
Difference in time: 2.687332
Hand-rolled (at 10^7):
Difference in time: 62.096438
mathn (at 10^7):
Difference in time: 64.990647


For powers of ten, it seems as though my process is faster. 10⁶ doesn’t quite follow the pattern, though.

I then ran the same test on different data points:
Hand-rolled (at 2^14):
Difference in time: 0.014882
mathn (at 2^14):
Difference in time: 0.009224
Hand-rolled (at 2^15):
Difference in time: 0.036732
mathn (at 2^15):
Difference in time: 0.022161
Hand-rolled (at 2^16):
Difference in time: 0.085459
mathn (at 2^16):
Difference in time: 0.044076
Hand-rolled (at 2^17):
Difference in time: 0.208553
mathn (at 2^17):
Difference in time: 0.076775
Hand-rolled (at 2^18):
Difference in time: 0.498292
mathn (at 2^18):
Difference in time: 0.151843

Running everything as powers of two show a reversal of position for the results; the standard lib does better. This gives me some insight as to why the above 10⁶ test is reversed; the value for 10⁶ is very close to a power of two (2²⁰), and so the optimizations that are in the ruby library to handle near 2ⁿ are in effect at that point. Logically, I would see something similar for 10⁹, but I’m not going to let my computer sit for a day to crunch that out.

Tags: 50 lines of code, algorithm, code, euler, math, number, prime, prime number, project euler, questions, ruby

Posted in 50 Lines of Code, Neat and Interesting, personal, Ruby, Tech