Wikia

How To Wiki

How to preform addition chain exponentiation

1,794pages on
this wiki
Talk0

addition chain exponentiation

LogicEdit

a0 = 1, and

for each k>0: ak = ai + aj for some i, j < k.

ExamplesEdit

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


From HowTo Wiki, a Wikia wiki.

Around Wikia's network

Random Wiki