Accession Number : ADA299006

Title :   An Improved RNS Division Algorithm.

Descriptive Note : Final rept.,

Corporate Author : NAVAL ACADEMY ANNAPOLIS MD

Personal Author(s) : Turner, Peter R.

PDF Url : ADA299006

Report Date : 07 NOV 1994

Pagination or Media Count : 16

Abstract : This paper presents a division algorithm for the Residue Number System which is a modification, and improvement on, the recent algorithm of Hitz and Kaltofen (1994). The relative cost of the divisions is substantially reduced rendering the RNS division feasible for computations which are not division-intensive such as the solution of a system of linear equations of small dimension. The advantages of this algorithm over the original work of Hitz and Kaltofen lies simply in using a ceiling function in place of the floor function. This leads to a better and simpler convergence criterion and test, and, more importantly, to a simple scheme for accelerating the potentially slow early iteration of the Newton-iteration-based algorithm. (AN)

Descriptors :   *ALGORITHMS, OPTIMIZATION, COMPUTATIONS, COMPARISON, INTEGER PROGRAMMING, PARALLEL PROCESSING, APPROXIMATION(MATHEMATICS), CONVERGENCE, NUMERICAL METHODS AND PROCEDURES, ITERATIONS, DYNAMIC RANGE, LINEAR ALGEBRAIC EQUATIONS, BINARY ARITHMETIC, DIVISION.

Subject Categories : Numerical Mathematics
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE