I've uploaded optimized upgraded versions of my SoZ prime generators, with included benchmarks against the Sieve of Atkin (SoA) and Sieve of Eratosthenes (SoE). Available here: http://www.4shared.com/dir/7467736/97bd7b71/sharing.html Versions for Python and Forth also provided here too. I am also finishing a paper presenting a mathematical/algorithmic analysis and explanation of my method. This will explain why the SoZ generators are computationally superior than the SoA and SoE. An interesting result is the benchmarks under Ruby 1.9.0-1 are many times faster than under "normal" Python, and even close compared to Python using the psyco C optimizing library. I've tried to run my Ruby code with JRuby, but I can't get JRuby to install correctly on my laptop (w/PCLinuxOS, Intel P4 2.8Ghz). I would appreciate if someone would run my code under JRuby, Rubinius, et al, and post results. Jabari

on 2008-11-20 22:50

on 2008-11-21 21:39

On Thu, Nov 20, 2008 at 9:33 PM, Frank Cameron > $ jruby SieveOfZakiya.rb > Error, could not compile; pass -d or > -J-Djruby.jit.logging.verbose=true for more details > user system total real > primes up to 10000001: 10.529000 0.000000 10.529000 ( 10.528562) > ... $ jruby -J-Djruby.jit.logging.verbose=true SieveOfZakiya.rb could not compile: SieveOfZakiya.rb because of: "Invalid method Code length 78818 in class file SieveOfZakiya" java.lang.ClassFormatError: Invalid method Code length 78818 in class file SieveOfZakiya at java.lang.ClassLoader.defineClass1(Native Method) at java.lang.ClassLoader.defineClass(ClassLoader.java:637) at org.jruby.util.JRubyClassLoader.defineClass(JRubyClassLoader.java:22) at org.jruby.compiler.impl.StandardASMCompiler.loadClass(StandardASMCompiler.java:147) at org.jruby.Ruby.tryCompile(Ruby.java:494) at org.jruby.Ruby.tryCompile(Ruby.java:474) at org.jruby.Ruby.runNormally(Ruby.java:453) at org.jruby.Ruby.runFromMain(Ruby.java:337) at org.jruby.Main.run(Main.java:214) at org.jruby.Main.run(Main.java:100) at org.jruby.Main.main(Main.java:84) user system total real primes up to 10000001: 10.125000 0.000000 10.125000 ( 10.125155) ...

on 2008-11-21 21:43

