c++ - 使用64位分子和分母对pi的最佳有理近似值是什么？

用两个64位整数表示的Pi最精确的有理对是什么？如果需要，可以随意包含其他int类型。
这是我想出的，但是我敢肯定，因为分母可以变得更大，所以它可以变得更准确-我只是在以10为底的思维。我很确定分子应该类似于uint64 max。

// c++
inline constexpr auto pi_num = 3141592653589793238ull;
inline constexpr auto pi_den = 1000000000000000000ull;
// c
const unsigned long long pi_num = 3141592653589793238ull;
const unsigned long long pi_den = 1000000000000000000ull;

最佳答案

您可以使用continued fractions获得无理数的出色近似值。如果您以前从未遇到过连续小数，则可以将数字写为该形式的嵌套小数序列

将越来越多的项加到连续分数中，得出的有理数越来越好。
continued fraction of π是

[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13, 1, 4, 2, 6, 6, 99, 1, 2, 2, 6, 3, 5, 1, 1, 6, 8, 1, 7, 1, 2, 3, 7, 1, 2, 1, 1, 12, 1, 1, 1, 3, 1, 1, 8, 1, 1, 2, 1, 6, 1, 1, 5, 2, 2, 3, 1, 2, 4, 4, 16, 1, 161, ...]

因此，我们可以编写一个小小的Python脚本来基于这种连续的分数表示来计算近似值，如下所示:

from fractions import *

digits = [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13, 1, 4, 2, 6, 6, 99, 1, 2, 2, 6, 3, 5, 1, 1, 6, 8, 1, 7, 1, 2, 3, 7, 1, 2, 1, 1, 12, 1, 1, 1, 3, 1, 1, 8, 1, 1, 2, 1, 6, 1, 1, 5, 2, 2, 3, 1, 2, 4, 4, 16, 1, 161]

for i in range(len(digits)):
    # Start with the last digit
    f = Fraction(digits[i]);

    # Keep rewriting it as term + 1 / prev
    for j in range(i-1, -1, -1):
        f = digits[j] + 1 / f

    # Stop if we overshoot
    if f.numerator >= 2**64 or f.denominator >= 2**64: break

    # Print the approximation we found
    print(f)

这样会以越来越好的近似值打印出连续的分数，直到我们超出了适合64位整数的值为止。这是输出:

3
22/7
333/106
355/113
103993/33102
104348/33215
208341/66317
312689/99532
833719/265381
1146408/364913
4272943/1360120
5419351/1725033
80143857/25510582
165707065/52746197
245850922/78256779
411557987/131002976
1068966896/340262731
2549491779/811528438
6167950454/1963319607
14885392687/4738167652
21053343141/6701487259
1783366216531/567663097408
3587785776203/1142027682075
5371151992734/1709690779483
8958937768937/2851718461558
139755218526789/44485467702853
428224593349304/136308121570117
5706674932067741/1816491048114374
6134899525417045/1952799169684491
30246273033735921/9627687726852338
66627445592888887/21208174623389167
430010946591069243/136876735467187340
2646693125139304345/842468587426513207

我认为，最后一个近似值是π的最佳近似值，它适合64位整数。 (有可能在该分母和您得到的下一个分母之间出现一个更好的整数，该分母溢出了64位整数，但这仍然很接近!)因此，您想要

const uint64_t pi_num   = 2646693125139304345u;
const uint64_t pi_denom = 842468587426513207u;

This source报告此近似值精确到小数点后37位(!):

3.14159265358979323846264338327950288418 (approximation)
3.14159265358979323846264338327950288419 (actual)

对于您要进行的操作，这应该绰绰有余。 (当然，除非您试图设置一个记录以查找π或类似的数字。^ _ ^)

关于c++ - 使用64位分子和分母对pi的最佳有理近似值是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/62925107/