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