The basic question addressed in this chapter is this: given a positive integer E, and given a multiplicative semigroup, what is the smallest number of multiplications and/or divisions needed to compute elements of the semigroup of the form TE , given that we begin with an element T, and are allowed to multiply or divide only by already-computed powers of T? This is clearly equivalent to the problem of finding a shortest sequence of integers (a0,a1, ... ,an), such that a0 = 1, an = E, and, for each 1 < k < n, there exist i,j < k, such that ak = ai +/- aj.
This problem is known to be nondeterministic polynomial time (NP) hard, but, nonetheless, one can find several reasonably efficient algorithms that produce a nearly optimal result. The exact value of the length of such a minimal sequence is known only for small values of E, while for large values of E, we do know that this length is
The authors present a new method, using genetic algorithms, for trying to produce a near optimal result. This method is well explained in the chapter, and is definitely of interest, as it obtains better results than the heuristics now in use.
