我正在寻找一种快速计算 n mod x1、n mod x2、n mod x3 的方法，...找到了一篇关于“remainder trees”的文章，声称可以做到这一点。
但是，我看不出上述方法比天真地分别计算每个 mod 有什么好处(即使是上述 remaindersusingproducttree 的最后一步似乎也正是这样做的).我还简单地对上面的代码进行了基准测试，它似乎并没有运行得更快。
我的问题是，我猜“剩余树”在某种程度上比天真的方法更有效，但我不明白如何。拜托，任何人都可以对此有所了解吗？
或者，是否有任何其他方法可以快速计算许多 mod 操作？
最佳答案
该算法的加速假定 log(n) >> log(x[i])。两个数相除的时间复杂度是O(b^2)，其中b是被除数的位数。如果 n 非常大，初始除法 (n mod x[0]x[1]) 会非常昂贵，但接下来的两个除法是在相对较小的余数上完成的来自第一师。因此，为了在基本情况下获得两个余数，该算法将两个非常昂贵的除法替换为一个非常昂贵的除法和两个非常便宜的除法。
关于algorithm - 用余数树计算许多余数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52295035/