Prime numbers constraint

write a constraint to randomly generate 10 unique prime numbers in an array between 1 and 200. the generated prime numbers shoould have 7 in it . example ( 07,17,37… et

In reply to pradeepD:

What is your question?

In reply to dave_59:

My question is that how I will make that lsb part as constant 7

In reply to pradeepD:

You could simply constraint lower 4 bits to be 7


constraint LSB_7 { rand_var[3:0] == 7 ; }

In reply to ABD_91:

I am not able to understand your point. My point is that the randomly generated prime number should have 7 at the lsb side (eg 17,37,47 etc…).

In reply to pradeepD:

You want the numbers to be BCD ( 17 , 37 , 47 etc … )

So each digit would be represented in 4-bits .

Your question is how do I make LSB part as 7 , I gave you the solution to achieve it

The lowest digit is always 7 by constraint LSB_7

In reply to ABD_91:

Thanks Dave and ABD_91 for the clarification

In reply to pradeepD:


module test;
class prime_number;
  rand bit [8:0] a[$],b[$];
  constraint abc {a.size==200; }
  constraint cba { foreach(a[i])
    if(i>1 )
     a[i]==prime(i);}
 
  function int prime( int g);
    for(int i=2;i<g;i++)
        if(g%i==0)
          return 2; //if it is not a prime number ,returning 2 which is one of prime
      prime=g;
    endfunction
  function void post_randomize();
    a=a.unique;
   for(int i=0;i<a.size;i++)
     if(a[i]%10==7)
       b.push_back(a[i]);  //in b queue you will find prime numbers with units place as 7.
 
  endfunction
endclass

prime_number pri;

initial
  begin
    pri=new;
    void'(pri.randomize);
    $display("%p",pri);
  end
endmodule
1 Like

In reply to Bandaru sateesh:

Hi, I have run your code on eda playground platform. It’s giving some unexpected outcomes. In queue a, we are saving all prime numbers less than 200. But we didn’t mention any specific condition for the first two cases when i=0 and i=1. Due to this reason, we are getting some absurd values which are not satiating our requirement partially.
I tried to redesign the code. Please look into it. If there is any edge case, I missed out on, please mention it in this thread.

module test;
class prime_number;
  rand int a[],b[$];
  constraint abc {a.size==200; }
  constraint cba { foreach(a[i])
    a[i]==prime(i);}
 
  function int prime( int g);
    if(g <= 1)return 2;
    for(int i=2;i<g;i++)
      if(g%i==0)
          return 2; //if it is not a prime number ,returning 2 which is one of prime
      prime=g;
    endfunction
  function void post_randomize();
    a=a.unique;
   for(int i=0;i<a.size;i++)
     begin
     if(a[i]%10==7)
       b.push_back(a[i]);  //in b queue you will find prime numbers with units place as 7.
    if(b.size() == 10) break;
     end
  endfunction
endclass
 
prime_number pri;
 
initial
  begin
    pri=new;
    assert(pri.randomize);
    $display("%0p",pri.b);
  end
endmodule

In reply to Shubhabrata:

Hi, I just found out this thread. My logic was mostly similar except I wasn’t using the
prime = g logic. I’m not entirely sure what/how does that work? Are you assigning value to a variable? Where are you returning that? I’m unfamiliar with this syntax of system verilog function.

Thanks

In reply to nitin4natu:

Verilog allows you to use the name of the function as an implicit variable storing the return value. If you exit the function without using return, that value becomes the returned value. In this case, prime=g; is the same as return g;

Note that prior to SystemVerilog, the return construct did not exist. so you had to make an assignment to the implicit variable.

*In reply to dave_59:*Thanks, Dave!

This is my solution. Seems to work fine, if you guys see any issues, please let me know.

module test();

  class x;
    rand int arr;
    int q[$];

    constraint sel{
      !(arr inside {q});
      arr < 200;
      arr>0; 
      arr%10 == 7;


    }

    function int prime(int arr);
      for(int i = 2;i<arr;i++) begin
        if(arr%i==0)
          return 0;
      end
      return 1;
    endfunction


    function void post_randomize();

      if(prime(arr))
        q.push_back(arr);
    endfunction
  endclass

  initial begin
    x a = new();
    while(a.q.size()<10) begin
      a.randomize();
    end
    $display("%p",a.q);
  end
endmodule

This is prime number generator code using constraint
So as per original question
We want numbers to be prime + numbers whos LSB is 7

Prime no Theory:
Prime numbers are one which can be divisible by 1 or itself
So if X is prime number then from 2 to (X-1) any number less than X can not divide X
Here, we can make our code efficient by dividing numbers from 2 till X/2
Lets see with example:
prime number 11
Hence 11 is divisible by 1 and 11 and no numbers 2 to 10 can not divide 11
For efficiency we try to divide 11 from 2 to (11/2) that is 2 to 5
Numbers 2,3,4,5 can not divide 11 hence we confirmed that number is prime number
We are not checking numbers 6,7,8,9,10 because if no lower elements are able to divide 11 hence we do not need to check upper elements(i.e > 11/2)

My approach is:
1] generate prime number in integer array of dynamic size. (dynamic array size limit mentioned in constraint). All generated prime numbers will be unique as per my code
2] In Post randomize when prime numbers are generated, I am picking numbers from prime number generated stream and pushing it to queue
3] So required final number streams are present in queue

