FactHacks

Given an integer n and a sequence X of positive integers, the remainder-tree algorithm computes n mod X[0], n mod X[1], n mod X[2], etc. For long sequences the remainder-tree algorithm is much faster than computing each remainder separately.

The remainder-tree algorithm is an important subroutine in the batch-gcd algorithm.

How it works

The remainder-tree algorithm uses the product tree of X as input:

     def remaindersusingproducttree(n,T):
       result = [n]
       for t in reversed(T):
         result = [result[floor(i/2)] % t[i] for i in range(len(t))]
       return result

     def remainders(n,X):
       return remaindersusingproducttree(n,producttree(X))

     # example:
     print remainders(8675309,[11,13,17,19,23])
     # output: [5, 6, 5, 4, 8]
     # double check:
     print [8675309 % p for p in [11,13,17,19,23]]
     # output: [5, 6, 5, 4, 8]

This algorithm computes n mod X[0] and n mod X[1] by first computing n mod X[0]X[1] and then using the identities

n mod X[0] = (n mod X[0]X[1]) mod X[0],
n mod X[1] = (n mod X[0]X[1]) mod X[1].

Example:

     sage: X = [41,43,47,53]
     sage: T = producttree(X); print T
     [[41, 43, 47, 53], [1763, 2491], [4391633]]
     sage: n = 31415926535
     sage: r = [n]
     sage: r = [r[floor(i/2)] % T[2][i] for i in range(len(T[2]))]; print r
     [2575686]
     sage: r = [r[floor(i/2)] % T[1][i] for i in range(len(T[1]))]; print r
     [1706, 2483]
     sage: r = [r[floor(i/2)] % T[0][i] for i in range(len(T[0]))]; print r
     [25, 29, 39, 45]
     sage: # double check:
     sage: [n%x for x in X]
     [25, 29, 39, 45]

Here 31415926535 is first reduced mod 4391633, producing 2575686; then 2575686 is reduced mod 1763 and 2491, producing 1706 and 2483; then 1706 is reduced mod 41 and 43, producing 25 and 29; then 2483 is reduced mod 47 and 53, producing 39 and 45.

Version: This is version 2013.09.16 of the remainder.html web page.