Integer and Rational Arithmetic on MasPar

. The speed of integer and rational arithmetic increases significantly by systolic implementation on a SIMD architecture. For multiplication of integers one obtains linear speed-up (up to 29 times), using a serial--parallel scheme. A two-dimensional algorithm for multiplication of polynomials gives half-linear speed-up (up to 383 times). We also implement multiprecision rational arithmetic using known systolic algorithms for addition and multiplication, as well as recent algorithms for exact division and GCD computation. All algorithms work in "least-significant digits first" pipelined manner, hence they can be well aggregated together. The practical experiments show that the timings depend linearly on the input length, demonstrating the effectiveness of the systolic paradigm for multiple precision arithmetic. 1 Introduction Systolic parallelization of multiprecision arithmetic in the "most-significant digits first" (MSF) pipelined manner was considered by [13] and other authors (see ..