一个插值相关的简单的整除问题

近段时间在写动作捕获数据插值相关的代码，在插值的过程中遇到了一点关于整除的问题。

该问题来源于以下场景：

对一条动作捕获数据的轨迹 \(D = \left\{ s_0, s_1, s_2, ..., s_n \right\}\), 数据的采样间隔为 \(t_m\) ，现在需要通过插值来将这条动作轨迹的采样间隔降低为 \(t\) （\(t_m > t\)）。现已有两个数据点之间的均匀插值算法 \(I\)（具体实现与该问题无关）： \(\left\{ s'_0, s'_1, ..., s'_{m - 1}, s'_{m} \right\} = I\left(s_{i}, s_{i + 1}, m\right)\)。 问如何给定上述插值算法的参数 \(m\) ，使得插值后，两点之间的 \(m + 1\) 个点能够完整覆盖原先的采样间隔？

对上述问题进行抽象，记数据采样间隔为 \(N = t_m\)，要求采样间隔为 \(n = t\)，插值算法参数为 \(m\)。则上述问题转化为：给定两个数 \(N\) 和 \(n\)，它们满足关系 \(N >> n\)，求一个整数 \(m\)，使得：

\[ \begin{align} n\cdot m &\geq N \\ n\cdot (m-1) &< N \end{align} \]

对这个问题，第一反应大概会是这个表达式：

\[ m = \left[ \frac{N}{n} \right] \]

对于能够整除的情况，如 \(N=0.25\)，\(n=0.05\)。则根据上述的算法， \(m = 5\)，符合需求。但是当不能整除时，如 \(N=0.25\)，\(n=0.04\)，则计算得到 \(m = 5\)，采样得到的点的数量并不能覆盖整个采样间隔。类似的问题存在与下面的两个表达式：

\[ m = \left[ \frac{N}{n} \right] + 1 \]

和

\[ m = \left[ \frac{N}{n} + 0.5 \right] \]

所以似乎常见的整除相关的表达式都不能完美地解决这个问题。下面根据取整符号的性质来推导出正确的表达式。

对于取整符号 \(\left[\right]\) ，有以下的性质

\[ \text{For}\, m'=\left[ \frac{N'}{n'} \right],\, m' \, \text{satisfies}\\ m'\cdot n' \leq N' < (m'+1)\cdot n' \tag{1} \]

而我们期望的结果为：

\[ n\cdot (m-1) < N \leq n\cdot m \tag{2} \]

可以观察到目标结果和取整符号之间存在一定的差异，所以对期望结果进行等效变换如下

\[ \begin{align} n\cdot (m-1) < &N \leq n\cdot m \notag\\ -n\cdot (m-1) > &-N \geq -n\cdot m \notag\\ n\cdot (-m+1) > &-N \geq n\cdot (-m) \notag\\ n\cdot ((-m)+1) > &(-N) \geq n\cdot (-m) \notag\\ n\cdot (-m) \leq &(-N) < n\cdot ((-m)+1) \tag{3} \end{align} \]

对比等式(1) 和 (3) ，将 \(m'\) 等效为 \(-m\)，\(N'\) 等效为 \(-N\)，\(n'\) 等效为 \(n\)。

则能够得到正确的等式如下：

\[ m = - \left[-\frac{N}{n}\right] \tag{*} \]

需要注意的是，Python 中的 int() 函数并不等价于数学上的取整函数。其对于负数的取整是向上取整，而非向下取整。一个可靠的替代为 math.floor()