|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Memory Efficient Arithmetic | | Ernie Croot
; | | Date: |
25 Feb 2003 | | Subject: | Number Theory; Data Structures and Algorithms MSC-class: 11Y70 | math.NT cs.DS | | Abstract: | 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. | | Source: | arXiv, math.NT/0302315 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER