2003/02/25 by Ernie Croot, Croot, Ernie
Computer Science · Mathematics · #11Y70 #Computability, Logic, AI Algorithms #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Numerical Methods and Algorithms #cs.DS #math.NT #msc:11Y70
paper · pdf · doi:10.48550/arxiv.math/0302315
Difference between this version and last: Better notation, light corrections, and more explanations
openalex publication_date 2003/02/25 · arxiv created 2003/03/20 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we give an algorithm for computing the mth base-b digit (m=1 is the least significant digit) of an integer n (actually, it finds sharp approximations to n/bm mod 1), where n is defined as the last number in a sequence of integers s1,s2,...,sL=n, where s1=0, s2=1, and each successive si is either the sum, product, or difference of two previous sj's in the sequence. In many cases, the algorithm will find this mth digit using far less memory than it takes to write down all the base-b digits of n, while the number of bit operations will grow only slighly worse than linear in the number of digits. One consequence of this result is that the mth base-10 digit of 2t can be found using O(t2/3 logC t) bits of storage (for some C>0), and O(t logC t) bit operations. The algorithm is also highly parallelizable, and an M-fold reduction in running time can be achieved using M processors, although the memory required will then grow by a factor of M.