7 Jul
2014
7 Jul
'14
12:42 a.m.
On 7/6/14, Warren D Smith <warren.wds@gmail.com> wrote:
h(n) = (-1)^(parity of bit-sum of binary representation of n)
f(x) S=SUM[ f(n) * h(n), for n=0..2^k-1 with k large]
--incidentally, the hackers may enjoy the following problem: compute (-1)^h(n) for each n=0,1,2,...,2^k-1. I know of at least three ways to accomplish this in O(1) time per n (provided n is small enough to fit in a machine word) while consuming a number of words of memory O(1+k) or less...