[开_145-2]计算根号2，比精度比速度[已总结]

cleverzhzhf

{:soso_e113:}只要本月就好~~我就等着这个分，争取第一次的优秀会员了~~{:soso_e113:}

jsxjd

看来这段时间楼主分身无术，以前都是提前总结的。

jsxjd

jsxjd 发表于 2014-1-4 23:28
看来这段时间楼主分身无术，以前都是提前总结的。

再等等楼主吧，这题参与的人就少，做对的更少，而且我感觉楼主可能有独到之见。

lee1892

各位，只能说抱歉了，最近实在忙的晕头转向，而我又不想胡乱写几句，所以只有再延期了，估计20号以后能好些。

lee1892

一、算法：

1、泰勒多项式展开

首先将根号2表达为：

其次根据泰勒多项式展开，有：

则可知：

式中限制P、Q的关系仅是为了计算时的简化，并不是必须的。可以通过代码找出满足这样的关系的P和Q，实际上是佩尔方程，感兴趣的可以去看另一个竞赛贴 [第77期]编写VBA代码解方程。

这样一来，就可以通过迭代计算使得结果的精度不断提高。另外，对于P、Q的值得选择，数字越大，则精度提高或称有效数字的增长速度就越快。很容易就可以获得下列数据：

1. P= 1          Q= 1          N= 2
   
2. P= 5          Q= 7          N= 50
   
3. P= 29         Q= 41         N= 1682
   
4. P= 169        Q= 239        N= 57122
   
5. P= 985        Q= 1393       N= 1940450
   
6. P= 5741       Q= 8119       N= 65918162
   
7. P= 33461      Q= 47321      N= 2239277042
   
8. P= 195025     Q= 275807     N= 76069501250

复制代码

2、牛顿迭代

由牛顿迭代，易知：

按照这个公式，就可以很容易实现迭代结算，其有效数字的增长速度是十分快的，以初始值为1为例，其迭代计算结果如下表

迭代计算序数	结果
1	1.(500...)
2	1.41(666...)
3	1.41421(568...)
4	1.41421356237(468...)

其缺点是需要计算一个超大数的倒数，一个变通的做法是计算根号2的倒数（其等于 sqr(2)/2），同样由牛顿迭代，有：

所获结果乘2即可获得根号2，但不可避免的需要计算两个超大数的乘积，而前面的泰勒展开式的方法则只需要计算超大数和一个Long整形的四则运算。

但其好处是有效数字的增长速度非常快，基本上是每次迭代其有效数字翻倍，下表是牛顿迭代法的迭代次数 n 和其对应得有效数字个数 D

n	1	2	3	4	5	6	7	8	9	10
D	0	2	5	11	24	48	97	195	391	783

还有很多别的方法，就不展开说了，上面这两种是最为常见的方法。

二、超大数计算的技巧及任意精确度小数的计算

1、超大整数的计算

通常程序语言提供的数据类型都会有变量数字大小的限制，VB中的有效计算数字是15位。对于超过这个数量的大数的计算，则可以通过自行编程来解决。

通常的做法是采用数组来计算，将数组理解为一个某进制下的数字，其各元素则代表了该进制下数字的各位上的数。以10进制为例，数组下标由1开始，则下标为1的元素对应个位数，下标2的元素对应十位数，以此类推。

为提高计算效率，通常采用的进制为2的某次方或是10的某次方，取决于诸如程序语言的内存限制、提供的数据类型限制等因素，前者是适合计算机存储计算，而后者则相对更为直观。

以一个超大数与一个LONG整形数间的四则运算为例，加法和乘法是由低位到高位计算，减法和除法则是由高位到低位计算的。与我们小学时学习的竖式计算方法一样，加法和乘法遇到有进位的，则用临时变量保存至下一个元素中参与计算，减法和除法则是碰到有余留的也是同样的方法。

很显然的，两个超大数之间的加减法会是 O(N) 的复杂度，而乘除法则会是 O(N^2) 的复杂度，这也是前面两种算法的一个主要的区别。
值得一提的是两个超大整数的乘法计算可以将复杂度提高到 O(N log(N))，有兴趣的可以查找关键字 Fast Fourier Transform，采用这个方法结合牛顿迭代或是其它类似的高阶迭代方法将会非常快。

2、任意精度小数的计算

一个非常简单的思路转换，在上述的超大整数计算方法中，可以将第一个元素理解为这个小数的整数部分（如果选择的进制基数够覆盖该小数的整数部分），其余的元素则代表了该小数的小数部分，在计算方式上则与整数的计算完全没有区别。

jsxjd

lee1892 发表于 2014-1-20 17:16
一、算法：

1、泰勒多项式展开

难道这题“全军覆没”，怎么还不评分？

香川群子

jsxjd 发表于 2014-2-14 20:09
难道这题“全军覆没”，怎么还不评分？

你用的是什么算法，好像不和前面说的二种一样。

jsxjd

香川群子 发表于 2014-2-28 12:45
你用的是什么算法，好像不和前面说的二种一样。

泰勒展开式
具体的数可视情况而定

lee1892

抱歉拖了这么长时间，不过相信大家都知道结果了

测试结果如下：

1. Testing length: 100
   
2. ----------------------------
   
3.         ID: Lee1892 - Origin Code
   
4. Time Used: 0.0000s
   
5. Calculated: 100 digits of square root 2.
   
6. ----------------------------
   
7.         ID: Lee1892 - Fast Code
   
8. Time Used: 0.0000s
   
9. Calculated: 100 digits of square root 2.
   
10. ----------------------------
    
11.         ID: 香川群子
    
12. Time Used: 0.00s
    
13. Calculated: 100 digits of square root 2.
    
14. ----------------------------
    
15.         ID: cleverzhzhf
    
16. Time Used: 0.00s
    
17. Calculated: 100 digits of square root 2.
    
18. 楼03_cleverzhzhf is OUT for wrong digit too early.
    
19. The wrong digit from number 2
    
20. Right one is 1.41421356
    
21. The answer is 10.0000000
    
22. ----------------------------
    
23.         ID: jsxjd
    
24. Time Used: 0.00s
    
25. Calculated: 100 digits of square root 2.
    
26. ----------------------------
    
27. ID: 苍海拾贝
    
28. Time Used: 0.34s
    
29. Calculated: 100 digits of square root 2.
    
30. ----------------------------
    
31.         ID: doryan
    
32. Time Used: 0.00s
    
33. Calculated: 100 digits of square root 2.
    
34. 楼07_doryan is OUT for wrong digit too early.
    
35. The wrong digit from number 2
    
36. Right one is 1.41421356
    
37. The answer is 10.
    
38. ============================
    
39. Testing length: 300
    
40. ----------------------------
    
41.         ID: Lee1892 - Origin Code
    
42. Time Used: 0.0156s
    
43. Calculated: 300 digits of square root 2.
    
44. ----------------------------
    
45.         ID: Lee1892 - Fast Code
    
46. Time Used: 0.0000s
    
47. Calculated: 300 digits of square root 2.
    
48. ----------------------------
    
49.         ID: 香川群子
    
50. Time Used: 0.03s
    
51. Calculated: 300 digits of square root 2.
    
52. ----------------------------
    
53. 楼03_cleverzhzhf is already OUT.
    
54. ----------------------------
    
55.         ID: jsxjd
    
56. Time Used: 0.00s
    
57. Calculated: 300 digits of square root 2.
    
58. ----------------------------
    
59. ID: 苍海拾贝
    
60. Time Used: 7.72s
    
61. Calculated: 300 digits of square root 2.
    
62. 楼06_苍海拾贝 is OUT for overtime using.
    
63. ----------------------------
    
64. 楼07_doryan is already OUT.
    
65. ============================
    
66. Testing length: 1000
    
67. ----------------------------
    
68.         ID: Lee1892 - Origin Code
    
69. Time Used: 0.0156s
    
70. Calculated: 1000 digits of square root 2.
    
71. ----------------------------
    
72.         ID: Lee1892 - Fast Code
    
