Minimal Addition-Subtraction Chains Using Genetic Algorithms

摘要

Addition and addition-subtraction chains consist of a sequence of integers that allow one to efficiently compute power T~E, where T varies but E is constant. The shorter the addition (addition-subtraction) chain is, the more efficient the computation. Solving the optimisation problem that yields the shortest addition (addition-subtraction) is NP-hard. There exists some heuristics that attempt to obtain reduced addition (addition-subtraction) chains. We obtain minimal addition (addition-subtraction) chains using genetic algorithms.