The Product Replacement Prospector

We present a heuristic extension to the product replacement algorithm, called the Prospector  . The aim is to find hopefully good quality ‘random’ elements with short straight line programs in the given generators. This is achieved by saving the random state at certain points and later restoring it. Statistical tests are employed in order to determine when to save the state. We also give evidence for the surprisingly good effect of using an accelerator. The Prospector has been implemented in MagmaMagma, and experimental evidence is provided which indicates that it is a very practical method.

► We present a heuristic extension to the product replacement algorithm.
► The aim is to find random elements with short straight line programs.
► We achieve this by saving the random state at certain points and later restoring it.
► Statistical tests are employed in order to determine when to save the state.