Analysis for the realization of an in-place and in-order prime factor algorithm

摘要

For the computation of the prime factor algorithm (PFA), an in-place and in-order approach is always desirable not only because of its reduction on memory requirement for the storage of the temporary results, but also because the computation time which is required to unscramble the output sequence to a proper order can also be saved. In this paper, we show that the PFA has an intrinsic property that allows it to be easily realized in an in-place and in-order form. As it is different from the other propositions which use two equations respectively for loading data from and retrieving results back to the memory, in this paper we show formally that in many cases only one equation is enough for both operations. Thus a truly in-place and in-order computation is accomplished. Nevertheless, the sequence length of the PFA computation must be carefully selected. Another objective of this paper is to analyze the conditions on which a particular sequence length is possible for in-place and in-order PFA computation. The result of this paper is useful to both the hardware and software realization of the PFA.