Memory Efficient Arithmetic

Details Memory Efficient Arithmetic Memory Efficient Arithmetic

2003-02-25

arxiv.org/abs/math/0302315v3

Mathematics

Number Theory

Difference between this version and last: Better notation, light corrections, and more explanations

Scientific paper

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/b^m 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 2^t can be found using O(t^{2/3} log^C t) bits of storage (for some C>0), and O(t log^C 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.

Affiliated with

Also associated with

No associations

Rating

Memory Efficient Arithmetic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Memory Efficient Arithmetic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory Efficient Arithmetic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-482881