1 Sep
2013
1 Sep
'13
5:46 p.m.
On 01/09/2013 17:28, Joerg Arndt wrote: [me:]
It may be worth observing that (modulo implementation details) Mike's solution (*the* solution) is essentially the same thing as 1 / (1+x^n) = 1 - x^n + x^2n - x^3n ..., where (mod 2) minus equals plus.
[Joerg:]
The code (note the n*=2; ) rather uses 1/(1-z) = (1+z) * (1+z^2) * (1+z^4) * (1+z^8) * ... where z = x^n
I see that as an implementation detail -- though really I suppose it's not much more obvious that 1+x+x^2+x^3+... = (1+x)(1+x^2)(1+x^4)... than that 1+x+x^2+x^3+... = 1/(1-x). -- g