LeetCode
登録して1問だけ解いた．競プロみたいに言語間での公平性を保証する必要がないため，標準入力のパースは不要で関数を定義するというスタイルが新鮮．
LeetCode - The World’s Leading Online Programming Learning Platform
これはどんどん解いていきたい．
sin1の近似値
MD5のこれに関して．
This step uses a 64-element table T[1 … 64] constructed from the
sine function. Let T[i] denote the i-th element of the table, which
is equal to the integer part of 4294967296 times abs(sin(i)), where i
is in radians. The elements of the table are given in the appendix.
区間 [ 0 , a ] ∈ R [0,a]\in\mathbb{R} [ 0 , a ] ∈ R C n + 1 C^{n+1} C n + 1 f ( x ) f(x) f ( x )
f ( x ) = ∑ k = 0 n f ( 0 ) k ! x k + f ( c ) ( n + 1 ) ! x n + 1 f(x) = \sum_{k=0}^n \frac{f(0)}{k!}x^k + \frac{f(c)}{(n+1)!}x^{n+1} f ( x ) = k = 0 ∑ n k ! f ( 0 ) x k + ( n + 1 )! f ( c ) x n + 1 を満たすc ∈ ( 0 , a ) c\in(0,a) c ∈ ( 0 , a ) f ( x ) = sin x f(x)=\sin x f ( x ) = sin x n n n 2 n + 1 2n+1 2 n + 1 x > 0 x > 0 x > 0
sin x = ∑ k = 0 n ( − 1 ) k x 2 k + 1 ( 2 k + 1 ) ! + ( − 1 ) n + 1 sin c x 2 n + 3 ( 2 n + 3 ) ! \sin x = \sum_{k=0}^n \frac{(-1)^kx^{2k+1}}{(2k+1)!} + \frac{(-1)^{n+1}\sin c\, x^{2n+3}}{(2n+3)!} sin x = k = 0 ∑ n ( 2 k + 1 )! ( − 1 ) k x 2 k + 1 + ( 2 n + 3 )! ( − 1 ) n + 1 sin c x 2 n + 3 を満たす c ∈ ( 0 , x ) c\in (0,x) c ∈ ( 0 , x ) ∥ sin x ∥ ≤ 0 \|\sin x\|\leq 0 ∥ sin x ∥ ≤ 0
∣ sin x − ∑ k = 0 n ( − 1 ) k x 2 k + 1 ( 2 k + 1 ) ! ∣ ≤ x 2 n + 3 ( 2 n + 3 ) ! \left|\sin x-\sum_{k=0}^n \frac{(-1)^kx^{2k+1}}{(2k+1)!}\right| \leq \frac{x^{2n+3}}{(2n+3)!} sin x − k = 0 ∑ n ( 2 k + 1 )! ( − 1 ) k x 2 k + 1 ≤ ( 2 n + 3 )! x 2 n + 3 という，sin \sin sin
∣ cos x − ∑ k = 0 n ( − 1 ) k x 2 k ( 2 k ) ! ∣ ≤ x 2 n + 2 ( 2 n + 2 ) ! . \left|\cos x-\sum_{k=0}^n \frac{(-1)^kx^{2k}}{(2k)!}\right| \leq \frac{x^{2n+2}}{(2n+2)!}. cos x − k = 0 ∑ n ( 2 k )! ( − 1 ) k x 2 k ≤ ( 2 n + 2 )! x 2 n + 2 . OK．
さてx = 1 x=1 x = 1 π / 3 \pi/3 π /3
sin 1 ≃ 3 / 2 = 0.866 ⋯ , cos 1 ≃ 1 / 2 = 0.5 \begin{align}
\sin 1&\simeq \sqrt{3}/2=0.866\cdots,\\
\cos 1&\simeq 1/2=0.5
\end{align} sin 1 cos 1 ≃ 3 /2 = 0.866 ⋯ , ≃ 1/2 = 0.5 になるはずである．誤差項がx x x
∣ sin 1 − 5 6 ∣ ≤ 1 120 , ∣ cos 1 − 13 24 ∣ ≤ 1 120 \begin{align}
\left|\sin 1 - \frac{5}{6}\right| &\leq \frac{1}{120},\\
\left|\cos 1 - \frac{13}{24}\right| &\leq \frac{1}{120}
\end{align} sin 1 − 6 5 cos 1 − 24 13 ≤ 120 1 , ≤ 120 1 から
sin 1 ∈ [ 100 120 , 101 120 ] , cos 1 ∈ [ 65 120 , 66 120 ] \begin{align}
\sin 1\in \left[\frac{100}{120},\, \frac{101}{120}\right],\\
\cos 1\in \left[\frac{65}{120},\, \frac{66}{120}\right]
\end{align} sin 1 ∈ [ 120 100 , 120 101 ] , cos 1 ∈ [ 120 65 , 120 66 ] が分かる．
一方，x = 1 / 2 x=1/2 x = 1/2
sin 1 2 ∈ [ 23 48 , 23 48 + 1 120 ⋅ 2 5 ] , cos 1 2 ∈ [ 337 384 , 337 384 + 1 120 ⋅ 2 5 ] \begin{align}
\sin \frac{1}{2} \in \left[\frac{23}{48},\, \frac{23}{48}+\frac{1}{120\cdot 2^5}\right],\\
\cos \frac{1}{2} \in \left[\frac{337}{384},\, \frac{337}{384}+\frac{1}{120\cdot 2^5}\right]
\end{align} sin 2 1 ∈ [ 48 23 , 48 23 + 120 ⋅ 2 5 1 ] , cos 2 1 ∈ [ 384 337 , 384 337 + 120 ⋅ 2 5 1 ] 倍角公式から，
sin 1 = 2 sin 1 2 cos 1 2 ∈ [ 7751 9216 , 6206011 7372800 ] , cos 1 = cos 2 1 2 − sin 2 1 2 ∈ [ 885291 1638400 , 886449 1638400 ] . \begin{align}
\sin 1 = 2\sin \frac{1}{2}\cos\frac{1}{2}
&\in\left[
\frac{7751}{9216},\,
\frac{6206011}{7372800}
\right],\\
\cos 1 = \cos^2\frac{1}{2}-\sin^2\frac{1}{2}
&\in\left[
\frac{885291}{1638400},
\frac{886449}{1638400}
\right].
\end{align} sin 1 = 2 sin 2 1 cos 2 1 cos 1 = cos 2 2 1 − sin 2 2 1 ∈ [ 9216 7751 , 7372800 6206011 ] , ∈ [ 1638400 885291 , 1638400 886449 ] . あえて厳密に有理数として計算する．すると区間の幅はどちらも579 819200 \frac{579}{819200} 819200 579
この逆数が1414.8 ⋯ 1414.8\cdots 1414.8 ⋯ x = 1 x=1 x = 1 6 6 6
というのは次数が低いからで，次数が高いほどx = 1 / 2 x=1/2 x = 1/2
0に十分近いx x x
sin x ∈ [ a n − 1 , a n − 1 + x n n ! ] , cos x ∈ [ b n − 1 , b n − 1 + x n n ! ] , sin x 2 ∈ [ a n − 1 ′ , a n − 1 ′ + x n 2 n n ! ] , cos x 2 ∈ [ b n − 1 ′ , b n − 1 ′ + x n 2 n n ! ] \begin{aligned}
\sin x &\in \left[a_{n-1}, a_{n-1}+\frac{x^n}{n!}\right],&
\cos x &\in \left[b_{n-1}, b_{n-1}+\frac{x^n}{n!}\right],\\
\sin \frac{x}{2} &\in \left[a'_{n-1}, a'_{n-1}+\frac{x^n}{2^nn!}\right],&
\cos \frac{x}{2} &\in \left[b'_{n-1}, b'_{n-1}+\frac{x^n}{2^nn!}\right]
\end{aligned} sin x sin 2 x ∈ [ a n − 1 , a n − 1 + n ! x n ] , ∈ [ a n − 1 ′ , a n − 1 ′ + 2 n n ! x n ] , cos x cos 2 x ∈ [ b n − 1 , b n − 1 + n ! x n ] , ∈ [ b n − 1 ′ , b n − 1 ′ + 2 n n ! x n ] の場合に後者の2倍角から計算したときの区間幅は
2 ( a n − 1 ′ + b n − 1 ′ + x n 2 n n ! ) x n 2 n n ! < x n 2 n − 2 n ! 2\left(a'_{n-1}+b'_{n-1}+\frac{x^n}{2^n n!}\right)\frac{x^n}{2^n n!}
< \frac{x^n}{2^{n-2} n!} 2 ( a n − 1 ′ + b n − 1 ′ + 2 n n ! x n ) 2 n n ! x n < 2 n − 2 n ! x n だから，冪で区間幅の縮小は速くなる．
しかし，十分大きなn n n sin ( 1 / 2 ) \sin (1/2) sin ( 1/2 ) sin 1 \sin 1 sin 1 sin 1 \sin 1 sin 1
実際にやれよという話で，やりたい．が準備が足りない．
一旦2 32 sin 1 2^{32} \sin 1 2 32 sin 1
12 ! = 479001600 < 2 32 = 4294967296 < 13 ! = 6227020800 12! = 479001600 < 2^{32} = 4294967296 < 13 != 6227020800 12 ! = 479001600 < 2 32 = 4294967296 < 13 ! = 6227020800 なので，13 13 13
a 12 = 1 − 1 3 ! + 1 5 ! − 1 7 ! + 1 9 ! − 1 11 ! = 33588829 39916800 a_{12} = 1 - \frac{1}{3!} + \frac{1}{5!} - \frac{1}{7!} + \frac{1}{9!} - \frac{1}{11!} = \frac{33588829}{39916800} a 12 = 1 − 3 ! 1 + 5 ! 1 − 7 ! 1 + 9 ! 1 − 11 ! 1 = 39916800 33588829 sin 1 ∈ [ a 12 , a 12 + 1 13 ! ] \sin 1 \in
\left[
a_{12},\
a_{12} + \frac{1}{13!}
\right] sin 1 ∈ [ a 12 , a 12 + 13 ! 1 ] から，
⌊ 2 32 sin 1 ⌋ ∈ [ 3614090359. … , 3614090360. … ] . \lfloor 2^{32}\sin 1 \rfloor
\in \left[
3614090359.\ldots,
3614090360.\ldots
\right]. ⌊ 2 32 sin 1 ⌋ ∈ [ 3614090359. … , 3614090360. … ] . 「精度は足りる」←嘘だった．
a 13 : = 1 − 1 3 ! + 1 5 ! − 1 7 ! + 1 9 ! − 1 11 ! + 1 13 ! = 209594293 249080832 a_{13} := 1 - \frac{1}{3!} + \frac{1}{5!} - \frac{1}{7!} + \frac{1}{9!} - \frac{1}{11!} + \frac{1}{13!} =\frac{209594293}{249080832} a 13 := 1 − 3 ! 1 + 5 ! 1 − 7 ! 1 + 9 ! 1 − 11 ! 1 + 13 ! 1 = 249080832 209594293 まで精度を上げると，
⌊ 2 32 a 13 ⌋ = ⌊ 2 32 ( a 13 + 1 14 ! ) ⌋ = 3614090360 \left\lfloor 2^{32}a_{13} \right\rfloor
=\left\lfloor 2^{32}\left(a_{13}+\frac{1}{14!}\right)\right\rfloor
=3614090360 ⌊ 2 32 a 13 ⌋ = ⌊ 2 32 ( a 13 + 14 ! 1 ) ⌋ = 3614090360 から，2 32 sin 1 2^{32}\sin 1 2 32 sin 1 3614090360 3614090360 3614090360 d76aa478.
RFC1321中のMD5のCによる実装（p.12 )を見ると，この値がしっかり現れている．
/* Round 1 */ FF (a, b, c, d, x [ 0 ], S11, 0x d76aa478 ); /* 1 */ 2 32 sin 64 2^{32}\sin 64 2 32 sin 64 1 1 1 171 171 171
64 171 171 ! < 1 < 64 170 170 ! . \frac{64^{171}}{171!} < 1 < \frac{64^{170}}{170!}. 171 ! 6 4 171 < 1 < 170 ! 6 4 170 . この171 171 171 64 e ≃ 174 64\,e\simeq 174 64 e ≃ 174 2 32 sin 64 2^{32}\sin 64 2 32 sin 64 192 192 192
……とはいってもせいぜい100桁オーダーなので数式処理システムは難なくやってのけてしまうが．ただ分母にどんどん値の評価に本質的ではない素因数が蓄積してしまうのが気持ち良くない．
精度保証付き数値計算
精度保証付き数値計算における四則演算の基本は数を「区間」として操作することで，区間演算という．区間演算の遂行には丸めの方向を厳密に取り扱う必要があるが，浮動小数点数は丸めの方向が実装依存になっているためそのままでは実現できない．
演算子オーバーロードによって区間演算を行えるC++のライブラリがある．
kv - a C++ Library for Verified Numerical Computation
作成者のwebサイト．数値計算の専門家．
区間演算の実装について(1) - kashiの日記
この記事が面白かった．
調和級数の部分和で遊んでみた - kashiの日記
非整数に対する数値計算による厳密な結果というものについて驚くほど何も知らないことに気付く．円周率の計算の世界記録が具体的に何をやっているか実際のところを何も知らない．何桁目の数が何であるか確定させるのはどんな誤差評価に基づいているのだろうか．どんな形式で数値を持つのだろうか．
Rust本読めてない！ また明日．