高精度大数开根（python实现）

jerryxjr1220

对大数有效（仅保留整数部分，有小数的可以移动小数点后再开根）

1. def big_sqrt(n):
   
2.         lst = []
   
3.         res = []
   
4.         while n > 0:
   
5.                 lst.append(n%100)
   
6.                 n //= 100
   
7.         q = lst.pop()
   
8.         for a in range(9,-1,-1):
   
9.                 if a*a<=q:
   
10.                         break
    
11.         res.append(a)
    
12.         if lst:
    
13.                 qq = lst.pop()
    
14.                 remind = (q-a*a)*100+qq
    
15.         else:
    
16.                 remind = (q-a*a)*100
    
17.         while lst:       
    
18.                 for b in range(9,-1,-1):
    
19.                         if (a*20+b)*b <= remind:
    
20.                                 break
    
21.                 res.append(b)
    
22.                 q = lst.pop()
    
23.                 remind = (remind-(a*20+b)*b)*100+q
    
24.                 a = int(''.join([str(i) for i in res]))
    
25.         return a
    
26. print(big_sqrt(200000000000000000000))

复制代码

1414213562
[Finished in 0.1s]

新手·ing

沙发拿下，代码收下~

新手·ing

这个用了numba是什么效果

jerryxjr1220

print(big_sqrt(200000000000000000000000000000000000000000000000000))
import math
print(math.sqrt(200000000000000000000000000000000000000000000000000))
1414213562373095048801688
1.4142135623730952e+25
[Finished in 0.1s]
精度要比原始的math库的开根精度高

jerryxjr1220

新手·ing 发表于 2017-7-20 12:00
这个用了numba是什么效果

这个可以不用numba，用了也没有明显提高
一共就这些位数，循环也就没几次，不必要用numba

新手·ing

jerryxjr1220 发表于 2017-7-20 12:03
这个可以不用numba，用了也没有明显提高
一共就这些位数，循环也就没几次，不必要用numba

恩恩

SixPy

1. >>> import decimal
   
2. >>> n=2*10**50
   
3. >>> decimal.Decimal(n).sqrt()
   
4. Decimal('14142135623730950488016887.24')

复制代码

jerryxjr1220

SixPy 发表于 2017-7-20 12:56

在解欧拉计划的第137题，本来想用大数开根直接算的，不过就算用decimal来提高精度，速度还是不够，解不出来。

SixPy

jerryxjr1220 发表于 2017-7-20 13:39
在解欧拉计划的第137题，本来想用大数开根直接算的，不过就算用decimal来提高精度，速度还是不够，解不出 ...

http://pe-cn.github.io/137/

这题？

jerryxjr1220

SixPy 发表于 2017-7-20 14:17
这题？

是的，本来想用暴力解法直接大数开根求的，后来由于误差问题一直不行。
现在找到其他方法，已经解决啦！
http://bbs.fishc.com/thread-75435-1-5.html

不知道最终可以刷到多少题，感觉后面越来越有难度了。