开方术 译自维基百科.doc

开方术 puting_square_roots
http://en./wiki/puting_square_roots
在数学的一个分支——数值分析学科中,有许多开平方的算法或计算非负实数平方根方法。对于负数或复数的平方根,本文最后有涉及。
计算等价于解方程。因此,一般求根算法都可以应用在这里。比如,牛顿法,在这里简化为巴比伦方法:
通常,这些方法产生近似的结果。为了得到一个更精确的根,我们需要进行很多步的迭代计算。
粗略估计
许多平方根算法需要一个初始估计值。如果这个初始值远离实际的平方根,算法运算起来将会慢一些。因此粗略估计是非常有用的,可能结果是非常错误的,但很容易用来继续计算。利用S的科学计数法,如,平方根可以被估计为
因子2和6常被使用,因为他们近似于给出数字最低和最高可能的值的几何平均值:
和
举例来说,对于,估计值就是。
对于二进制运算系统……二进制方法暂略
这个方法对找到一个迭代算法的初始值非常有帮助,可以有助于快速收敛收敛可看做不断接近
。
巴比伦方法
可能第一个已知的近似开平方的方法就是巴比伦人的巴比伦方法了(或者以一世纪希腊数学家希罗命名的希罗法,他第一次明确描述了这个方法)。它可以由牛顿法演化而来(但比牛顿法早了很多)。基本的想法就是如果非负实数S的平方根x估计过高,那么就会过低,所以取其平均值作为更近的估计值(尽管正式证明表明这个平均值将永远高于平方根准确值,但它可以保证是收敛的)。
更精确地说,如果x是初始猜测值,e是估计值得偏差(),我没刻意展开二项式:
,因为。“:=”冒号等号表示赋值
因此,我们可以更新旧的估计值:
这将成为我没下一个猜测。这个过程不断迭代直到达到需要的精确度。这是个二次收敛算法,即准确数字的位数随每次迭代大致加倍。过程如下:
以任意一个数值开始(越接近实际值越好)。
把赋值为和的平均值(使用算术平均值来接近几何平均值)。
重复步骤2直到达到精确度。
方法可以表示为:
这个算法同样可以很好地用在P进数中……不懂,待译
例
所以
收敛证明
收敛最坏情形暂略
逐位计算
这是一个寻找平方根结果的每一位数字的方法。它比巴比伦法要慢,但有如下优势:
更易于人工计算。
每一位计算出的平方根数字都是准确的,也就是说,算出一位后后面的计算不会影响这一位。
如果某数是完全平方数,这个方法会随答案算出而终止。因此它易于判断完全平方数。
这个方法对任意进制都通用,不过计算流程会有所差异。
Napier的骨头类似算盘的工具
可以用来执行这个算法。Shifting nth root algorithm 未发现中文翻译,大概译为移根算法(用于n次方根求解)
是这个方法的推广。
基本原理
假设我们通过把N表示为n个数字的和的平方来寻找平方根:
应用二项式定理:
这个表达式可以让我们通过连续的猜测找到的值。每一个猜测需要满足下列递归式:
当,确切的平方根就被算出来了;否则,每一个给出的可以构成近似的平方根值。
例
假设我们要找某五位数的平方根。这里的1,10,100用来表示三位数。每次递归,我们从0到9中猜测的值。
寻找第一个数使尽可能接近。即寻找最大的满足
寻找第二个数,使尽可能接近。即寻找最大的满足
最后,寻找最后一个数,使尽可能接近。即寻找最大的满足
如果N为完全平方数,则。否则,我们可以得到一个平方根的近似值(或增加小数位数得到更精确的近似值)。
对于二进制运算系统……二进制方法暂略
十进制列式算法详细内容建议阅读./469614686/blog/1334934689
指数恒等式
计算器一般引用了很好的运算指数和自然对数的方法,然后我们可以利用自然对数()和指数()求平方根:
分数的分母对应n次方根。上述情形分母为2,因此可以求出平方根。我们可以利用对数表或计算尺来应用这一恒等式。
巴赫沙里近似法
这个计算近似平方根的方法是出自古印度数学手稿《巴赫沙里手稿》。它等价于巴比伦法两次迭代。原始描述为:计算,令N2为尽可能接近S的完全平方。然后,计算:
这也可以写作
例
求
吠陀Duplex未找到合适翻译
法
这个方法是古印度的方法。它是逐位计算方法的变式。
Duplex是一个数(商)中间数字的平方加上首位对应数字(与中心等距的2个数字)积的两倍。这个数一般是当前商除去第一位的各位数字。Duplex将会被初始被除数减去得到最终的被除数。我们将通过这些信息议商(即不断尝试0到9的数字,使该位商最大且符合要求)。
Duplex算法
原数=> 计算过程= Duplex
574 => 2*(5*4)+72 = 89
406739 => 2*(4*9)+2