假设我有一个实数。对于整数 a 和 b，我想用 a+sqrt(b) 形式的东西来近似它。但我不知道 a 和 b 的值。当然，我更愿意得到一个小的 a 和 b 值的近似值。让我们暂时不定义“好”和“小”的含义。这些术语的任何合理定义都可以。
有没有一种理智的方法可以找到它们？类似于用于查找小数的分数逼近的连分数算法。有关分数问题的更多信息，请参见此处。
编辑：澄清一下，这是一个任意实数。我只有一堆数字。因此，根据我们想要的近似值的好坏，a 和 b 可能存在也可能不存在。蛮力自然不是特别好的算法。我能想到的最好的方法是开始将整数添加到我的实数中，对结果进行平方，然后查看我是否接近整数。几乎是蛮力，并不是一个特别好的算法。但是，如果没有更好的存在，这本身就会很有趣。
编辑：显然 b 必须为零或正数。但 a 可以是任何整数。
不需要连分数；只需计算所有“小”值的平方根b（直到您认为仍然“足够小”的任何值），删除小数点之前的所有内容，然后将它们全部排序/存储（连同b生成它的那个）。
然后，当您需要逼近一个实数时，找到其小数部分最接近实数小数部分的部首。这给了你b- 选择正确a的就是一个简单的减法问题。
这实际上更像是一个数学问题，而不是一个计算机问题，但要回答这个问题，我认为你是对的，你可以使用连分数。你要做的是首先将目标数表示为连分数。例如，如果要近似 pi (3.14159265)，则 CF 为：
3: 7, 15, 1, 288, 1, 2, 1, 3, 1, 7, 4 ...
下一步是为平方根创建一个 CF 表，然后将表中的值与目标值的小数部分进行比较（此处为：7、15、1、288、1、2、1、3、1、 7、4...)。例如，假设您的表格只有 1-99 的平方根。然后你会发现最接近的匹配是 sqrt(51)，它的 CF 为 7: 7,14 重复。7,14 最接近 pi 的 7,15。因此，您的答案将是：
平方（51）-4
作为给定 ab < 100 的最接近的近似值，相差 0.00016。如果您允许更大的 b，那么您可以获得更好的近似值。
使用 CF 的优点是它比使用双精度数或使用浮点数更快。例如，在上述情况下，您只需比较两个整数（7 和 15），您还可以使用索引来快速找到表中最近的条目。
这可以使用混合整数二次规划非常有效地完成（尽管没有运行时保证，因为 MIQP 是 NP 完全的。）
定义：
d := the real number you wish to approximate
b, a := two integers such that a + sqrt(b) is as "close" to d as possible
r := (d - a)^2 - b, is the residual of the approximation
目标是最小化r。将您的二次程序设置为：
x := [ s b t ]
D := | 1 0 0 |
| 0 0 0 |
| 0 0 0 |
c := [0 -1 0]^T
with the constraint that s - t = f (where f is the fractional part of d)
and b,t are integers (s is not)
这是一个凸的（因此是最优解的）混合整数二次程序，因为D它是半正定的。
一旦s,b,t被计算，只需使用 , 得出答案b=b，s=d-a并且t可以忽略。
您的问题可能是 NP 完全的，如果是这样证明会很有趣。
之前的一些答案使用时间或空间复杂度 O(n) 的方法，其中 n 是将被接受的最大“小数”。相比之下，以下方法在时间上是 O(sqrt(n))，在空间上是 O(1)。
假设正实数r = x + y，其中x=floor(r)和0 ≤ y < 1。我们想r通过一个数字来近似的形式a + √b。如果x+y ≈ a+√bthen x+y-a ≈ √b，那么√b ≈ h+y对于一些整数偏移量h，并且b ≈ (h+y)^2。为了使 b 成为整数，我们希望最小化(h+y)^2所有符合条件的小数部分h。最多有 的√n合格值h。请参阅以下 python 代码和示例输出。
import math, random
def findb(y, rhi):
bestb = loerror = 1;
for r in range(2,rhi):
v = (r+y)**2
u = round(v)
err = abs(v-u)
if round(math.sqrt(u))**2 == u: continue
if err < loerror:
bestb, loerror = u, err
return bestb
#random.seed(123456) # set a seed if testing repetitively
f = [math.pi-3] + sorted([random.random() for i in range(24)])
print (' frac sqrt(b) error b')
for frac in f:
b = findb(frac, 12)
r = math.sqrt(b)
t = math.modf(r)[0] # Get fractional part of sqrt(b)
print ('{:9.5f} {:9.5f} {:11.7f} {:5.0f}'.format(frac, r, t-frac, b))
（注 1：此代码为演示形式；参数为findb()，y小数部分r，和rhi，最大小数的平方根。您可能希望更改参数的用法。注 2：代码行
if round(math.sqrt(u))**2 == u: continue
防止findb()返回 的完美平方值b，但值 b=1 除外，因为没有完美平方可以提高 b=1 提供的精度。）
示例输出如下。中间省略了大约十几行。第一个输出行显示此过程产生b=51表示 的小数部分pi，这与其他一些答案中报告的值相同。
frac sqrt(b) error b
0.14159 7.14143 -0.0001642 51
0.11975 4.12311 0.0033593 17
0.12230 4.12311 0.0008085 17
0.22150 9.21954 -0.0019586 85
0.22681 11.22497 -0.0018377 126
0.25946 2.23607 -0.0233893 5
0.30024 5.29150 -0.0087362 28
0.36772 8.36660 -0.0011170 70
0.42452 8.42615 0.0016309 71
...
0.93086 6.92820 -0.0026609 48
0.94677 8.94427 -0.0024960 80
0.96549 11.95826 -0.0072333 143
0.97693 11.95826 -0.0186723 143
在程序末尾添加以下代码后，还会出现如下所示的输出。这显示了 pi 小数部分的更接近的近似值。
frac, rhi = math.pi-3, 16
print (' frac sqrt(b) error b bMax')
while rhi < 1000:
b = findb(frac, rhi)
r = math.sqrt(b)
t = math.modf(r)[0] # Get fractional part of sqrt(b)
print ('{:11.7f} {:11.7f} {:13.9f} {:7.0f} {:7.0f}'.format(frac, r, t-frac, b,rhi**2))
rhi = 3*rhi/2
frac sqrt(b) error b bMax
0.1415927 7.1414284 -0.000164225 51 256
0.1415927 7.1414284 -0.000164225 51 576
0.1415927 7.1414284 -0.000164225 51 1296
0.1415927 7.1414284 -0.000164225 51 2916
0.1415927 7.1414284 -0.000164225 51 6561
0.1415927 120.1415831 -0.000009511 14434 14641
0.1415927 120.1415831 -0.000009511 14434 32761
0.1415927 233.1415879 -0.000004772 54355 73441
0.1415927 346.1415895 -0.000003127 119814 164836
0.1415927 572.1415909 -0.000001786 327346 370881
0.1415927 911.1415916 -0.000001023 830179 833569
我不知道这种问题是否有任何标准算法，但它确实引起了我的兴趣，所以这是我尝试开发一种找到所需近似值的算法。
拨打有问题的真实号码r。然后，首先我假设它a可能是负数，在这种情况下，我们可以减少问题，现在只需要找到一个b使得 的小数部分sqrt(b)是 的小数部分的良好近似值r。现在让我们写成r整数和r = x.y小数部分。xy
Now:
b = r^2
= (x.y)^2
= (x + .y)^2
= x^2 + 2 * x * .y + .y^2
= 2 * x * .y + .y^2 (mod 1)
我们现在只需要（大约）找到一个x这样的。0 = .y^2 + 2 * x * .y (mod 1)
将其填充x到上面的公式中，我们得到b，然后可以计算a为a = r - b。（当然，所有这些计算都必须仔细四舍五入。）
现在，我暂时不确定是否有办法在x不强制使用的情况下找到它。但即便如此，人们也可以简单地使用一个简单的循环来找到一个x足够好的。
我正在考虑这样的事情（半伪代码）：
max_diff_low = 0.01 // arbitrary accuracy
max_diff_high = 1 - max_diff_low
y = r % 1
v = y^2
addend = 2 * y
x = 0
while (v < max_diff_high && v > max_diff_low)
x++;
v = (v + addend) % 1
c = (x + y) ^ 2
b = round(c)
a = round(r - c)
现在，我认为这个算法相当有效，同时甚至允许您指定所希望的近似精度。可以将其变成 O(1) 算法的一件事是计算所有的x并将它们放入查找表中。如果只关心r（例如）的前三位十进制数字，则查找表将只有 1000 个值，即只有 4kb 的内存（假设使用 32 位整数）。
希望这完全有帮助。如果有人发现算法有任何问题，请在评论中告诉我，我会修复它。
编辑：
经过反思，我收回了我对效率的主张。事实上，据我所知，不能保证上述算法会终止，即使终止，也可能需要很长时间才能找到一个x可以充分解决方程的非常大的算法。
人们可能会跟踪x迄今为止发现的最佳算法，并随着时间的推移放宽准确度范围，以确保算法快速终止，但可能会以准确度为代价。
如果简单地预先计算一个查找表，这些问题当然是不存在的。