c++ - 将无理分数转换为一组四个真/假分数

Question

这是我正在尝试做的示例代码。当然，这需要很长时间才能处理 (410^8)。

编辑:

目标是允许在 0.0*/1 和 100.*/1 的近似范围内输入实数，例如.457473343788374/1, 8.5476457654/1 并使用四个分数得出最佳可能的近似值，所有分数都具有两个指定约束(例如 16 到 400)之间的整数。

分数代表机器中需要精确计时并且可以适合给定空间的齿轮齿。想想 Antikythera 装置。

主要目标是在找到近似值时不停止，而是找到即使以牺牲效率为代价也不能改进的最佳近似值。

是否有专门针对此类问题的算法？

for(auto_t num_1 = 20; num_1 != 431; num_1++)
  {
    for(auto_t num_2 = 20; num_2 != 431; num_2++)
      {
        for(auto_t num_3 = 20; num_3 != 431; num_3++)
          {
            for(auto_t num_4 = 20; num_4 != 431; num_4++)
              {
                for(auto_t num_5 = 20; num_5 != 431; num_5++)
                  {
                    for(auto_t num_6 = 20; num_6 != 431; num_6++)
                      {
                        for(auto_t num_7 = 20; num_7 != 431; num_7++)
                          {
                            for(auto_t num_8 = 20; num_8 != 431; num_8++)
                              {

        nOutput = double(num_1*num_2*num_3*num_4)/(num_5*num_6*num_7*num_8);

                              }
                          }
                      }
                  }
              }
          }
      }
 }

我写了一些运行速度相当快并且返回看起来准确的结果的东西。

位于此处(64 位，Vista 或更新版本):http://1drv.ms/1zgpQnB

例子:

pi ~~ (323 * 379 * 413 * 388)/(235 * 283 * 229 * 410) 我如何确认使用 20 到 430 的范围是否尽可能准确？或者不是(我怀疑不是)。

更多:

pi ~~ (381 701 341 523)/(309 573 128 669) 使用 25 到 750 作为约束。

cos(45d) ~~ (617 713 723 92)/(485 734 263 442) ''

Answer 1

这种类型的循环非常低效。您正在检查 411^8 ~ 8x10^20 种可能性。正如 Ben Voigt 评论的那样，您可以通过选择一组无序的分母和一组无序的分子将其减少大约 4!^2 ~ 600，但这仍然很糟糕 (10^17)。

一个快速归约是创建一个排序的分子集合和一个排序的分母集合，然后遍历分母，只检查恰好在分母 pi 上方和下方的分子。如果分子的数量是 n，如果你能高效地完成，这大约需要 n log n 个步骤。这只有几十亿步，主要用于对列表进行排序，因此您实际上可以这样做，并且可以并行对数字进行排序，以便轻松扩展。

使用晶格缩减对此进行了改进。

但是，以这种方式通过反复试验找到这种近似值的整个想法很糟糕。有一个数学领域称为 Diophantine approximation，它包括用有理数逼近无理数。您可以使用简单连分数理论或 Farey 序列快速找到良好的近似值。这是一种快速找到大量合理近似值的方法:从 3/1 < pi < 4/1 开始。将分子和分母相加得到 7/2。将 pi 与新分数进行比较。它更低，所以我们有 3/1 < pi < 7/2。迭代。这将达到 pi 的简单连分数的所有收敛点，例如 22/7、355/113 和 5419351/1725033。在像 3.011 这样的尴尬情况下，有一些简单的方法可以稍微加快速度，在这种情况下，您反复调整一个分数而不是另一个分数。

如果出于某种原因你对分数的乘积很感兴趣(这是一个竞赛题吗？)，那么我认为你最好找到所有好的有理近似值，然后将它们分解成分子和分母的分数您指定的范围。