C-ish bitwise prime sieve in Ruby?

[Jimmy Kofler]

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;
}

 

[Phrogz]

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"

 

[Phrogz]

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
*/

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.