Exercise 5 for RandomNumberGenerationTutorial - slightly cleaner solution

[abrassel]

The current approach for the RandomNumberGenerationTutorial tries to generate random numbers from [0, max) until it finds a value in [min, max]. You could make it a bit more efficient this way:

operation RandomNumberInRange (min : Int, max : Int) : Int {
    let range = max - min;
    let N = BitSizeI(range + 1);
    mutable result = 0;
    repeat {
        set result = RandomNBits(N);
    }
    until result <= range;
    return min + result;
}

Also, because the original implementation calls BitSizeI(max), and RandomNBits(N) generates values between [0, 2^N-1], if max is a power of 2 (e.g. 2^N), then RandomNBits will generate values in the range [0, max). Adding +1 to the range fixes this. Incidentally, it looks like the tests don't detect this edge case, as I was able to pass with and without the +1

[Manvi-Agrawal]

@abrassel , seems there are three things at play here: efficiency of current algorithm, correctness of existing solution and passing of your solution with and without +1.

• Efficiency: I agree that your solution is slightly more efficient. I think it would be a good idea to have it as an alternative solution in workbook
• Correctness of existing solution: The existing solution is correct because BitSizeI function returns the minimum number of bits required to represent a number. BitSizeI function reference. To validate this, you can create an operation Demo_BitSizeI() operation in the jupyter notebook as follows:

open Microsoft.Quantum.Math;
operation Demo_BitSizeI() : Unit {
  let nBits = BitSizeI(8);
  Message($"Bits required to represent 8 {nBits}");
  }

And you can run above operation in jupyter notebook by executing the following code in a separate code cell. This gives 4 as the result

%simulate Demo_BitSizeI

• Solution passing with/without +1: As explained in second point, BitSizeI function returns the minimum bits required to represent a number. In your case, you are generating random numbers in range [0, max-min+1] both inclusive and then filtering out extra number max-min+1 in until condition by specifying result<=max-min. Hence the test is passing.

For alternative solution, I have a minor suggestion to use let N= BitSizeI(range).

I hope this answers your query. @tcNickolas thoughts?

[abrassel]

Thank you Manvi!

[tcNickolas]

I'm sorry for not answering this back in summer! I'm not sure how I've missed it, possibly I've read it and nodded along but got distracted before I actually commented?

I agree that it makes sense to use the more efficient approach you're describing, both as the main reference solution in the ReferenceImplementation.qs and in the workbook. Would you be interested in sending the pull request with the change? (I understand if you're not, it's been a couple months, which I'm terribly sorry about...)

[abrassel]

Hi Nickolas! I don't have the time at the moment to submit the PR, but you are welcome to copy and paste this solution yourself!