On Thu, Nov 20, 2008 at 3:46 PM, jzakiya <removed_email_address@domain.invalid> wrote: > I've uploaded optimized upgraded versions of my SoZ prime generators, > with included benchmarks against the Sieve of Atkin (SoA) and Sieve of > Eratosthenes (SoE). Available here: > > http://www.4shared.com/dir/7467736/97bd7b71/sharing.html > > I've tried to run my Ruby code with JRuby, but I can't get JRuby to > install correctly on my laptop (w/PCLinuxOS, Intel P4 2.8Ghz). > I would appreciate if someone would run my code under JRuby, Rubinius, > et al, and post results. $ uname -a Linux ViBEStation-alpha 2.6.27-7-generic #1 SMP Fri Oct 24 06:42:44 UTC 2008 i686 GNU/Linux $ cat /proc/cpuinfo | fgrep "model name" model name : Genuine Intel(R) CPU T2400 @ 1.83GHz model name : Genuine Intel(R) CPU T2400 @ 1.83GHz $ cat /proc/meminfo | fgrep MemTotal MemTotal: 1552052 kB $ ruby1.8 -v ruby 1.8.7 (2008-08-11 patchlevel 72) [i486-linux] $ ruby1.9 -v ruby 1.9.0 (2008-06-20 revision 17482) [i486-linux] $ jruby -v jruby 1.1.5 (ruby 1.8.6 patchlevel 114) (2008-11-03 rev 7996) [i386-java] $ java -version java version "1.6.0_0" IcedTea6 1.3.1 (6b12-0ubuntu6) Runtime Environment (build 1.6.0_0-b12) OpenJDK Client VM (build 1.6.0_0-b12, mixed mode, sharing) $ ruby1.8 SieveOfZakiya.rb user system total real primes up to 10000001: 12.060000 3.290000 15.350000 ( 15.416156) primes up to 10000001: 16.500000 2.690000 19.190000 ( 19.257785) primes up to 10000001: 4.530000 0.210000 4.740000 ( 4.748393) primes up to 10000001: 18.600000 2.510000 21.110000 ( 21.313465) primes up to 10000001: 11.830000 1.840000 13.670000 ( 13.736428) primes up to 10000001: 9.470000 1.300000 10.770000 ( 10.836533) primes up to 10000001: 8.810000 1.320000 10.130000 ( 10.169567) primes up to 10000001: 6.640000 0.210000 6.850000 ( 6.901754) primes up to 10000001: 4.650000 0.160000 4.810000 ( 4.859772) primes up to 10000001: 4.000000 0.190000 4.190000 ( 4.261946) primes up to 10000001: 7.780000 0.210000 7.990000 ( 8.005944) $ ruby1.9 SieveOfZakiya.rb user system total real primes up to 10000001: 3.970000 0.020000 3.990000 ( 4.038134) primes up to 10000001: 4.700000 0.040000 4.740000 ( 4.750093) primes up to 10000001: 1.770000 0.050000 1.820000 ( 1.825153) primes up to 10000001: 6.190000 0.080000 6.270000 ( 6.293999) primes up to 10000001: 4.120000 0.080000 4.200000 ( 4.220465) primes up to 10000001: 3.360000 0.060000 3.420000 ( 3.427870) primes up to 10000001: SieveOfZakiya.rb:962: [BUG] Segmentation fault ruby 1.9.0 (2008-06-20 revision 17482) [i486-linux] $ jruby SieveOfZakiya.rb Error, could not compile; pass -d or -J-Djruby.jit.logging.verbose=true for more details user system total real primes up to 10000001: 10.529000 0.000000 10.529000 ( 10.528562) primes up to 10000001: 14.105000 0.000000 14.105000 ( 14.105188) primes up to 10000001: 7.248000 0.000000 7.248000 ( 7.248299) primes up to 10000001: 15.564000 0.000000 15.564000 ( 15.564142) primes up to 10000001: 11.170000 0.000000 11.170000 ( 11.170565) primes up to 10000001: 8.735000 0.000000 8.735000 ( 8.734701) primes up to 10000001: 9.330000 0.000000 9.330000 ( 9.330105) primes up to 10000001: 11.366000 0.000000 11.366000 ( 11.365478) primes up to 10000001: 8.015000 0.000000 8.015000 ( 8.015094) primes up to 10000001: 12.421000 0.000000 12.421000 ( 12.420387) primes up to 10000001: 14.079000 0.000000 14.079000 ( 14.079476) $ python -V Python 2.5.2 $ python Sieves.py Traceback (most recent call last): File "Sieves.py", line 30, in <module> import psyco; psyco.full() ImportError: No module named psyco $ python Sieves.py 5 0.000430822372437 0.00113892555237 0.000353097915649 0.00146794319153 0.0988550186157 1000005 0.0542759895325 0.0466251373291 0.030809879303 0.0351409912109 0.318035125732 2000005 0.114179849625 0.104732990265 0.0793678760529 0.071692943573 0.142382144928 3000005 0.185572147369 0.170922994614 0.133031129837 0.12051987648 0.174972057343 4000005 0.268694877625 0.239547967911 0.192733049393 0.169470071793 0.171880960464 5000005 0.346322059631 0.307791948318 0.243360996246 0.21952009201 0.220386981964 6000005 0.43289399147 0.449116945267 0.302098035812 0.268841981888 0.269742965698 7000005 0.51304602623 0.448477983475 0.356249094009 0.31923699379 0.319150924683 8000005 0.598546981812 0.519491910934 0.415519952774 0.372243881226 0.374433994293 9000005 0.671094894409 0.591510057449 0.469482898712 0.424551010132 0.42044210434 10000005 0.757035017014 0.669479131699 0.5306661129 0.481162071228 0.471302032471 11000005 0.8411860466 0.747767925262 0.612731933594 0.523928880692 0.520886898041 12000005 0.920516967773 0.8079829216 0.652818202972 0.608549118042 0.570842981339 13000005 1.02680706978 0.879048109055 0.708424806595 0.627990007401 0.618942975998 14000005 1.08641910553 0.952656030655 0.779363870621 0.689521074295 0.667888879776 15000005 1.16809296608 1.02370405197 0.817245006561 0.72927904129 0.747013092041 16000005 1.24769997597 1.12631702423 0.87025809288 0.789395809174 0.765959024429 17000005 1.34199690819 1.16786408424 0.931406021118 0.826653003693 0.818248033524 18000005 1.41291308403 1.2686560154 0.988373041153 0.878173112869 0.867197990417 19000005 1.49461913109 1.34461092949 1.04254007339 0.94869184494 0.916136980057 20000005 1.58202815056 1.4249458313 1.1114461422 0.978127002716 0.96474814415

