Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

johngg's scratchpad

by johngg (Abbot)
on Feb 02, 2006 at 14:43 UTC ( #527334=scratchpad: print w/replies, xml ) 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 $
Log In?

What's my password?
Create A New User
and John Coltrane plays...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (4)
As of 2017-01-18 10:07 GMT
Find Nodes?
    Voting Booth?
    Do you watch meteor showers?

    Results (161 votes). Check out past polls.