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.

• trincot: How much probability should there be to generate 172839274398431/181289239839123?
• JonasH: What purpose has this? There are an infinite number of possible fractions between two numbers. So any sampling would be approximate. If you want "nice" fractions, that are easily understandable by a human, you need to define your problem better. If this is for any kind of simulation you should probably convert everything to doubles.
• Mr_Sure21: @trincot I think any fraction that consist of 3 digits 000/000 we can limit it by a variable that's not the issue
• trincot: So then generate a random numerator between 0 and 999 and set the denominator to 999, and simplify if possible (divide both by the gcd). This means some nice fractions will never appear, like 1/2, but those "nicer" fractions do not have an even distribution; you need to make a selection to get an even distribution.
• Mr_Sure21: @JonasH It's more like a question about if there is such an algorithm doesn't matter if it's limited by variables, not an issue. as I said I can use the other solution. anyway I'm making Linear Algebra calculator I want to make a function to create a random Fraction Matrix but First I want to be able to create a single random fraction and also I want to make it readable.

Answer 1

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)).

Answer 2

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.

• btilly: This requires creating and sorting a rather large number of fractions. The code will be simple, but very inefficient.
• JonasH: @btilly It should only be 10^6 for three digits each, so a fair amount, but not prohibitively so. I would expect it to take well under a second. And you only need to create/sort the list once.
• btilly: "Only" 10^6. And if you want to do millionths, then you "only" need 10^12. That's what I mean by inefficient. By contrast I provided a random sampling algorithm that takes logarithmic time.
• JonasH: @btilly I'm not sure what your point is. There are certainly advantages to your method, but also some disadvantages. You yourself admit it "may weight more heavily towards some than others". This approach has other advantages, it works well for small sets, should be easy to implement, and give the user full control over the candidate set. The OP is not very clear about what the specific goal is, so providing multiple different answers should be a good thing, no? And "inefficiency" really depend on the use case, another thing the OP is not very clear about.
• btilly: Thank you for pointing out that I forgot to fix my introduction when I figured out how to make it perfectly even. I'll fix that now. (My first approach was randomly sample, then use continued fractions, add a few fixes to improve sampling error.) As for your approach, it is always inefficient. On small enough problems it works anyways. That's the nature of inefficiency. But even so, knowing the Stern-Brocot tree would be helpful. Generate rationals in order, use reservoir sampling. Still slow, but you save memory.

Answer 3

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.