on 2008-11-21 23:09

On Thu, Nov 20, 2008 at 9:37 PM, <removed_email_address@domain.invalid> wrote: >> et al, and post results. > primes up to 10000001: 8.735000 0.000000 8.735000 ( 8.734701) > primes up to 10000001: 9.330000 0.000000 9.330000 ( 9.330105) > primes up to 10000001: 11.366000 0.000000 11.366000 ( 11.365478) > primes up to 10000001: 8.015000 0.000000 8.015000 ( 8.015094) > primes up to 10000001: 12.421000 0.000000 12.421000 ( 12.420387) > primes up to 10000001: 14.079000 0.000000 14.079000 ( 14.079476) $ jruby -J-server SieveOfZakiya.rb Error, could not compile; pass -d or -J-Djruby.jit.logging.verbose=true for more details user system total real primes up to 10000001: 6.195000 0.000000 6.195000 ( 6.194438) primes up to 10000001: 11.389000 0.000000 11.389000 ( 11.388889) primes up to 10000001: 6.085000 0.000000 6.085000 ( 6.085215) primes up to 10000001: 12.252000 0.000000 12.252000 ( 12.252067) primes up to 10000001: 7.555000 0.000000 7.555000 ( 7.555602) primes up to 10000001: 6.153000 0.000000 6.153000 ( 6.153644) primes up to 10000001: 5.805000 0.000000 5.805000 ( 5.805000) primes up to 10000001: 9.916000 0.000000 9.916000 ( 9.916375) primes up to 10000001: 9.148000 0.000000 9.148000 ( 9.147656) primes up to 10000001: 13.169000 0.000000 13.169000 ( 13.169869) primes up to 10000001: 16.541000 0.000000 16.541000 ( 16.540694) $ jruby -J-Xmn128m -J-Xms1024m -J-Xmx1024m -J-server SieveOfZakiya.rb Error, could not compile; pass -d or -J-Djruby.jit.logging.verbose=true for more details user system total real primes up to 10000001: 6.087000 0.000000 6.087000 ( 6.086382) primes up to 10000001: 9.360000 0.000000 9.360000 ( 9.360478) primes up to 10000001: 3.681000 0.000000 3.681000 ( 3.681715) primes up to 10000001: 10.023000 0.000000 10.023000 ( 10.022875) primes up to 10000001: 8.585000 0.000000 8.585000 ( 8.585405) primes up to 10000001: 5.008000 0.000000 5.008000 ( 5.007991) primes up to 10000001: 5.066000 0.000000 5.066000 ( 5.065975) primes up to 10000001: 6.416000 0.000000 6.416000 ( 6.415926) primes up to 10000001: 3.556000 0.000000 3.556000 ( 3.556291) primes up to 10000001: 4.631000 0.000000 4.631000 ( 4.631488) primes up to 10000001: 3.163000 0.000000 3.163000 ( 3.163181)

on 2008-11-22 01:23

