2009-11-30 (updated 2014-03-03)

Fast Base Extension in Residue Number Systems

% Remco Bloemen % 2009-11-30, last updated 2014-03-03

Residue number systems can make a lot of numerical operations embarrassingly parallel. But this comes at a cost: there is no parallel division algorithm and you need to known the size of the result upfront. In this post I'll address the last concern and show a $O(n)$ algorithm to extend the size should you need it.

Given a sequence of prime number $m = (m_1, m_2, \dots m_n)$ and the product of the prime numbers $M = \prod m_i$ the Chinese Remainder Theorem can be stated as:

$\left[ X \right]_M =\left[ \sum_{[1,n]}^i \frac{M}{m_i} \left[X \frac{m_i}{M} \right]_{m_i} \right]_M$

$x_i =\left[ X \right]_{m_i}$

$X_i =\frac{1}{m_i} \cdot \left[ x_i \cdot \frac{m_i}{M}\right]_{m_i}$

$\left\lfloor2^{64} \cdot X_i\right\rfloor =\left\lfloor \frac{2^{64}}{m_i} \cdot \left[ x_i \cdot \frac{m_i}{M} \right]_{m_i} \right\rfloor$

It is easy to proof that $0 \leq X_i < 1$ and that $X_i M$ is a whole number.

$X =\left[ \sum_{[0,N)}^i M \cdot X_i \right]_M$

$\frac{X}{M} =\left[ \sum_{[0,N)}^i X_i \right]_1$

$\frac{X}{M} + \frac{M-1}{2M} =\left[ \sum_{[0,N)}^i X_i\right]_1$

$W =\left\lfloor \sum_{[0,N)}^i X_i \right\rfloor$

$X = \sum_{[0,N)}^i M \cdot X_i - W \cdot M$

$\left[ X \right]_k = \left[ \sum_{[0,N)}^i M \cdot X_i - W \cdot M \right]_k$