Sieve of Zakiya

Discussion in 'Ruby' started by jzakiya, Nov 20, 2008.

  1. jzakiya

    jzakiya Guest

    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
    jzakiya, Nov 20, 2008
    #1
    1. Advertising

  2. jzakiya

    Guest

    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)
    ...
    , Nov 21, 2008
    #2
    1. Advertising

  3. jzakiya

    Guest

    On Thu, Nov 20, 2008 at 3:46 PM, 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'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
    , Nov 21, 2008
    #3
  4. jzakiya

    Guest

    On Thu, Nov 20, 2008 at 9:37 PM, <> wrote:
    > On Thu, Nov 20, 2008 at 3:46 PM, 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'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.

    >
    > $ 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)


    $ 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)
    , Nov 21, 2008
    #4
  5. 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
    Charles Oliver Nutter, Nov 21, 2008
    #5
  6. Charles Oliver Nutter wrote:
    > 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.


    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
    Charles Oliver Nutter, Nov 21, 2008
    #6
  7. jzakiya

    jzakiya Guest

    On Nov 21, 1:31 am, Charles Oliver Nutter <>
    wrote:
    > Charles Oliver Nutter wrote:
    > > 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.

    >
    > 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
    jzakiya, Nov 24, 2008
    #7
  8. jzakiya

    Guest

    jzakiya <> wrote:
    > Charles Oliver Nutter <>
    > 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.


    Cool, I'll try to give it a go on the same machine later today.
    , Nov 24, 2008
    #8
  9. jzakiya

    Chuck Remes Guest

    On Nov 24, 2008, at 11:25 AM, jzakiya wrote:

    > On Nov 21, 1:31 am, Charles Oliver Nutter <>
    > wrote:
    >> Charles Oliver Nutter wrote:
    >>> 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.

    >>
    >> 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.


    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
    Chuck Remes, Nov 24, 2008
    #9
  10. 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 =
    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 = false }
    end
    end

    primes = findPrimes.new(10_000_001)
    --
    Posted via http://www.ruby-forum.com/.
    Lloyd Linklater, Nov 24, 2008
    #10
  11. jzakiya

    jzakiya Guest

    On Nov 24, 3:35 pm, Lloyd Linklater <> wrote:
    > 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 =
    > 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 = false }
    >   end
    > end
    >
    > primes = findPrimes.new(10_000_001)
    > --
    > 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
    jzakiya, Nov 24, 2008
    #11
  12. jzakiya

    Guest

    jzakiya <> wrote:
    > Charles Oliver Nutter <> 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)
    , Nov 25, 2008
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jzakiya
    Replies:
    3
    Views:
    542
    jzakiya
    Jul 19, 2008
  2. jzakiya
    Replies:
    4
    Views:
    468
    user923005
    Jun 13, 2008
  3. jzakiya

    Sieve of Zakiya

    jzakiya, Nov 4, 2008, in forum: Python
    Replies:
    7
    Views:
    302
    Mark Dickinson
    Nov 19, 2008
  4. jzakiya
    Replies:
    6
    Views:
    181
    Michael Ulm
    Jun 11, 2008
  5. Replies:
    0
    Views:
    71
Loading...

Share This Page