73. Time Used: 0.0156s
    
74. Calculated: 1000 digits of square root 2.
    
75. ----------------------------
    
76.         ID: 香川群子
    
77. Time Used: 0.48s
    
78. Calculated: 1000 digits of square root 2.
    
79. ----------------------------
    
80. 楼03_cleverzhzhf is already OUT.
    
81. ----------------------------
    
82.         ID: jsxjd
    
83. Time Used: 0.02s
    
84. Calculated: 1000 digits of square root 2.
    
85. ----------------------------
    
86. 楼06_苍海拾贝 is already OUT.
    
87. ----------------------------
    
88. 楼07_doryan is already OUT.
    
89. ============================
    
90. Testing length: 3000
    
91. ----------------------------
    
92.         ID: Lee1892 - Origin Code
    
93. Time Used: 0.2031s
    
94. Calculated: 3000 digits of square root 2.
    
95. ----------------------------
    
96.         ID: Lee1892 - Fast Code
    
97. Time Used: 0.0469s
    
98. Calculated: 3000 digits of square root 2.
    
99. ----------------------------
    
100.         ID: 香川群子
     
101. Time Used: 9.05s
     
102. Calculated: 3000 digits of square root 2.
     
103. 楼02_香川群子 is OUT for overtime using.
     
104. 楼02_香川群子 is OUT for wrong digit too early.
     
105. The wrong digit from number 2708
     
106. Right one is 9314549999
     
107. The answer is 9314559999
     
108. ----------------------------
     
109. 楼03_cleverzhzhf is already OUT.
     
110. ----------------------------
     
111.         ID: jsxjd
     
112. Time Used: 0.05s
     
113. Calculated: 3000 digits of square root 2.
     
114. ----------------------------
     
115. 楼06_苍海拾贝 is already OUT.
     
116. ----------------------------
     
117. 楼07_doryan is already OUT.
     
118. ============================
     
119. Testing length: 5000
     
120. ----------------------------
     
121.         ID: Lee1892 - Origin Code
     
122. Time Used: 0.5469s
     
123. Calculated: 5000 digits of square root 2.
     
124. ----------------------------
     
125.         ID: Lee1892 - Fast Code
     
126. Time Used: 0.1406s
     
127. Calculated: 5000 digits of square root 2.
     
128. ----------------------------
     
129. 楼02_香川群子 is already OUT.
     
130. ----------------------------
     
131. 楼03_cleverzhzhf is already OUT.
     
132. ----------------------------
     
133.         ID: jsxjd
     
134. Time Used: 0.13s
     
135. Calculated: 5000 digits of square root 2.
     
136. ----------------------------
     
137. 楼06_苍海拾贝 is already OUT.
     
138. ----------------------------
     
139. 楼07_doryan is already OUT.
     
140. ============================
     
141. Testing length: 10000
     
142. ----------------------------
     
143.         ID: Lee1892 - Origin Code
     
144. Time Used: 2.2031s
     
145. Calculated: 10000 digits of square root 2.
     
146. ----------------------------
     
147.         ID: Lee1892 - Fast Code
     
148. Time Used: 0.5313s
     
149. Calculated: 10000 digits of square root 2.
     
150. ----------------------------
     
151. 楼02_香川群子 is already OUT.
     
152. ----------------------------
     
153. 楼03_cleverzhzhf is already OUT.
     
154. ----------------------------
     
155.         ID: jsxjd
     
156. Time Used: 0.47s
     
157. Calculated: 10000 digits of square root 2.
     
158. ----------------------------
     
159. 楼06_苍海拾贝 is already OUT.
     
160. ----------------------------
     
161. 楼07_doryan is already OUT.
     
162. ============================

复制代码

ID	正确计算	计算任意长度	4秒计算万位	优秀代码	奖励合计
香川群子	√	√			2 技术分
cleverzhzhf					参与比赛财富奖励
jsxjd	√	√	√	√	4 技术分
苍海拾贝	√	√			2 技术分
doryan					参与比赛财富奖励

香川的代码在2708位会出现错误，不知是何原因