Forum: Ruby C-ish bitwise prime sieve in Ruby?

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
E7fe24cfaaf8af56ae28f63c81363172?d=identicon&s=25 Jimmy Kofler (koflerjim)
on 2007-03-02 15:05
Can we translate the following C-coded prime sieve by Frank Pilhofer
into a Ruby version that also uses bitwise operations?

Thanks for any suggestions!



#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc/malloc.h>

/*
Sieve of Eratosthenes.
C code by Frank Pilhofer.
http://www.fpx.de/fp/Software/Sieve.html
*/


#define TEST(f,x)  (*(f+(x)/16)&(1<<(((x)%16L)/2)))
#define SET(f,x)          *(f+(x)/16)|=1<<(((x)%16L)/2)

int main(int argc, char *argv[])
{
  unsigned char *feld=NULL, *zzz;
  unsigned long teste=1, max, mom, hits=1, count, alloc, s=0, e=1;
  time_t begin;

  if (argc > 1)
    max = atol (argv[1]) + 10000;
  else
    max = 14010000L;

  while (feld==NULL)
        zzz = feld = malloc (alloc=(((max-=10000L)>>4)+1L));

  for (count=0; count<alloc; count++) *zzz++ = 0x00;

  //printf ("Searching prime numbers to : %ld\n", max);

  begin = time (NULL);
  while ((teste+=2) < max)
        if (!TEST(feld, teste)) {
                ++hits;
                //if  (++hits%2000L==0) {printf (" %ld. prime
number\x0d", hits); fflush(stdout);}
                for (mom=3L*teste; mom<max; mom+=teste<<1) SET (feld,
mom);
                }

  printf (" %ld prime numbers found in %ld secs.\n\nShow prime numbers",
          hits, time(NULL)-begin);

  while (s<e) {
        printf ("\n\nStart of Area : "); fflush (stdout); scanf ("%ld",
&s);
        printf ("End   of Area : ");     fflush (stdout); scanf ("%ld",
&e);

        count=s-2; if (s%2==0) count++;
        while ((count+=2)<e) if (!TEST(feld,count)) printf ("%ld\t",
count);
        }
  free (feld);
  return 0;
}
852a62a28f1de229dc861ce903b07a60?d=identicon&s=25 Gavin Kistner (phrogz)
on 2007-03-02 15:45
(Received via mailing list)
On Mar 2, 7:05 am, Jimmy Kofler <kofler...@mailinator.com> wrote:
> Can we translate the following C-coded prime sieve by Frank Pilhofer
> into a Ruby version that also uses bitwise operations?

Yes! Ruby supports bitwise operations on Integers. One thing to watch
out for: Ruby's integers are unbounded in size, so shifting left may
produce different results in a Ruby Integer than on a 32- or 64-bit
int in C. You'll need to mask the values whenever something might
overflow.

For example:

irb(main):001:0> i = 0x7FFF_FFFF
=> 2147483647
irb(main):002:0> '%032b' % i
=> "01111111111111111111111111111111"
irb(main):003:0> i2 = i << 1
=> 4294967294
irb(main):004:0> '%032b' % i2
=> "11111111111111111111111111111110"
irb(main):005:0> i4 = i << 2
=> 8589934588
irb(main):006:0> '%032b' % i4
=> "111111111111111111111111111111100"
irb(main):007:0> i4 = (i << 2) && 0xFFFF_FFFF
=> 4294967295
irb(main):008:0> '%032b' % i4
=> "11111111111111111111111111111111"
852a62a28f1de229dc861ce903b07a60?d=identicon&s=25 Gavin Kistner (phrogz)
on 2007-03-02 16:15
(Received via mailing list)
On Mar 2, 7:05 am, Jimmy Kofler <kofler...@mailinator.com> wrote:
> /*
> Sieve of Eratosthenes.
> C code by Frank Pilhofer.http://www.fpx.de/fp/Software/Sieve.html
> */

Also:
a) http://www.google.com/search?q=Eratosthenes+ruby

b) If you're doing this to learn Ruby, that's fine. However, if you
want speed, you might want to look at RubyInline, which lets you re-
use pieces of C-code directly within Ruby.
This topic is locked and can not be replied to.