removed_email_address@domain.invalid wrote: > $ jruby -J-Xmn128m -J-Xms1024m -J-Xmx1024m -J-server SieveOfZakiya.rb > Error, could not compile; pass -d or > -J-Djruby.jit.logging.verbose=true for more details Odd...the main script, or a method in it, must be gi-frigging-gantic to blow out the bytecode cap. Glad to see in your results below that with a bit of tweaking we're on par with 1.9. I'll look into the compilation issue; I know there are a few cases that can still pop the compiler, like really big arrays that require a lot of init. > user system total real ... > primes up to 10000001: 3.163000 0.000000 3.163000 ( 3.163181) Much better! Pretty noisy on the warmup though. - Charlie

on 2008-11-22 01:38

```
Charles Oliver N. wrote:
> like really big arrays that require a lot of init.
Yeah, there's several methods there that could easily blow the cap and
have to remain interpreted. The inability to compile the whole file as a
result is probably a large part of the lower perf. The algorithm is also
*extremely* memory-intensive; logging GC on JRuby it had to do multiple
full collections before the first iteration even came back.
- Charlie
```

on 2008-11-24 19:32

On Nov 21, 1:31 am, Charles Oliver N. <removed_email_address@domain.invalid> wrote: > > issue; I know there are a few cases that can still pop the compiler, > > like really big arrays that require a lot of init. > > Yeah, there's several methods there that could easily blow the cap and > have to remain interpreted. The inability to compile the whole file as a > result is probably a large part of the lower perf. The algorithm is also > *extremely* memory-intensive; logging GC on JRuby it had to do multiple > full collections before the first iteration even came back. > > - Charlie I just uploaded a more memory efficient and faster upgrade. Please check it out. Jabari

on 2008-11-24 20:14

```
jzakiya <removed_email_address@domain.invalid> wrote:
> Please check it out.
Cool, I'll try to give it a go on the same machine later today.
```

on 2008-11-24 21:14

On Nov 24, 2008, at 11:25 AM, jzakiya wrote: >>> Odd...the main script, or a method in it, must be gi-frigging- >> have to remain interpreted. The inability to compile the whole file > > Please check it out. On a Mac Pro (2.8 Ghz). Jruby 1.1.5 cremes$ jruby -J-Xmn128m -J-Xms1024m -J-Xmx1024m -J-server SieveOfZakiya.rb user system total real primes up to 10000001: 3.106000 0.000000 3.106000 ( 3.105799) primes up to 10000001: 5.774000 0.000000 5.774000 ( 5.773820) primes up to 10000001: 2.893000 0.000000 2.893000 ( 2.893756) primes up to 10000001: 7.883000 0.000000 7.883000 ( 7.883993) primes up to 10000001: 5.714000 0.000000 5.714000 ( 5.714248) primes up to 10000001: 4.792000 0.000000 4.792000 ( 4.791677) primes up to 10000001: 4.697000 0.000000 4.697000 ( 4.697211) primes up to 10000001: 4.066000 0.000000 4.066000 ( 4.065598) primes up to 10000001: 3.395000 0.000000 3.395000 ( 3.394890) primes up to 10000001: 3.232000 0.000000 3.232000 ( 3.232953) primes up to 10000001: 3.245000 0.000000 3.245000 ( 3.244323) Rubinius (built as of 5 minutes ago from latest git pull). I cancelled the run after an hour. It had not yet completed a single run. cr

on 2008-11-24 22:40

jzakiya wrote: > I've uploaded optimized upgraded versions of my SoZ prime generators, > with included benchmarks against the Sieve of Atkin (SoA) and Sieve of > Eratosthenes (SoE). Available here: > > http://www.4shared.com/dir/7467736/97bd7b71/sharing.html I looked at the code in there and it seemed awfully complex and difficult to follow. I thought that the sieve was a simple algorithm. While I am at work and not able to hammer out the wrinkles, if you consider this as psuedo code, it should give you an idea of what I am thinking. Wouldn't this be more straightforward? class findPrimes def initialize(max_prime) max_prime += 1 # for a 1 based array @isa_prime = Array.new max_prime.times { |index| @isa_prime[index] = true } @isa_prime[0] = false # never considered a prime number @isa_prime[1] = false # never considered a prime number flag_non_primes(2) # get all even numbers # check only odd numbers. If you find a prime one, # flag its multiples 3.step(max_prime, 2) { |i| flag_non_primes(i) unless @isa_prime[i] = false } end def isa_prime @isa_prime end # You only need to start with the square of the number as everything # between is a multiple of something else. # # You can skip every other multiple as it will be even. def flag_non_primes(starting) (starting * starting).step(max_prime, starting * 2) { |i| isa_prime[i] = false } end end primes = findPrimes.new(10_000_001)

