Efficient computation of the iteration of functions

Given a function f from {0,1,…,N−1} to {0,1,…,N−1}, we prove that fm(x), the mth iterate of f at x, can be computed in time O(logN) for each natural number m and each x by using O(N) information that is generated in a preprocessing procedure. Two types of optimal orbit decompositions of functional graphs are proposed for the preprocess. Both preprocesses require only linear time and linear space. Our decompositions minimize the number of recursions in the computation of fm(x) and solve some open problems in Tsaban (Discrete Applied Mathematics 155 (2007) 386–393).