Advertisement
Published in:
2015 | OriginalPaper | Chapter
Easy Multiple-Precision Divisors and Word-RAM Constants
Author : Torben Hagerup
Published in: Mathematical Foundations of Computer Science 2015
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
For integers \(b\ge 2\) and \(w\ge 1\), define the (b, w) cover size of an integer A as the smallest nonnegative integer k such that A can be written in the form \(A=\sum _{i=1}^k(-1)^{\sigma _i}b^{\ell _i}d_i\), where \(\sigma _i\), \(\ell _i\) and \(d_i\) are nonnegative integers and \(0\le d_i<b^w\), for \(i=1,\ldots ,k\). We study the efficient execution of arithmetic operations on (multiple-precision) integers of small (b, w) cover size on a word RAM with words of w b-ary digits and constant-time multiplication and division. In particular, it is shown that if A is an n-digit integer and B is a nonzero m-digit integer of (b, w) cover size k, then \(\lfloor A/B\rfloor \) can be computed in \(O(1+{{(k n+m)}/w})\) time. Our results facilitate a unified description of word-RAM algorithms operating on integers that may occupy a fraction of a word or several words.
As an application, we consider the fast generation of integers of a special form for use in word-RAM computation. Many published word-RAM algorithms divide a w-bit word conceptually into equal-sized fields and employ full-word constants whose field values depend in simple ways on the field positions. The constants are either simply postulated or computed with ad-hoc methods. We describe a procedure for obtaining constants of the following form in constant time: The ith field, counted either from the right or from the left, contains g(i), where g is a constant-degree polynomial with integer coefficients that, disregarding mild restrictions, can be arbitrary. This general form covers almost all cases known to the author of word-RAM constants used in published algorithms.