Fandom

How To Wiki

How to preform addition chain exponentiation

1,795pages on
this wiki
Add New Page
Talk0 Share

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.


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.

Also on Fandom

Random Wiki