3
$\begingroup$

Could somebody please help me understand what is going on here (in plain English)? I think that $(k \mathbin{\&} 63)$ has the effect of modular division. Is that right? How are the primes encoded / how can I know exactly where a number starts and ends by moving my finger across each 64-bit word?

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, ...


[The goal is to make] a table of all odd prime numbers less than 1024, so that we can easily decide the primality of a small integer.

  1. The ultimate package density is achieved when we have 1-bit items.
  2. We can cram them into a 64-bit word.
  3. Only 64-bit numbers are required.
  4. To test whether $2k+1$ is prime, for $0 ≤ k < 512$, simply compute the following in a 64-bit register, and see if the leftmost bit is 1:

$$P_{\lfloor k/64\rfloor} << (k \mathbin{\&} 63)$$

P is in big-endian format. Q is in little-endian format.

P0 —0111011011010011001011010010011001011001010010001011011010000001, 
P1 —0100110000110010010100100110000110110000010000010110100110000100, 
P2 -1001001100101100001000000101101000000100100001101001000100100101, 
P3 -0010001010001000011000011001010010001011010000010001010001010010, 
P4 —0000110000000010010000100100110010000100100110010010110000010000, 
P5 -1101001001100000101001000100001000100001000100100101000100101000, 
P6 —1010000001000010000011000011011000010000001011010000001011010000, 
P7 -0000010100010000100010100100100000010100100100010010000010100110.

For little-endian, $$Q_{\lfloor k/64\rfloor} >> (k \mathbin{\&} 63) $$

and look at the rightmost bit of the result.

Q0 — 1000000101101101000100101001101001100100101101001100101101101110, 
Q1 - 0010000110010110100000100000110110000110010010100100110000110010, 
Q2 - 1010010010001001011000010010000001011010000001000011010011001001, 
Q3 - 0100101000101000100000101101000100101001100001100001000101000100, 
Q4 — 0000100000110100100110010010000100110010010000100100000000110000, 
Q5 — 0001010010001010010010001000010001000010001001010000011001001011, 
Q6 — 0000101101000000101101000000100001101100001100000100001000000101, 
Q7 — 0110010100000100100010010010100000010010010100010000100010100000;

– The Art of Computer Programming. Volume 4, Fascicle 1. Bitwise Tricks and Techniques. Binary Decision Diagrams. p.5

$\endgroup$
2
$\begingroup$

P is in big-endian format.
P0 —0111011011010011001011010010011001011001010010001011011010000001,

The first bit, 0, means 2*0 + 1 = 1 is not a prime.
The second bit, 1, means 2*1 + 1 = 3 is a prime.
The third bit, 1, means 2*2 + 1 = 5 is a prime.
The fourth bit, 1, means 2*3 + 1 = 7 is a prime.
The fifth bit, 0, means 2*4 + 1 = 9 is not a prime.
The sixth bit, 1, means 2*5 + 1 = 11 is a prime.
The seventh bit, 1, means 2*6 + 1 = 13 is a prime.
The eighth bit, 0, means 2*7 + 1 = 15 is not a prime.
The ninth bit, 1, means 2*8 + 1 = 17 is a prime.
And so on.

P1 —0100110000110010010100100110000110110000010000010110100110000100,

The first bit, 0, means 2*64 + 1 = 129 is not a prime.
The second bit, 1, means 2*65 + 1 = 131 is a prime.
The third bit, 0, means 2*66 + 1 = 133 is not a prime.
The fourth bit, 0, means 2*67 + 1 = 135 is not a prime.
The fifth bit, 1, means 2*68 + 1 = 137 is a prime.
The sixth bit, 1, means 2*69 + 1 = 139 is a prime.
The seventh bit, 0, means 2*70 + 1 = 141 is not a prime.
The eighth bit, 0, means 2*71 + 1 = 143 is not a prime.
The ninth bit, 0, means 2*72 + 1 = 145 is not a prime.
And so on.

P2 -1001001100101100001000000101101000000100100001101001000100100101,

The first bit, 1, means 2*128 + 1 = 257 is a prime.
And so on.

P3 -0010001010001000011000011001010010001011010000010001010001010010,

The first bit, 0, means 2*192 + 1 = 385 is not a prime.
And so on.

And so on.

P7 -0000010100010000100010100100100000010100100100010010000010100110.

The first bit, 0, means 2*448 + 1 = 897 is not a prime.
And so on.
The last bit, 0, means 2*511+1 = 1023 is not a prime.

Could somebody please help me understand what is going on here (in plain English)? I think that (k&63) has the effect of modular division. Is that right? How are the primes encoded / how can I know exactly where a number starts and ends by moving my finger across each 64-bit word?

If you have read the above explanation for many bits in P0, P1, ..., P7, the answer to your questions should be obvious now. For a number $2k+1$, $\lfloor k/64\rfloor$, the quotient of $k$ divided by 64, is which $P$ should be used. $k \mathbin{\&} 63$, the remainder of $k$ divided by 64 is how many bits you should move to the right to find its primeness-indicator bit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.