on 2008-11-25 00:40

On Nov 24, 3:35 pm, Lloyd L. <removed_email_address@domain.invalid> wrote: > consider this as psuedo code, it should give you an idea of what I am > flag_non_primes(2) # get all even numbers > # You only need to start with the square of the number as everything > -- > Posted viahttp://www.ruby-forum.com/. Chuck, Thanks for those times for JRuby 1.1.5. They are comparable, though a bit slower, than I get on my PCLinuxOS based Intel P4, 2.8 Ghz laptop with Ruby 1.9.0-1 and Ruby 1.9.1- preview1 (which is a bit slower than 1.9.0-1). But I'm glad to see it not only ran, but ran well with JRuby. Hopefully Rubinius will be able to run it sometime soon too. Lloyd, Check out my Sieve of Zakiya paper I have on my 4shared site. It explains what I'm doing. All my SoZ generators have the same form, they just get bigger and have more 'stuff' to take care of. Look at the code to the generalized version: sozPn. This is the compact version that can perform the generalized algorithm for any prime generator from P3 thru P11. It will take as input the prime numbers 3,5,7,11 or the modulus values 6, 110, and all the multiples of 30 upto 210 (30, 60, 90, 120, 150, 180, 210). To run bigger prime/modulus values you need to compute a different class of, what I describe as, modulus complement pair (mcp) values, which I show in my paper. I actually can do sozPn(13) by feeding in the mcp values for it, but I need more memory to do higher than this. The method is really very simple and straightforward though. I'm hoping to finish up another paper detailing the mathematical and algorithmic features of the prime generators and algorithm before December. When I do I'll make an announcement. Jabari

on 2008-11-25 03:19

