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)O(n) algorithm to extend the size should you need it.

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

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

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

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

264Xi=264mi[ximiM]mi \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 0Xi<10 \leq X_i < 1 and that XiMX_i M is a whole number.

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

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

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

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

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

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