Cliff Bergman on Tue, 31 Dec 2002 09:49:35 -0600

 Re: How to find the period in a vector ?

I know of two ways to find the period of a vector. One way is to use Floyd's algorithm. It is described in Exercise 6, page 7 of Volume 2 of the Art of Computer Programming by Don Knuth. (There is also an enhanced version of the algorithm due to, I think, Lamport. I can't find the reference at the moment.)


The other way, which is probably more practical if you already have the vector in memory is to use Gusfield's Z function. This is from his book: D. Gusfield, {\it Algorithms on strings, trees, and sequences}, Cambridge Univ. Press, Cambridge, 1997; MR 99b:68095.


I once coded the algorithm to do this in Gap. (My apologies to this list. This was before I was aware of pari.) I'm including the code below, in case you know gap well enough to read it. One wrinkle in the code: in order to account for a possible "tail" on the sequence before the periodic part, I first reverse the sequence and then compute the period.

I'd be glad to try and help explain this code if it is unreadable.

--cliff b.

# Compute a version of the 'Z' function discussed in Chapter 1 of
# Gusfield's book. The only difference is that we are comparing to the
# _end_ of the string, rather than the beginning.  Thus, given a string
# s, z[k] is the number of characters ending with s[k] that matches a
# suffix of s.

ExplicitCompare:=function(s,a,b)

# Returns the number of characters of s, ending at positions a and b
# that agree. Uses brute force.

local i,min;
i:=0;
min:=Minimum(a,b);
while (i< min and s[a-i]=s[b-i]) do
i:=i+1;
od;
return i;
end;

SuffixMatch:=function(s)
# Returns the z function described above.

local n,z,i,r,l,k,kk,beta;
n:=Length(s);
z:=[1..n-1]*0;

#Basis for the recursive definition: compute z[n-1] explicitly.
i:=ExplicitCompare(s,n-1,n);
z[n-1]:=i;
if i>0 then
r:=n-1;
l:=n-i;
else
r:=n; l:=n;
fi;

# Now, Compute z[k] by working downward to 1
for k in [n-2,n-3..1] do
if k<l then
# Determine z[k] by explicit comparison
i:=ExplicitCompare(s,k,n);
z[k]:=i;
if i>0 then
r:=k;
l:=k-i+1;
fi;
else        # if k>=l
kk:=n-r+k;
beta:= k-l+1;
if z[kk] < beta then
z[k]:=z[kk];
else
i:=ExplicitCompare(s,l-1,n-beta);
z[k]:=beta+i;
l:=l-i;
r:=k;
fi;    # if kk<beta
fi;    # if k<l
od;
return z;
end;

# Accepts a finite string as input, and determines whether it is
# eventually periodic. If so, we return the length of the period and the
# length of the tail.  If not, return 0 for the period.

period:=function(s)
local z, p,t,k, n, kmax;

# Find the location of the largest z-value
z:=SuffixMatch(s);
n:=Length(s);
kmax:=n-1;
for k in [n-2,n-3..1] do
if z[k]>z[kmax] then
kmax:=k;
fi;
od;

p:=n-kmax;          #period
t:=n-p-z[kmax];     #tail

# Heuristics to determine whether the string should be considered
# eventually periodic.  Change to suit yourself.

if z[kmax]>p or 3*z[kmax]>t+p then
return [p,t];
else
return [0,n];
fi;
end;


--On Sunday, December 15, 2002 12:12:11 PM +0100 Thomas Baruchel <thomas.baruchel@libertysurf.fr> wrote:


Brest, le dimanche 15 décembre

Hi, I wonder what is the best way to find the length of the period
in a vector. I suppose the vector is completely periodical, eg:
[1,2,3,1,2,3,1,2,3], though I'm not sure that the length of the vector
is divisible by the length of the period, eg: [1,2,3,1,2,3,1,2]
(without the last '3'). Is there something quick enough to do with
GP ?

--
Deux choses remplissent le coeur d'une admiration et d'une vénération
toujours nouvelles et toujours croissantes, à mesure que la réflexion
s'y attache et s'y applique : le ciel étoilé au-dessus de moi et la loi
morale en moi. (Emmanuel Kant)



Cliff Bergman
Department of Mathematics
Iowa State University
Ames, Iowa 50011