随机有理数生成

有理数是可数的。例如，此代码在开区间 0..1 中查找第 k 个有理数，排序为{n1, d1}是在之前{n2, d2} if (d1<d2 || (d1==d2 && n1<n2))假设{n,d}是互质的。

RankedRational[i_Integer?Positive] := 
 Module[{sum = 0, eph = 1, den = 1},
  While[sum < i, sum += (eph = EulerPhi[++den])];
  Select[Range[den - 1], CoprimeQ[#, den] &][[i - (sum - eph)]]/den
  ]

In[118]:= Table[RankedRational[i], {i, 1, 11}]

Out[118]= {1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6}

现在我想生成随机有理数，给定分母上界，均匀地排序，以便对于足够大的分母有理数将在单位区间上均匀分布。

直观上，我们可以在所有具有相同权重的小分母的有理数中进行选择：

RandomRational1[maxden_, len_] := 
 RandomChoice[(Table[
     i/j, {j, 2, maxden}, {i, 
      Select[Range[j - 1], CoprimeQ[#, j] &]}] // Flatten), len]

是否可以更有效地生成具有这种分布的随机有理数，而不需要构造所有有理数？这张桌子不需要太多就能变得很大。

In[197]:= Table[RankedRational[10^k] // Denominator, {k, 2, 10}]

Out[197]= {18, 58, 181, 573, 1814, 5736, 18138, 57357, 181380}

或者也许可以有效地生成具有不同“感觉均匀”分布的有界分母的有理数？

Clear[RandomFarey];
RandomFarey[n_, len_] := Module[{pairs, dim = 0, res, gcds},
  Join @@ Reap[While[dim < len,
      gcds = cfGCD[pairs = cfPairs[n, len - dim]];
      pairs = Pick[pairs, gcds, 1];
      If[pairs =!= {}, 
       dim += Length@Sow[res = pairs[[All, 1]]/pairs[[All, 2]]]];
      ]][[2, -1]]
  ]

以下编译函数生成整数对{i,j}这样1<=i < j<=n:

cfPairs = 
  Compile[{{n, _Integer}, {len, _Integer}}, 
   Table[{i, RandomInteger[{i + 1, n}]}, {i, 
     RandomChoice[2 (n - Range[n - 1])/(n (n - 1.0)) -> Range[n - 1], 
      len]}]];

下面的编译函数计算 gcd。它假设输入是一对正整数。

cfGCD = Compile[{{prs, _Integer, 1}}, Module[{a, b, p, q, mod},
    a = prs[[1]]; b = prs[[2]]; p = Max[a, b]; q = Min[a, b]; 
    While[q > 0, mod = Mod[p, q]; p = q; q = mod]; p], 
   RuntimeAttributes -> Listable];

Then

In[151]:= data = RandomFarey[12, 10^6]; // AbsoluteTiming

Out[151]= {1.5423084, Null}

In[152]:= cdf = CDF[EmpiricalDistribution[data], x];

In[153]:= Plot[{cdf, x}, {x, 0, 1}, ImageSize -> 300]

我强烈建议看看任意有理数的“猜数字”游戏？ https://stackoverflow.com/questions/5440688/the-guess-the-number-game-for-arbitrary-rational-numbers以获得有关您的根本问题的一些灵感。

如果您的目标是尽快达到大致均匀，并且您不介意选择具有不同概率的不同有理数，则以下算法应该是有效的。

lower = fractions.Fraction(0)
upper = fractions.Fraction(1)

while lower < upper:
    mid = (upper + lower)/2
    if 0 == random_bit():
        upper = largest_rational_under(mid, denominator_bound)
    else:
        lower = smallest_rational_over_or_equal(mid, denominator_bound)

请注意，这两个辅助函数都可以通过将 Stern-Brocot 树向中间移动来计算。另请注意，通过一些细微的修改，您可以轻松地将其转换为迭代算法，该算法输出一系列有理数，并最终以相等的可能性在区间内的任何位置收敛。我认为那个属性有点不错。

如果您想要最初指定的精确分布，并且rand(n)给你一个随机整数1 to n，那么以下伪代码将适用于分母界限n:

Try:
    k = rand(n * (n+1) / 2)
    do binary search for largest j with j * (j-1) / 2 < k
    i = k - (j * (j-1) / 2)
    if (i, j) are not relatively prime:
        redo Try
answer = i/j

平均而言，对于大型n你必须Try约2.55倍。所以在实践中这应该是非常有效的。