证明
platelett
·
·
个人记录
定理：令 p=\lceil\frac km\times2^{64}\rceil, 当 a_i\le \frac{2^{64}}m 时，下取整的计算结果是准确的。
证明：设 \frac p{2^{64}}=\frac km+\epsilon，其中 \epsilon\in[0,\frac1{2^{64}})。
\begin{aligned}
\lfloor\{a_i\times \frac p{2^{64}}\}\times m\rfloor&=\lfloor\{a_i\times (\frac km+\epsilon)\}\times m\rfloor\\
&=\lfloor\{a_i\times \frac km+a_i\epsilon\}\times m\rfloor
\end{aligned}
这里如果 \lfloor a_i\times\frac km+a_i\epsilon\rfloor>\lfloor a_i\times \frac km\rfloor 肯定就寄了，a_i\times \frac km 距离 \lfloor a_i\times\frac km\rfloor+1 至少有 \frac1m，所以只要 a_i\epsilon<\frac1m 就 OK，继续推式子。
\begin{aligned}
&=\lfloor\{a_i\times \frac km+a_i\epsilon\}\times m\rfloor\\
&=\big\lfloor\left(\{a_i\times \frac km\}+a_i\epsilon\right)m\big\rfloor\\
&=\lfloor\{a_i\times \frac km\}\times m+a_im\epsilon\rfloor
\end{aligned}
由于 \{a_i\times\frac km\}\times m 是整数，所以只要 a_im\epsilon<1 结果就是准确的。