# Hamming weight of powers

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?

• 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 Oct 5 '11 at 21:19
• @MarkusBläser answer ? – Suresh Venkat Oct 5 '11 at 22:21

## 1 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.