Hello,
I am writing a sequence which requires me to generate a random number to write to a register (in reg_block) which shouldn’t be same as the reset value for any of the registers within the reg_block.
I am using the following code for this but it is O(n), I want to make it O(1).
foreach (regs[i]) reset_valQ[i] = regs[i].get_reset();
success = std::randomize(rnd_val) with { foreach (reset_valQ[k]) rnd_val != reset_valQ[k]; };
Is there a way to make this O(1)? Any help is highly appreciated. Thank you
In reply to mr_2020:
What does O(n) and O(1) mean?
In reply to dave_59:
O(n) : Order of n.
Each time the simulation tries to solve this constraint to ensure the random value is not the same as any of the reset value in the queue, it has to somehow compare the random value against all values in the queue. So checking whether a random value is one of the reset values is Order(n). assuming the queue has n elements.
O(1) : Order of 1 means not looping through all n elements of the queue and doing it in one shot.
In reply to mr_2020:
You can write the constraint without the foreach loop using unique:
success = std::randomize(rnd_val) with { unique {rnd_val, reset_valQ}; };
But realize that’s just syntactic sugar for your original code, so both are O(n) by your definition.
In reply to dave_59:
Thank you Dave for teaching me a new trick with the SV constraints. But yes that’s still of order n. Anything to make this more efficient?
In reply to mr_2020:
Before spending time trying to make something more efficient, you should performance profile your code to see if it’s worth the effort spending time trying to make something more efficient if you’ll never get that time back.
The only way I can think of getting an O(1) solution is building a list of all possible values of rnd_val excluding the values that match whats inside reset_valQ. Then generate a random number index into the remaining values. Depending on how many times you need to call randomize() you could spend more time building the list.
Modern constraint solvers have tons of optimizations from decades of experience that might make this effort totally unnecessary.