Best approach to achieve prime number via constraint

SystemVerilog
, ,
1

Hi Forum,

I have a parameterized class class Prime#(WIDTH) where WIDTH indicates the width of random property bit [WIDTH-1 : 0] numb

Using Prime#(10) p10_h, numb should have a prime number b/w 2 to 1023 ( i.e 2**10 - 1 )

(1) Solution1 would be to use constraints. However for a large value of WIDTH the constraints would be solved for each call to randomize which would have simulation performance.

(2) Solution2 would to have a const queue of all possible prime numbers the moment an object is created. The logic would execute only once which ends up populating the queue

One could then simply constraint numb to have a value inside this const queue.

For a value of WIDTH as 64 the logic might take longer so one could split the logic to divide into 2 parts

Part1 would find prime numbers from 2 to 2^32-1 and 2nd part would find prime numbers from

2 ^32 to 2^64 -1. However this still iterates from 2 to 2^64-1

I am trying to understand what would be the best approach to achieve prime number

Is there a better simulation efficient solution ?

2

Hi @Have_A_Doubt

Very beautiful question, thank you!

May I ask which constraint you wrote to find a prime number?
As far as I know, declarative or constraint-based approaches for finding prime numbers are not very common.

Personally, I would use an iterative algorithm, such as: Miller–Rabin.
Steps:

  1. Randomize an odd number in the range: 2..2^width-1.
  2. Run deterministic Miller–Rabin
  3. If composite, pick another candidate and repeat.

Regards the const queue - not sure how it could be calculated for WIDTH=64, since even using a supercomputer generating and storing all 64-bit primes is infeasible (hundreds of petabytes of storage and decades of CPU time :face_with_monocle:

3

Are you asking for the best from an academic perspective or a practical engineering application? I’ll leave the academic aspects to the Ph.D. students. Finding all the primes of a 64-bit number took several months on a massive distributed server farm.

For practical applications with widths of 32-bits or less, you should compute the prime numbers offline and store them in an array during to be read at compilation. At runtime, you can simply select a random index into the array. This approach requires 512 MB of memory to represent all the prime numbers of a 32-bit integer. (1-bit for each odd number to indicate if it’s prime or not)

2 Likes
4

Hi Dave,

A few quick questions

[1] Could you give a small example ( assuming it’s 3-bit ) ? I am not sure on how the prime numbers are calculated prior to compilation stage. Would one use a python based script or C-based code to calculate it ?

[2] Post [1] how would we read the array ? Would the array exist in some Input file that is read using $fopen ?

[3] I am not clear on how 512MB is calculated.

[4] Could you please elaborate on

“1-bit for each odd number to indicate if it’s prime or not”

Where would we store the 1-bit ? How does it relate with the array calculated in [1] ?

Thanks

5

You can create a program in any language to produce a file either in SystemVerilog syntax or $readmemb format.
SystemVerilog:

const bit isprime = {
0, //1
1, //3
1, //5
1, //7
0, //9
1, //11
1, //13
0  //15
};

$readmemb:

0 //1
1 //3
1 //5
1 //7
0 //9
1 //11
1 //13
0 //15

There are many algorithms for searching for prime numbers within an array. The algorithm I used uses a single bit to represent each odd number. If N represents a 4-bit number you wanted to check, this expression returns true if N a prime number.

N==2 || N[0]==1 && isprime[N>>1]

This approach simplifies the process of eliminating all the even numbers by simply checking the least significant bit. For the first 32 numbers (4-bits), this takes one byte of storage. There are other algorithms that trade off space for computational timing. However, this is not a significant issue in verification.

1 Like