jzakiya <removed_email_address@domain.invalid> wrote: > Charles Oliver N. <removed_email_address@domain.invalid> wrote: >> Yeah, there's several methods there that could easily blow the cap and >> have to remain interpreted. The inability to compile the whole file as a >> result is probably a large part of the lower perf. The algorithm is also >> *extremely* memory-intensive; logging GC on JRuby it had to do multiple >> full collections before the first iteration even came back. > > I just uploaded a more memory efficient and faster upgrade. > > Please check it out. $ ruby1.8 -v SieveOfZakiya.rb ruby 1.8.7 (2008-08-11 patchlevel 72) [i486-linux] user system total real primes up to 10000001: 12.160000 3.280000 15.440000 ( 15.968446) primes up to 10000001: 16.410000 2.710000 19.120000 ( 19.802800) primes up to 10000001: 4.340000 0.300000 4.640000 ( 4.708012) primes up to 10000001: 18.340000 2.510000 20.850000 ( 21.099350) primes up to 10000001: 11.600000 1.750000 13.350000 ( 13.638693) primes up to 10000001: 9.060000 1.450000 10.510000 ( 10.802420) primes up to 10000001: 8.410000 1.260000 9.670000 ( 9.923761) primes up to 10000001: 6.620000 0.200000 6.820000 ( 7.042592) primes up to 10000001: 4.620000 0.210000 4.830000 ( 4.858175) primes up to 10000001: 4.010000 0.210000 4.220000 ( 4.241419) primes up to 10000001: 9.060000 0.230000 9.290000 ( 9.345546) $ ruby1.9 -v SieveOfZakiya.rb ruby 1.9.0 (2008-06-20 revision 17482) [i486-linux] user system total real primes up to 10000001: 3.870000 0.020000 3.890000 ( 4.007278) primes up to 10000001: 4.670000 0.050000 4.720000 ( 4.884780) primes up to 10000001: 1.710000 0.060000 1.770000 ( 1.818867) primes up to 10000001: 6.020000 0.080000 6.100000 ( 6.291805) primes up to 10000001: 3.970000 0.050000 4.020000 ( 4.189796) primes up to 10000001: 3.170000 0.080000 3.250000 ( 3.355820) primes up to 10000001: SieveOfZakiya.rb:1272: [BUG] Segmentation fault ruby 1.9.0 (2008-06-20 revision 17482) [i486-linux] $ jruby -v SieveOfZakiya.rb jruby 1.1.5 (ruby 1.8.6 patchlevel 114) (2008-11-03 rev 7996) [i386-java] Error, could not compile; pass -d or -J-Djruby.jit.logging.verbose=true for more details user system total real primes up to 10000001: 10.117000 0.000000 10.117000 ( 10.116355) primes up to 10000001: 14.625000 0.000000 14.625000 ( 14.624596) primes up to 10000001: 7.303000 0.000000 7.303000 ( 7.303146) primes up to 10000001: 16.469000 0.000000 16.469000 ( 16.468992) primes up to 10000001: 10.874000 0.000000 10.874000 ( 10.874482) primes up to 10000001: 8.648000 0.000000 8.648000 ( 8.648109) primes up to 10000001: 9.625000 0.000000 9.625000 ( 9.624519) primes up to 10000001: 10.190000 0.000000 10.190000 ( 10.190249) primes up to 10000001: 9.384000 0.000000 9.384000 ( 9.383951) primes up to 10000001: 10.588000 0.000000 10.588000 ( 10.587707) primes up to 10000001: 15.747000 0.000000 15.747000 ( 15.747025) $ jruby -v -J-server SieveOfZakiya.rb jruby 1.1.5 (ruby 1.8.6 patchlevel 114) (2008-11-03 rev 7996) [i386-java] Error, could not compile; pass -d or -J-Djruby.jit.logging.verbose=true for more details user system total real primes up to 10000001: 6.457000 0.000000 6.457000 ( 6.457001) primes up to 10000001: 11.203000 0.000000 11.203000 ( 11.202618) primes up to 10000001: 5.599000 0.000000 5.599000 ( 5.599136) primes up to 10000001: 12.384000 0.000000 12.384000 ( 12.384355) primes up to 10000001: 7.844000 0.000000 7.844000 ( 7.844102) primes up to 10000001: 6.420000 0.000000 6.420000 ( 6.420077) primes up to 10000001: 7.478000 0.000000 7.478000 ( 7.478256) primes up to 10000001: 8.779000 0.000000 8.779000 ( 8.778884) primes up to 10000001: 8.752000 0.000000 8.752000 ( 8.752092) primes up to 10000001: 10.061000 0.000000 10.061000 ( 10.060471) primes up to 10000001: 11.674000 0.000000 11.674000 ( 11.674323) $ jruby -v -J-Xmn128m -J-Xms1024m -J-Xmx1024m -J-server SieveOfZakiya.rb jruby 1.1.5 (ruby 1.8.6 patchlevel 114) (2008-11-03 rev 7996) [i386-java] Error, could not compile; pass -d or -J-Djruby.jit.logging.verbose=true for more details user system total real primes up to 10000001: 4.512000 0.000000 4.512000 ( 4.512570) primes up to 10000001: 9.059000 0.000000 9.059000 ( 9.058663) primes up to 10000001: 3.557000 0.000000 3.557000 ( 3.556361) primes up to 10000001: 11.114000 0.000000 11.114000 ( 11.113504) primes up to 10000001: 16.059000 0.000000 16.059000 ( 16.059220) primes up to 10000001: 5.075000 0.000000 5.075000 ( 5.075088) primes up to 10000001: 4.964000 0.000000 4.964000 ( 4.964077) primes up to 10000001: 6.260000 0.000000 6.260000 ( 6.260179) primes up to 10000001: 3.720000 0.000000 3.720000 ( 3.720471) primes up to 10000001: 2.877000 0.000000 2.877000 ( 2.877802) primes up to 10000001: 4.547000 0.000000 4.547000 ( 4.547695)