logo标签列表

将实数转化为根式

algorithmmathlanguage-agnostic
7
假设我有一个实数。我想用形如a+sqrt(b)的东西来近似它，其中a和b是整数。但我不知道a和b的值。当然，我希望用小的a和b得到一个好的近似值。现在先不定义“好”和“小”的含义。任何合理的定义都可以。
有没有一种明智的方法来找到它们？类似于寻找小数的分数近似的连分数算法。有关分数问题的更多信息，请参见此处。
编辑：为了澄清，这是一个任意的实数。我只有一堆数字。因此，根据我们想要的近似度，a和b可能存在，也可能不存在。暴力破解自然不是特别好的算法。我想到的最好的方法是从我的实数开始加整数，平方结果，并查看是否接近整数。基本上就是暴力破解，而且不是特别好的算法。但如果没有更好的方法，那本身也是很有趣的。
编辑：显然，b必须为零或正数。但a可以是任何整数。
有两件事情我不太清楚：1- 你最初的实数是以什么形式呈现的；2- 考虑到天真、蛮力算法假设算术操作为常数时间，以 O(r) 的时间复杂度给出最佳答案，那么你认为“明智”的算法是什么？（除非你允许参数 a 为负数，否则蛮力算法无法解决） - Pascal Cuoq
是的，更好地描述您的实数将会很有帮助。一些实数无法用a+sqrt(b)这样的形式表示，例如圆周率。 - ckb
a和b应该是正整数吗？ - Tyler Durden
我的答案中的方法每次查询使用O(sqrt(n))时间，O(1)空间，而你接受的BlueRaja的答案使用O(n)空间，O(n)设置时间和O(ln n)查询时间。(n = 最大的“小值”) - James Waldby - jwpat7
CF表的平方根需要设置时间。除非我漏掉了什么。 - William Jockusch
5个回答
6
不需要连分数；只需计算所有“小”的b值（直到您认为仍然足够“小”为止）的平方根，删除小数点前面的所有内容，并将它们全部排序/存储（以及生成它的b）。
然后，当您需要近似一个实数时，找到其小数部分最接近实数小数部分的根。这就给出了b - 选择正确的a只是简单的减法问题。
我很惊讶，在写我的答案时，我主要关注的是“好”的优化，而你则是在优化“小”的方面。我根本没有考虑过那种方法。 - amulware
5
这实际上更像是一个数学问题而不是计算机问题，但为了回答这个问题，我认为您是正确的，您可以使用连分数。首先将目标数字表示为连分数。例如，如果您想近似π（3.14159265），则连分数为：
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。因此，您的答案将是：
sqrt（51）-4
作为给定b＜100的最接近的近似值，差0.00016。如果允许较大的b，则可以获得更好的近似值。
使用CF的优点是它比使用浮点数，例如double，更快。例如，在上面的情况下，您只需要比较两个整数（7和15），并且您还可以使用索引使查找表中最接近的条目非常快。
同样是一个优秀的答案。它的优点是可以扩展到其他问题上。但我已经接受了我认为最适合所提出问题的答案。 - William Jockusch
1
这可以通过使用混合整数二次规划非常高效地完成（尽管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完全问题，如果是的话，证明会很有趣。

1

之前的一些答案使用的方法时间或空间复杂度为O(n)，其中n是最大可接受的“小数”。相比之下，以下方法的时间复杂度为O(sqrt(n))，空间复杂度为O(1)。

假设正实数r = x + y，其中x=floor(r)且0 ≤ y < 1。我们想要用形如a + √b的数字来近似r。如果x+y ≈ a+√b，那么x+y-a ≈ √b，因此√b ≈ h+y，其中h是某个整数偏移量，b ≈ (h+y)^2。为了使b成为整数，我们希望在所有合适的h中最小化(h+y)^2的小数部分。有至多√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的完全平方值，除了值为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
0

我不知道是否有任何标准算法可以解决这种问题，但它确实让我感到好奇，所以我尝试开发一种算法来找到所需的近似值。

将所涉及的实数称为r。首先，我假设a可以是负数，在这种情况下，我们可以简化问题，现在只需要找到一个b，使得sqrt(b)的小数部分是r的一个很好的近似值。现在，让我们将r写成r = x.y，其中x是整数，y是小数部分。

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)

现在，我认为这个算法相当有效，甚至允许您指定所需的近似精度。可以做的一件事是计算所有的x并将它们放入查找表中，从而将其转换为O(1)算法。如果只关心r的前三个小数位（例如），则查找表只有1000个值，这仅仅是4kb的内存（假设使用32位整数）。

希望这对您有所帮助。如果有人发现算法有误，请在评论中告诉我，我会进行修正。

编辑： 经过反思，我撤回了自己的高效性声明。实际上，据我所知，上述算法没有任何保证会终止，即使它终止，找到一个足够解方程的非常大的x可能需要很长时间。

也许可以跟踪到目前为止找到的最佳x，并随着时间的推移放松精度界限，以确保算法快速终止，但有可能牺牲精度。

当然，如果简单地预先计算查找表，则不存在这些问题。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接