This is my code with comments

class packet;
  rand int arr[];
  int que[$];
  ///////////Constraint
  constraint cons_name2{arr.size() inside{[10:25]};}
  constraint cons_name{foreach(arr[index])
 						 {
                           arr[index] == prime(index);
                         }
                      }
  
  //////////properties for prime num
   int prime_num=7; //last saved prime number in array is 7 , 
  
   
  ///////////Method for prime num
    function int prime(int index);
       int flag=0; //default number is not prime number assumption hence flag is 0
         //hard code first 4 element i.e 2,3,5,7             
         if(index == 0)
     	 	return 2;
         else if(index == 1)
     		return 3;
         else if(index == 2)
     		return 5;
         else if(index == 3)
     		return 7;
         else begin
      
         prime_num= prime_num +1;  //so next prime numbers will be upwards 7 hence +1 before going to for loop
           
      
      for(int i=2; i<=(prime_num)/2;i++)begin //For loop till (Prime_num/2 )mentioned reason above in theory
        if(prime_num%i == 0)begin //any divisor found able to divide our prime_num
          flag = 0;     //means prime_num is not prime hence need to update prime_num and start loop again 
          prime_num = prime_num +1; //increment number
          i=2; //reset base divisor to 2
        end 
        else begin
          flag = 1;  //none of divisor found who can divide our prime number
        end 
      end
      
           
      if( flag == 1 ) begin
        return prime_num; // hence we found prime number and return to constraint
      end
           
     end   
    endfunction
     //////// Post randomization  function, here complete array is generated and we are picking only elements which LSB is 7 using %10 operation to get remainder 7                       
        function void post_randomize(); //post function after arr is generated
            foreach(arr[i])begin
                if(arr[i]%10 == 7) //divide integer by 10 remainder is 7 means LSB 7
                que.push_back(arr[i]);
            end
        endfunction              
 endclass
                      
                       
module TB_TOP;
  
  initial begin
    packet pkt=new();
    pkt.randomize();
    $display("Prime no in array %p",pkt.arr);
    $display("Prime no ends with 7 are %p",pkt.b);
  end

endmodule

# Loading sv_std.std
# Loading work.design_sv_unit(fast)
# Loading work.TB_TOP(fast)
#
# run -all
# Prime no in array '{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73}
# Prime no ends with 7 are '{7, 17, 37, 47, 67}
# exit
# End time: 03:35:55 on Jun 26,2024, Elapsed time: 0:00:00
# Errors: 0, Warnings: 0
# *** Summary *********************************************
# qrun: Errors: 0, Warnings: 0
# vlog: Errors: 0, Warnings: 3
# vopt: Errors: 0, Warnings: 5
# vsim: Errors: 0, Warnings: 0
# Totals: Errors: 0, Warnings: 8


You can shuffle que to get random que in post randomization function :)

Ok, This is one bonus code :)

In my previous comment if you go through theory i am trying numbers from 7 onwards one by one and check each number whether it is prime number or not. If it is prime number then pick it and move forward

prime_num= prime_num +1; //so next prime numbers will be upwards 7 hence +1 before going to for loop

Which is also not much efficient code for simulator if i want large array size suppose 500 or 1000 then looking for each numbers and checking it is prime or not is not much optimal solution, as numbers increase difference between two consecutive prime numbers will increase and code unnecessary checking numbers in between which are surly not prime numbers. It will work no doubt but not efficient way of doing

I was going through some theory related to prime numbers
and saw one post in geekforgeeks

Theory:

  • Every prime number can be represented in form of 6n + 1 or 6n – 1 except the prime numbers 2 and 3 , where n is any natural number.

