我正在寻找快速计算n mod x1，n mod x2，n mod x3的方法......我发现了一篇关于“remainder trees”的文章，声称这样做。
然而，我没有看到上述方法如何比天真地分别计算每个mod更好（甚至上面的remaindersusingproducttree的最后一步似乎正是这样做）。我也简单地对上面的代码进行了基准测试，但它似乎运行得不快。
我的问题是，我认为“剩余树木”在某种程度上比天真的方法更好，但我不明白如何。拜托，任何人都可以对此有所了解吗？
或者，有没有其他方法来快速计算许多mod操作？
该算法的加速假定为log(n) >> log(x[i])。除以两个数的时间复杂度是O(b^2)，其中b是被除数中的位数。如果n mod x[0]x[1]非常大，那么初始划分（n）相当昂贵，但是对于来自第一师的相对较小的剩余部分进行了以下两个划分。因此，为了在基本情况下获得两个剩余部分，该算法将由一个非常昂贵的部门和两个非常便宜的部门替换两个非常昂贵的部门。