使用余数树计算多个余数

Question

使用余数树计算多个余数

algorithmoptimizationdivisionmodulointeger-division

3

我正在寻找一种快速计算 n mod x1，n mod x2，n mod x3等的方法。我找到了一篇关于“remainder trees”的文章，声称可以做到这一点。

然而，我无法看出上述方法比单独计算每个mod更好（即使上述remaindersusingproducttree的最后一步似乎正是在这样做）。我也简单地对上述代码进行了基准测试，但它似乎并没有运行得更快。

我的问题是，我猜“余数树”在某种程度上比朴素的方法更有效，但我不明白为什么。请问有人能够解释一下吗？

或者，还有其他快速计算多个mod操作的方法吗？

- minmax

从快速浏览文章来看，它似乎是针对除法结果越长（较小的除数意味着更多的操作）时除法变得更加昂贵的用例。您是否尝试过使用比计算机本地类型大得多的数字进行测试，例如100位数字左右？ - domen

@domen 是的，我尝试过了，但没有任何区别。就像我之前所说的那样，最后一步似乎与朴素方法相同，所以我有点困惑。 - minmax

最后一步与朴素方法不完全相同。朴素方法计算可能非常大的n mod x。树算法首先通过应用n mod（某些x的乘积）将n减小到较小的数字，然后使用这些较小的数字来计算最终结果。我同意@domen的观点，当n非常大且我们假设余数运算具有非常量运行时间时，这可能是有用的。 - lwi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sneftel · Accepted Answer

该算法的加速假设是log(n) >> log(x[i])。两个数字的除法时间复杂度为O(b^2)，其中b是被除数中的位数。如果n非常大，则初始除法（n mod x[0]x[1]）的成本相当高，但是接下来的两个除法是针对第一个除法的相对较小的余数进行的。因此，为了在基础情况下获得两个余数，该算法将两个非常昂贵的除法替换为单个非常昂贵的除法和两个非常便宜的除法。