生成2的平方根数字
我想生成两到三百万个数字的平方根数字。
我知道Newton-Raphson，但由于缺乏大整数支持，我不知道如何在C或C ++中实现它。有人能指出我正确的方向吗？
另外，如果有人知道如何在python中做到这一点（我是初学者），我也会很感激。
没有找到相关结果
已邀请:
9 个回复
镶骄册筷
以开头。这收敛于sqrt（2）（实际上给出了它的连续分数表示）。 现在关键点：这可以表示为矩阵乘法（类似于斐波那契） 如果a_n和b_n是步骤中的第n个数字 [1 2] [a_n b_n] T = [a_（n + 1）b_（n + 1）] T [1 1] 现在给了我们 [1 2] n [a_1 b_1] T = [a_（n + 1）b_（n + 1）] T [1 1] 因此，如果2x2矩阵是A，我们需要计算An，这可以通过重复平方来完成，并且只使用整数运算（因此您不必担心精度问题）。 另请注意，您获得的a / b将始终为缩小形式（如gcd（a，b）= gcd（a + 2b，a + b）），因此如果您考虑使用分数类来表示中间体结果，不要！ 由于第n个分母类似于（1 + sqrt（2））^ n，要获得300万个数字，您可能需要计算直到第3671656个术语。 请注意，即使您正在寻找~360万个术语，重复平方也可以让您计算O（Log n）乘法和加法中的第n项。 此外，这可以很容易地平行，不像像Newton-Raphson等迭代的那样。厢界山攀
def sqrt_list(n, precision): ndigits = [] # break n into list of digits n_int = int(n) n_fraction = n - n_int while n_int: # generate list of digits of integral part ndigits.append(n_int % 10) n_int /= 10 if len(ndigits) % 2: ndigits.append(0) # ndigits will be processed in groups of 2 decimal_point_index = len(ndigits) / 2 # remember decimal point position while n_fraction: # insert digits from fractional part n_fraction *= 10 ndigits.insert(0, int(n_fraction)) n_fraction -= int(n_fraction) if len(ndigits) % 2: ndigits.insert(0, 0) # ndigits will be processed in groups of 2 rootlist = [] root = carry = 0 # the algorithm while root == 0 or (len(rootlist) < precision and (ndigits or carry != 0)): carry = carry * 100 if ndigits: carry += ndigits.pop() * 10 + ndigits.pop() x = 9 while (20 * root + x) * x > carry: x -= 1 carry -= (20 * root + x) * x root = root * 10 + x rootlist.append(x) return rootlist, decimal_point_index掀辟髓观粟
赣借
厘恼轨
的平方根。def root_two_cf_expansion(): yield 1 while True: yield 2 def z(a,b,c,d, contfrac): for x in contfrac: while a > 0 and b > 0 and c > 0 and d > 0: t = a // c t2 = b // d if not t == t2: break yield t a = (10 * (a - c*t)) b = (10 * (b - d*t)) # continue with same fraction, don't pull new x a, b = x*a+b, a c, d = x*c+d, c for digit in rdigits(a, c): yield digit def rdigits(p, q): while p > 0: if p > q: d = p // q p = p - q * d else: d = (10 * p) // q p = 10 * p - q * d yield d def decimal(contfrac): return z(1,0,0,1,contfrac)返回所有小数位的迭代器。算法中的和是下一个数字的最小值和最大值。当它们相等时，我们输出该数字。 请注意，这不会处理某些特殊情况，例如连续分数中的负数。 （此代码是Haskell代码的改编，用于处理已经浮动的连续分数。）恋卡
def sqroot(a, digits): a = a * (10**(2*digits)) x_prev = 0 x_next = 1 * (10**digits) while x_prev != x_next: x_prev = x_next x_next = (x_prev + (a // x_prev)) >> 1 return x_next烫珊
def sqrt(number,digits_after_decimal=20): import time start=time.time() original_number=number number=str(number) list=[] for a in range(len(number)): if number[a]=='.': decimal_point_locaiton=a break if a==len(number)-1: number+='.' decimal_point_locaiton=a+1 if decimal_point_locaiton/2!=round(decimal_point_locaiton/2): number='0'+number decimal_point_locaiton+=1 if len(number)/2!=round(len(number)/2): number+='0' number=number[:decimal_point_locaiton]+number[decimal_point_locaiton+1:] decimal_point_ans=int((decimal_point_locaiton-2)/2)+1 for a in range(0,len(number),2): if number[a]!='0': list.append(eval(number[a:a+2])) else: try: list.append(eval(number[a+1])) except IndexError: pass p=0 c=list[0] x=0 ans='' for a in range(len(list)): while c>=(20*p+x)*(x): x+=1 y=(20*p+x-1)*(x-1) p=p*10+x-1 ans+=str(x-1) c-=y try: c=c*100+list[a+1] except IndexError: c=c*100 while c!=0: x=0 while c>=(20*p+x)*(x): x+=1 y=(20*p+x-1)*(x-1) p=p*10+x-1 ans+=str(x-1) c-=y c=c*100 if len(ans)-decimal_point_ans>=digits_after_decimal: break ans=ans[:decimal_point_ans]+'.'+ans[decimal_point_ans:] total=time.time()-start return ans,total队辅坟阮阶
死搭胯
def isqrt(n): x = (n >> n.bit_length() // 2) + 1 result = (x + n // x) // 2 while abs(result - x) > 1: x = result result = (x + n // x) // 2 while result * result > n: result -= 1 return result