Computing many remainders with remainder trees

user_10005302 0
Viewed 369

I'm looking for fast a way to compute n mod x1, n mod x2, n mod x3, ... I found a an article about "remainder trees" which claims to do just that.

However, I fail to see how is the above approach any better than naively computing each mod separately (even the last step of the above remaindersusingproducttree seems to doing exactly this). I also trivially benchmarked the above code and it does not seem to run faster.

My question is, I guess "remainder trees" somehow work better than the naive approach but I don't understand how. Please, could anyone shed some light into this?

Alternatively, is there any other way to quickly computing the many mod operations?

integer-division division modulo optimization algorithm
1 Answers

The speedup of this algorithm assumes that log(n) >> log(x[i]). The time complexity of dividing two numbers is O(b^2), where b is the number of bits in the dividend. The initial division (n mod x[0]x[1]) is quite expensive if n is very large, but the following two divisions are done on the comparatively small remainder from the first division. Thus, to obtain two remainders in the base case, the algorithm is replacing two very expensive divisions by a single very expensive division and two very cheap divisions.

user_7874800
Related