Authors
Citation
W. Krandick et T. Jebelean, BIDIRECTIONAL EXACT INTEGER DIVISION, Journal of symbolic computation, 21(4-6), 1996, pp. 441-455
Citations number
17
Categorie Soggetti
Mathematics,"Computer Sciences, Special Topics",Mathematics,"Computer Science Theory & Methods
Journal title
ISSN journal
07477171
Volume
21
Issue
4-6
Year of publication
1996
Pages
441 - 455
Database
ISI
SICI code
0747-7171(1996)21:4-6<441:BEID>2.0.ZU;2-1
Abstract
Division of integers is called exact if the remainder is zero. We show
that the high-order part and the low-order part of the exact quotient
can be computed independently from each other. A sequential implement
ation of this algorithm is up to twice as fast as ordinary exact divis
ion and four times as fast as the general classical division algorithm
if the dividend is twice as long as the divisor. A shared-memory para
llel implementation on two processors gains another factor of two in s
peed. (C) 1996 Academic Press Limited