Extended Precision Arithmetic

Computer algebra systems support exact sums and products of integers that are hundreds of digits long. One way to do such extended precision arithmetic is to generate a set of mutually relatively prime bases, and to do modular arithmetic modulo all of these bases. For example, consider the vector

$\displaystyle \left(\vphantom{ 997,999,1000,1001,1003,1007,1009}\right.$997, 999, 1000, 1001, 1003, 1007, 1009$\displaystyle \left.\vphantom{ 997,999,1000,1001,1003,1007,1009}\right)$

of bases. Factorization shows that the entries are pairwise relatively prime.


$\blacktriangleright$ Factor

$\left[\vphantom{
\begin{array}{c}
997 \\
999 \\
1000 \\
1001 \\
1003 \\
1007 \\
1009
\end{array}
}\right.$$\begin{array}{c}
997 \\
999 \\
1000 \\
1001 \\
1003 \\
1007 \\
1009
\end{array}$$\left.\vphantom{
\begin{array}{c}
997 \\
999 \\
1000 \\
1001 \\
1003 \\
1007 \\
1009
\end{array}
}\right]$ = $\left[\vphantom{
\begin{array}{c}
997 \\
3^{3}37 \\
2^{3}5^{3} \\
7...
...\times 13 \\
17\times 59 \\
19\times 53 \\
1009
\end{array}
}\right.$$\begin{array}{c}
997 \\
3^{3}37 \\
2^{3}5^{3} \\
7\times 11\times 13 \\
17\times 59 \\
19\times 53 \\
1009
\end{array}$$\left.\vphantom{
\begin{array}{c}
997 \\
3^{3}37 \\
2^{3}5^{3} \\
7...
...\times 13 \\
17\times 59 \\
19\times 53 \\
1009
\end{array}
}\right]$


Consider the two numbers 23890864094 and 1883289456. You can represent these numbers by reducing the numbers modulo each of the bases. Thus,


23890864094 $\displaystyle \longleftrightarrow$ $\displaystyle \left[\vphantom{
\begin{array}{rl}
23890864094\limfunc{mod}\;997 ...
...unc{mod}1007 & =564 \\
23890864094\limfunc{mod}1009 & =218
\end{array}}\right.$$\displaystyle \begin{array}{rl}
23890864094\limfunc{mod}\;997 & =350 \\
238908...
...094\limfunc{mod}1007 & =564 \\
23890864094\limfunc{mod}1009 & =218
\end{array}$$\displaystyle \left.\vphantom{
\begin{array}{rl}
23890864094\limfunc{mod}\;997 ...
...unc{mod}1007 & =564 \\
23890864094\limfunc{mod}1009 & =218
\end{array}}\right]$  
     1pt  
1883289456 $\displaystyle \longleftrightarrow$ $\displaystyle \left[\vphantom{
\begin{array}{rl}
1883289456\limfunc{mod}\;997 &...
...imfunc{mod}1007 & =70 \\
1883289456\limfunc{mod}1009 & =37
\end{array}}\right.$$\displaystyle \begin{array}{rl}
1883289456\limfunc{mod}\;997 & =324 \\
1883289...
...289456\limfunc{mod}1007 & =70 \\
1883289456\limfunc{mod}1009 & =37
\end{array}$$\displaystyle \left.\vphantom{
\begin{array}{rl}
1883289456\limfunc{mod}\;997 &...
...imfunc{mod}1007 & =70 \\
1883289456\limfunc{mod}1009 & =37
\end{array}}\right]$ 6pt  

Thus, the product 23890864094⋅1883289456 is represented by the vector

$\displaystyle \left[\vphantom{
\begin{array}{rl}
350\cdot 324\limfunc{mod}\;...
...1007 & =\;207 \\
218\cdot 37\limfunc{mod}1009 & =1003
\end{array}
}\right.$$\displaystyle \begin{array}{rl}
350\cdot 324\limfunc{mod}\;997 & =\;739 \\
...
...mfunc{mod}1007 & =\;207 \\
218\cdot 37\limfunc{mod}1009 & =1003
\end{array}$$\displaystyle \left.\vphantom{
\begin{array}{rl}
350\cdot 324\limfunc{mod}\;...
...1007 & =\;207 \\
218\cdot 37\limfunc{mod}1009 & =1003
\end{array}
}\right]$ 6pt

The product 23890864094⋅1883289456 is now a solution to the system
x 739 $\displaystyle \left(\vphantom{ \limfunc{mod}997}\right.$$\displaystyle \limfunc$mod997$\displaystyle \left.\vphantom{ \limfunc{mod}997}\right)$  
x 909$\displaystyle \left(\vphantom{ \limfunc{mod}999}\right.$$\displaystyle \limfunc$mod999$\displaystyle \left.\vphantom{ \limfunc{mod}999}\right)$  
x 864$\displaystyle \left(\vphantom{ \limfunc{mod}1000}\right.$$\displaystyle \limfunc$mod1000$\displaystyle \left.\vphantom{ \limfunc{mod}1000}\right)$  
x 652 $\displaystyle \left(\vphantom{ \limfunc{mod}1001}\right.$$\displaystyle \limfunc$mod1001$\displaystyle \left.\vphantom{ \limfunc{mod}1001}\right)$  
x 671 $\displaystyle \left(\vphantom{ \limfunc{mod}1003}\right.$$\displaystyle \limfunc$mod1003$\displaystyle \left.\vphantom{ \limfunc{mod}1003}\right)$  
x 207 $\displaystyle \left(\vphantom{ \limfunc{mod}1007}\right.$$\displaystyle \limfunc$mod1007$\displaystyle \left.\vphantom{ \limfunc{mod}1007}\right)$  
x 1003$\displaystyle \left(\vphantom{ \limfunc{mod}1009}\right.$$\displaystyle \limfunc$mod1009$\displaystyle \left.\vphantom{ \limfunc{mod}1009}\right)$