Window and Extended Window Methods for Addition Chain and Addition -Subtraction Chain
Noboru KUNIHIRO and Hirosuke YAMAMOTO
- The addition chain (A-chain) and addition-subtraction chain (AS-chain) are efficient tools to calculate power $M^e$(or multiplication $eM$), where integer $e$ is fixed and $M$ is variable. Since the optimization problem to find the shortest A(or AS)-chain in polynomial time are proposed. In this paper, a window method for the A-chain and AS-chain are proposed and their performances are theoretically evaluated by applying the theory of the optimal variable-to-fixed length code, i.e., Tunstall code, in data compression. It is shown by theory and simulation that the proposed algorithms are more efficient than other algorithms in practical cases in addition to the asymptotic case. key words: addition -subtraction chain, Tunstall code, canonical signed binary representation, window method.
- Key words: addition-substraction chain, Tunstall code, canonical signed binary representation, window method
- PDF (832 Kbytes) Copyright(c)1998 IEICE