> < ^ Date: Fri, 05 Oct 2001 11:10:25 -0400
< ^ From: Bill Dubuque <wgd@zurich.ai.mit.edu >
< ^ Subject: Re: linear feedback shift registers in GAP

David Joyner wrote to GAP Forum:
>
> One example I've been trying to illustrate in my undergraduate
> algebra class is the following:
>
> (a) the coefficients of X^i in the power series expansion
> of 1/(1 + X^3 + X^4) (mod 2), [...]
>
> GAP does all these, but (a) is the hardest. [...] It is
> so slow that it is almost impractical for classroom use [...]

This series may be quickly computed using the Newton iteration
for inversion of a power series. Here it nicely specializes to

f  (X)  =  1
 0 

f  (X)  =  f (X^2) (1 + X^3 + X^4)   mod  X^2^(n+1)
 n+1        n

which may be quickly computed via additions and shifts.

What is the source of this problem?

-Bill Dubuque

Miles-Receive-Header: reply


> < [top]