So instead of looking for all numbers just look for (6n-1) and (6n+1) numbers. 2 and 3 are default prime numbers. Since any prime number can be multiple of 6n-1 pr 6n+1
NOTE: can be multiple, it does not means strictly mulitple of 6n-1 and 6n+1
Example
default numbers=2,3 now move ahead to find next prime numbers
Put n=1,2,3,4 in 6n-1 and 6n+1
numbers generated are 5,7,11,13,17,19,23,25 [25 is not prime numbers other are prime numbers]
so you can see prime numbers are either 6n-1 or 6n+1.
but not strictly multiple of this formula
So in above n=4 6n+1=25 and it is not prime number
Hence can be prime number but not strictly prime numbers

Approach:
1]With above theory, I am hopping to only (6n-1) and (6n+1) numbers to check those numbers are prime or not. Because for sure numbers other these are not prime numbers. hence no need to check those
2] Default prime numbers I am adding are 2,3,5,7

I have explain code with comments

class packet;
  rand int arr[];
  ///////////Constraint
  constraint cons_name2{arr.size() inside{[500:600]};}
  constraint cons_name{foreach(arr[index])
 						 {
                           arr[index] == prime(index);
                         }
                      }
  
  //////////properties for prime num
  int hop_index= 2;// for index 1 (6n-1) and (6n+1) it is hard coded print ie 5 and 7 respectively [hop_index is same as n]
  int incr_decr= -1; //-1 and +1 this 2 possible value see in formula other than n we have -1 and +1
  int prime_num;
 
  
    
  ///////////Method for prime num
    function int prime(int index);
       int flag=0; //default number is not prime number assumption hence flag is 0
         //hard code first 4 element for 6n-1 and 6n+1 rule              
         if(index == 0)
     	 	return 2;
         else if(index == 1)
     		return 3;
         else if(index == 2)
     		return 5;
         else if(index == 3)
     		return 7;
         else begin
      
      //For index above 3
      
           prime_num = prime_6n1_formula(); // first hop starts from n=2 hence 6n-1= 11 6n+1=13, n=1 numbers 5 and 7 already coded as default
           
      
      for(int i=2; i<=(prime_num)/2;i++)begin
        if(prime_num%i == 0)begin //any divisor found able to divide our prime_num
          flag = 0;     //means prime_num is not prime hence need to update prime_num and start loop again 
          hop_update();
          prime_num = prime_6n1_formula(); //function contain 6n-1 and 6n+1 formula
          i=2; //reset base divisor to 2
        end 
        else begin
          flag = 1; 
        end 
      end
      
           
      if( flag == 1 ) begin
        hop_update();// before returning found prime number we hop update for next iteration
      	return prime_num;
      end
     end   
    endfunction
 //below are Individual Functions for calculating next possible prime number
                       
     function int prime_6n1_formula(); 
       return (6*hop_index + incr_decr);
     endfunction
  
     function void hop_update(); 
//if not  understand this hop logic try to print numbers for 6n-1 and 6n+1 and see common pattern

       if(incr_decr == 1)begin
         hop_index= hop_index+1; //increment hop index
         incr_decr= -1; // reset hop index
        //if incr_decr = 1 means we have 2 possible combination  with next value of n (i.e 6n-1 and 6n+1 ) hence incr_decr to -1 and hop_index incremented
       end
       else begin
         //do not change hop index 
         incr_decr= 1; //update incr_decr
        //if incr_decr = -1 means we have one more combination remain with same value of n (i.e 6n+1 is remain) hence only change incr_decr to +1
       end
  	 endfunction

endclass
  
                       
                       
module TB_TOP;
  initial begin
    packet pkt=new();
    pkt.randomize();
    $display("Hopping 6n-1 and 6n+1 to get prime numbers");
    $display("Prime no in array %p",pkt.arr);
  end
endmodule

Output:
Loading work.TB_TOP(fast)
#
# run -all
# Hopping 6n-1 and 6n+1 to get prime numbers
# Prime no in array '{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 244***trimmed
# exit

1 Like

Thanks for this. I like all the comments and other details.
Is modifying variable “prime_num” in the function legal?
Based on this thread Function in Constraint this might work in some simulators but not all and is mostly not-recommended.
Overall I like the solution very much, and the bonus stuff below, the only issue being the modification of local variable.

class test;
rand int num;
int b [$];
function void post_randomize();
int count;
for(int i=0;i<num;i++) begin
count=0;
for(int j=1;j<=i/2;j++) begin
if(i%j==0)
count++;
end
if(count==1&&i%10==7)
b.push_back(i);
end
endfunction
endclass

module tb;
test t;
initial begin
t=new;
assert (t.randomize with {num==100;});
$display(“prime numbers =%0p”,t.b);
end

endmodule

this code also works for prime numbers as well as 7,17 type of pattern.if you remove i%10==7 in post randomization method it will give only prime numbers if you include it will give you 7,17,37…etc.

prime numbers =7 17 37 47 67 97

exit