Addition chain
|
|
In mathematics, an addition chain is a sequence a0, a1, a2, a3, ... that satisfies
- a0 = 1, and
- for each k>0: ak = ai + aj for some i, j < k.
As an example: 1, 2, 3, 6, 12, 24, 30, 31 is an addition chain for 31, of length 7, since
- 2 = 1 + 1
- 3 = 2 + 1
- 6 = 3 + 3
- 12 = 6 + 6
- 24 = 12 + 12
- 30 = 24 + 6
- 31 = 30 + 1
Addition chains can be used for exponentiation: so for example we only need 7 multiplications to calculate 531:
- 52 = 51 × 51
- 53 = 52 × 51
- 56 = 53 × 53
- 512 = 56 × 56
- 524 = 512 × 512
- 530 = 524 × 56
- 531 = 530 × 51
See also: