On today's pipelined processors, the fastest algorithm is probably some blending of the two. On Sep 1, 2013 4:46 PM, "Gareth McCaughan" <gareth.mccaughan@pobox.com> wrote:
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
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>