<p>This answer expands my comment above.</p>

<p>You can do it with $O(\log e + \log \log b)$ space as follows:</p>

<p>1) First compute $b^e$ in Chinese remainder representation modulo sufficiently many primes.</p>

<p>2) Then use the Chiu-Davida-Litow algorithm to convert the Chinese remainder representation into binary representation. (Informatique Theoretique et Applications, Vol 35(3), pages 259-275, 2001)</p>

<p>3) Finally, just count the number of $1$'s.</p>

<p>This is a composition of a finite number of log-space computable functions, which is itself log-space computable.</p>

CC BY-SA 3.0
2011-10-06T23:28:55.163Z
2011-10-06T23:28:55.163Z
Markus Bläser
<p>Given positive integers $b$ and $e$, what is known about the space and time complexity of finding the Hamming weight (number of binary 1s) of $b^e$?</p>

<p>If $e\log b$ bits are available, the number can simply be calculated by standard techniques and the 1s counted.  But what techniques are possible when less memory can be used?</p>

CC BY-SA 3.0
2011-10-05T21:19:55.490Z
Why don't you compute in Chinese remainder representation, use the Chiu-Davida-Litow algorithm to convert to binary representation in logarithmic space, and then just count?
Markus Bläser
CC BY-SA 3.0
2011-10-05T22:21:54.720Z
@MarkusBläser answer ?
Suresh Venkat
<ds.algorithms><co.combinatorics><space-bounded><space-time-tradeoff>
Hamming weight of powers
Charles
# Hamming weight of powers

(Asked by: username_0 on 2011-10-05)

Given positive integers $b$ and $e$, what is known about the space and time complexity of finding the Hamming weight (number of binary 1s) of $b^e$?

If $e\log b$ bits are available, the number can simply be calculated by standard techniques and the 1s counted. But what techniques are possible when less memory can be used?

**Tags:** ds.algorithms, co.combinatorics, space-bounded, space-time-tradeoff
> **Comments:**
> **username_1**: Why don't you compute in Chinese remainder representation, use the Chiu-Davida-Litow algorithm to convert to binary representation in logarithmic space, and then just count?  
> **username_2**: @MarkusBläser answer ?  

---

## 1 answers

### Answer by username_1 on 2011-10-06. Score: 12 | Accepted answer

This answer expands my comment above.

You can do it with $O(\log e + \log \log b)$ space as follows:

1) First compute $b^e$ in Chinese remainder representation modulo sufficiently many primes.

2) Then use the Chiu-Davida-Litow algorithm to convert the Chinese remainder representation into binary representation. (Informatique Theoretique et Applications, Vol 35(3), pages 259-275, 2001)

3) Finally, just count the number of $1$'s.

This is a composition of a finite number of log-space computable functions, which is itself log-space computable.


---

