An algorithm for exact division
type: Item
instance of: scholarly article
title: An algorithm for exact division
zbMATH Open document ID: 0779.68049
author: Tudor Jebelean
published in: Journal of Symbolic Computation
publication date: 1993-08-25T00:00:00Z
review text: Division of long integers is a frequently performed task in computer algebra. The common algorithms used for that purpose rely on computing quotient and remainder (\(IQR\)), even when it is known in advance that the latter one is zero. The author proposes to exploit the fact that the division is exact and gives a time-saving algorithm (\(EDIV\)) starting from the least significant digits of the operands, which is particulary efficient when the radix is a prime number or a power of 2. The speed-up may be quite significant, when the length of the result is much smaller than the lengths of the operands. Moreover the proposed algorithm is specially suited for systolic parallelization in pipelining least- significant-digits-first. The algorithm can be applied to integer \(GCD\) computation and to division modulo a power of 2. Benchmarks show that the ratio of \(CPU\)-times between \(EDIV\) and \(IQR\) is between 70\% and 30\% depending on the relation of the lengths of the operands. In computing the modular inverse the savings may even be better giving speed-ups between 23 and 28 depending on the input length.
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 65Y05
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 370649
zbMATH Keywords: computer algebra
zbMATH Keywords: systolic parallelization
zbMATH Keywords: modular inverse
MaRDI profile type: Publication
full work available at URL: jsco.1993.1012
OpenAlex ID: W1969260620
DOI: 10.1006/JSCO.1993.1012
Recommended article: A DIVISION ALGORITHM
Recommended article: A multiple-precision division algorithm
Recommended article: Q3759796
Recommended article: Constant-division algorithms
Recommended article: A division algorithm for residue numbers
Recommended article: Q3344989
Recommended article: Q4291472
Recommended article: Division algorithm and Kronecker's approximation theorem
description: scientific article; zbMATH DE number 370649