Perl-Sensitive Sunglasses PerlMonks

by johngg (Abbot)
 on Feb 02, 2006 at 14:43 UTC Need Help??

The "Sieve of Eratosthenes" optimises the calculation of prime numbers up to the limit we specify by keeping track of every number and marking if it can NOT be a prime number. It does this by finding the first prime number, 2, then marking every multiple of it as not prime, i.e. 4, 6, 8, ... and then moves to the next number that isn't so marked, which must also be prime. That would be 3 so then all multiples of 3 are marked (they may already have been marked but that doesn't matter) i.e. 6, 9, 12, ... and the process is repeated, finding 5 and marking 10, 15, 20, etc.

You could keep track of the numbers in an array and this would work perfectly well but could take up a lot of space if you were looking for all prime numbers up to, say, 500,000,000 or so. All we need to record for each number is whether it is a prime or not; this is a two-state piece of information (0 or 1 respectively) that can be held in a single bit rather than a byte or word, making for at least an 8-fold saving of space, leaving aside the mechanics of how Perl stores its internal variables. The tool Perl gives us to play around with individual bits is vec.

The vectors that vec builds are just scalar strings and can comprise multiple-bit elements but for the purposes of this discussion I will only deal with single-bit vectors. Because vectors are just strings they with always be a whole number of bytes long; if I want to use just the first 5 bits I will still get a vector of 8 bits, or 1 byte, but no matter as the last 3 that I'm not interested in can be ignored. The bits are arranged in each byte with the most significant bit first, e.g. for a vector of 16 bits taking 2 bytes the layout would be:-

```  bit           111111
offset  7654321054321098
vector  0000000000000000

To see a representation of the bits in a vector we can use unpack with the 'B' template which, from the documentation in its converse (pack), outputs:-

B A bit string (descending bit order inside each byte).

To demonstrate that vectors are just strings we cam look up the ASCII decimal and binary values of, say, the letters "A" and "B"

```\$  perl -Mstrict -Mwarnings -E '
say q{         76543210};
say qq{\$_ - }, ord, q{ - }, sprintf q{%08b}, ord for qw{ A B };'
76543210
A - 65 - 01000001
B - 66 - 01000010
\$

We can use these binary values with vec to construct a short string. Remember that the bit offsets in each byte descend from left to right.

```\$ perl -Mstrict -Mwarnings -E '
my \$vec;
vec( \$vec, 0, 1 ) = 1;
vec( \$vec, 6, 1 ) = 1;
say \$vec;
say unpack q{B*}, \$vec;
vec( \$vec, 14, 1 ) = 1;
vec( \$vec,  9, 1 ) = 1;
say \$vec;
say unpack q{B*}, \$vec;'
A
01000001
AB
0100000101000010
\$

Create A New User
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (11)
As of 2017-05-25 19:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favorite model of computation is ...

Results (187 votes). Check out past polls.