An addition chain for a positive integer is , where each is the sum of two earlier entries, which may coincide. It computes in multiplications by reusing previously computed powers. For example, computes in five multiplications.
An addition chain restricted to updates with . Each new power uses the most recently computed power as one factor. This restriction reduces the search space, but a shortest star chain need not be a shortest unrestricted addition chain for every target.
Articles by others on the same topic
An **addition chain** is a sequence of integers starting from 1, where each subsequent number is obtained by adding any two previous numbers in the sequence. The goal of an addition chain is to reach a specific target number using the fewest possible additions. For example, an addition chain for the number 15 could be: 1. Start with 1. 2. Add 1 + 1 to get 2. 3. Add 1 + 2 to get 3.