回答編集履歴
1
ざっくりとした説明追加
test
CHANGED
|
@@ -17,3 +17,47 @@
|
|
|
17
17
|
TLEのほうは、おそらく距離の計算でしょう。
|
|
18
18
|
|
|
19
19
|
平方根の計算には、それなりに時間がかかりそうです。
|
|
20
|
+
|
|
21
|
+
|
|
22
|
+
|
|
23
|
+
---
|
|
24
|
+
|
|
25
|
+
|
|
26
|
+
|
|
27
|
+
もう少し分かりやすい三角形をベースに、ざっくりとした説明を試みます。
|
|
28
|
+
|
|
29
|
+
|
|
30
|
+
|
|
31
|
+
座標(x,0)(-x,0)(0,1)からなる二等辺三角形を考えます(x>0)。
|
|
32
|
+
|
|
33
|
+
そうすると、底辺の長さが2x、斜辺の長さが√(x^2+1)となります。
|
|
34
|
+
|
|
35
|
+
|
|
36
|
+
|
|
37
|
+
ここで、xは10^9以下なので、x^2は最大20桁になりますが、floatの有効桁は16桁弱なので、表現しきれません。
|
|
38
|
+
|
|
39
|
+
そうなると、x^2に+1したとしても変化が少なすぎて表現しきれず、x^2のままとなります。
|
|
40
|
+
|
|
41
|
+
よって、xが大きい場合、この三角形の斜辺はxとなり、三角形の条件を満たさなくなります。
|
|
42
|
+
|
|
43
|
+
|
|
44
|
+
|
|
45
|
+
実際には、x=67108864にて斜辺の長さがxと等しくなります。
|
|
46
|
+
|
|
47
|
+
x^2はfloatの有効桁の限界まで到達していませんが、sqrt後の値とxとの差が限界を超えたのでしょう。
|
|
48
|
+
|
|
49
|
+
実際、直前の67108863での計算結果は、16桁の数値となっています。
|
|
50
|
+
|
|
51
|
+
```python
|
|
52
|
+
|
|
53
|
+
>>> import math
|
|
54
|
+
|
|
55
|
+
>>> math.sqrt(67108863*67108863+1)
|
|
56
|
+
|
|
57
|
+
67108863.00000001
|
|
58
|
+
|
|
59
|
+
>>> math.sqrt(67108864*67108864+1)
|
|
60
|
+
|
|
61
|
+
67108864.0
|
|
62
|
+
|
|
63
|
+
```
|