How to Generate a Random Fraction Within a Specific Range

Question

In my project, I built my own Fraction:

public partial struct Fraction
{
    public double Numerator;
    public double Denominator;
    public readonly decimal Quotient
    {
        get 
        {
            decimal quotient;
            try
            {
                quotient = (decimal)Numerator / (decimal)Denominator;
            }
            catch
            {
                quotient = (decimal)(Numerator / Denominator);
            }
            return quotient;
        }
    }
}

I want to create a function that takes in a range and return a random Fraction within that range:

    public static Fraction GenerateRandomFraction(Fraction Min, Fraction Max)
    {
    }

I tried to think about it but couldn't find an algorithm can achieve what I want. I tried to search online but couldn't find any All I found was about decimal. I can make it work using a workaround:

1. Get the Quotient of the range.
2. Generate a random decimal number.
3. Convert it back to Fraction.

But I don't want to use it unless I'm 100% that's such algorithm doesn't exist.

Example: Min = 0/1, Max = 1/1 Result: 1/10 or 1/9, or 1/3 But I want it to be randomized.

Answer 1

If you are ok with limiting yourself to three digits each for the Numerator and Denominator the problem becomes fairly simple.

Start by creating all possible fractions and put them in a list. Then sort the list, you will need to implement comparison for your fractions to make this work. Then find the indices for your min and max fractions (or possibly the next lower/higher fraction) using BinarySearch. You can then simply generate a random integer between these indices and use this to find your fraction.

Note that there are infinite fractions between two fractions, and computers do not deal particular well with infinities. So if you cannot just list all the numbers to select from you may need to consider what the goal is. Nice looking numbers? Even sampling? speed? There will be tradeoffs depending on what you want to accomplish.

Answer 2

One solution that can work fairly well, is that you take your two fractions, minimum and maximum, alter them to make the denominators equal, (then assure the minimum is less than the maximum, otherwise swap them). After that generate random numbers between the two generated numerators.

Let's say you have 1/3 and 3/5:

1. Alter them to eaualize the denominators => 5/15 and 9/15.
2. Generate random numbers between the numerators 5 and 9.

If you wish to get more accuracy results, you can let the user decide an accuracy level, like let's say 3, then you do the same exact steps, but after equalizing the denominators, you also multiply the fractions with 10^3.

This way 1/3 and 3/5 become 5000/15000 and 9000/15000, and now you're gonna generate a number between 5000 and 9000.

Finally, a cherry on the top would be to reduce the generated fraction if possible, and you're done.

EDIT: There are certain things that could potentially improve the quality of the generated numbers, those are:

1. Give the user the option not to choose any accuracy, then the function would choose a random number of accuracy between let's say 1 and 10, then it's possible to get a generated fraction with a denominator of 10 digits randomly.
2. For further randomization, you can add an additional step after the accuracy step, which involves multiplying the numerator and denominator of the two fractions with a random integer chosen in a specific range, (because multiplying the numerator and denominator of a fraction with a number, doesn't change its value), this way you can get more randomized fractions, just make sure you're not multiplying with zero.

Answer 3

Here is an algorithm which has an even chance of picking any fraction with a maximum denominator d in the range a to b. If 2 < (b-a)*d this will have an average runtime of O(log(d)).

The process that I'm going to use is a variation of Rejection Sampling. That is we're going to use a random process to generate a candidate fraction that is guaranteed to include all of the possible answers, but may weight more heavily towards some than others. Then we'll reject at various points to wind up with every actual fraction with equal likelihood. Here is the actual algorithm in pseudocode, then I'll put the explanation below.

answer = null
while answer is null:
    x = ((b-a)*d*(d+1)/2 + d) * random.Next()
    do binary search to find smallest integer t...
        with x < (b-a)*t*(t+1)/2 + t
    y = x - (b-a)*t*(t-1)/2 - t + 1
    s = Math.floor(a*t + y)
    if a < s/t < b and gcd(s, t) = 1:
        answer = Fraction(s, t)

Now for why it works.

We're looking for a fraction of the form s/t where 1 <= t <= d.

What we will do for each possible t is take a piece of the real line from a*t to b*t + 1. We'll start at 0 and add them all up. We'll pick a random number in this range. We find which piece it is in - that gives us t. We'll then transfer that piece back to its original range from a*t to b*t + 1, and we'll take Math.floor to get s. If s/t is in the right range, we have a pair s, t with a < s/t < b. Furthermore every such pair is produced with equal likelihood.

Unfortunately we have the problem that 1/1 = 2/2 = 3/3 = .... And so we throw out the pair if there are common factors. Now we're picking every fraction with the same likelihood.

Now to the derivation.

The tth piece is of size (b-a)*t + 1. What is the sum of the size of the pieces up to n?

((b-a)*1 + 1) + ((b-a)*2 + 1) + ... + ((b-a)*n) + 1)
  = (b-a)*(1 + 2 + ... + n) + (1 + 1 + ... + 1)
  = (b-a)*n*(n+1)/2 + n

where I used the well-known formula for the sum of natural numbers.

So let x be a random number from 0 to (b-a)*d*(d+1)/2 + d. There is a first positive integer t with x < (b-a)*t*(t+1)/2 + t. We are in the tth piece. Subtract off the first t-1 pieces to get

y = x - ((b-a)*(t-1)*((t-1)+1)/2 + (t-1))
  = x - ((b-a)*(t-1)*t/2 + t - 1)
  = x - (b-a)*t*(t-1)/2 - t + 1

Add a*t and we get back to the original chunk of the real line where that piece started, then take Math.floor to get s. That gives us s, t. If it meets our conditions, then it is our answer.

Producing and testing this candidate involves a binary search and a gcd, both of which are O(log(d)) operations. To show that the average performance of the whole algorithm is O(log(d)) we just have to demonstrate that there is at least a fixed probability larger than 0 that we keep our answer.

Suppose that 2/d < (b-a). At least half the possible values of t from 1, 2, ..., d are greater than d/2. Since the larger t is, the more likely it is to be chosen, with at least even odds we'll pick t in that range. For each t in that range there is at least one value of s with a < s/t < b, and there are at most 2 values of s outside of that range. The values outside of that range cannot be more likely to be picked than the values inside. So the odds of finding a pair when t is in that range is at least 1/3. (It's actually at least 1/2, but there is no need for precision here.)

The analysis of gcd(s, t) = 1 is more complicated. However that's true a bit more than 60% of the time.

And so we keep our answer at least (1/2) * (1/3) * 0.6 of the time, which is a fixed probability larger than 0. And so rejection sampling will find the answer in expected time O(log(d)).