求n次方根的整数部分
本文关键字：整数部 方根 | 更新日期: 2023-09-27 17:50:43
我在c#中实现了一个大整数类(学校项目)，我必须计算n次方根。我尝试过二分搜索，但是对于非常大的整数，它花费的时间太长了。我也试着实现牛顿法。问题是，我的除法函数只返回整数部分，没有数字。牛顿法需要用数字进行除法运算。我的愿望是找到一种方法，只从第n根得到整数部分。
牛顿法
N(x) = x - (x^n-a)/(n*x^(n-1))=( (n-1)*x + a/(x^(n-1)))/n
对于整数运算也应该能很好地工作。你可能需要更正结果+ 1。
使用一个好的初值是很重要的，因为离根很远，n次多项式的牛顿方法的收敛性是几何的。与因子(1-1/n)线性，因此对于较大的n值非常慢。
以B为基数，对于整数x, d位集合为q=d/n，通过截断数字序列转换成浮点数计算rx=x/B^(n*q)，用浮点数计算ry=pow(rx, 1.0/n)，并将y=ry*B^q转换成大整数格式作为第一个近似根。
请报告使用此方法时遇到的问题。
您也可以尝试实现http://en.wikipedia.org/wiki/Shifting_nth_root_algorithm