8
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ – Markus Bläser Oct 5 '11 at 21:19
  • 1
    $\begingroup$ @MarkusBläser answer ? $\endgroup$ – Suresh Venkat Oct 5 '11 at 22:21
12
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.