On an efficient algorithm for big rational number computations by parallel \(p\)-adics (Q1260760)

The author considers rational operations with large numbers as numerators and denominators of fractions. The multiple precision is achieved by repeating the computation in \(p\)-adic form for different single precision primes on \(k\) parallel processors, with expansions taken to \(r\) terms. Once the various \(p\)-adic answers are achieved, the Chinese remainder theorem produces a rational answer in \(O(r(k\log p)^{\log_ 2 3})\) binary steps. There are various refinements based on the relative values of \(p\), \(r\), and \(k\). The previous known bound had the power \(r^ 2\) instead of \(r\), and the strange ``logarithm'' exponent comes from fast multiplication. The vital details regarding the return from \(p\)-adic to rational are merely cited from an earlier work [see \textit{A. Colagrossi} and \textit{C. Limongelli}, Proc. Conf. AAECC-6, Lect. Notes Comput. Sci. 357, 169-180 (1989; Zbl 0703.11075)].