Wil*_*sch 7 language-agnostic algorithm math
假设我有一个实数.我想用整数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.因此你的答案是:
SQRT(51)-4
作为最接近的近似值,ab <100,其偏离0.00016.如果你允许更大的b,那么你可以获得更好的近似值.
使用CF的优势在于它比使用双倍或使用浮点更快.例如,在上面的例子中,你只需要比较两个整数(7和15),你也可以使用索引来快速找到表中最近的条目.