关于a^n的计算

northwolves

1.  计算a^n至少需要几步乘法（显然>=$log_2 n$)
2.  使用该最少的步数共有多少种不同的计算方法？
比如：
计算a^14最少需要6步，共14种计算方法：

1        2        3        4        7        14
1        2        3        5        7        14
1        2        3        6        7        14
1        2        3        6        8        14
1        2        3        6        12        14
1        2        4        5        7        14
1        2        4        5        9        14
1        2        4        5        10        14
1        2        4        6        7        14
1        2        4        6        8        14
1        2        4        6        10        14
1        2        4        6        12        14
1        2        4        8        10        14
1        2        4        8        12        14

3. a^n计算时，最少步数正好有 n种的除了1和14还有哪些？

asdfslw

一般地，一数列1=a0, a1, a2,... ar=e，如果对每个i=1,2,...r,存在一整数对(j,k),j<=k<i，使得ai=aj+ak成立，则称为e的长为r的加法链。
寻找最短加法链的问题，目前还不知道有没有多项式时间的算法。它是属于复杂类NP中的问题，即通过“猜测”能用非确定性方法在多项式时间内解决的问题，P类问题则是能确定性地在多项式时间内解决的问题。容易明白P类问题是NP类问题的子集，因为所有多项式时间确定性的问题都可以非确定性地解出。
最短加法链的确定是一个NP完全问题，它是一个至少与解NP集合中所有其他问题同样困难的一个问题。因此，NP完全问题有特别的重要性，因为如果发现它们中间一个的确定性多项式时间的算法，则其他的NP问题也可以在多项式时间内解出。在这种情况下P类与NP类恰好重合。目前，普遍认为P！=NP。

《密码编码学---加密方法的C与C++实现 第2版》P69

northwolves

谢谢回复。

更正一下，1楼的a^14 应该是5步：
1        2        3        4        7        14
即
a*a=a^2
a*a^2=a^3
a^2*a^2=a^4
a^3*a^4=a^7
a^7*a^7=a^14

无心人

乘法链的长度似乎有公式可以估算上界

northwolves

计算a^n至少需要几步乘法（显然>=log2n)
-------------------------------------------------
已经推导出：
p(1)=0
p(2)=1
p(3)=2
p(2^n)=n
p(2n)=p(n)+1
p(2n+1)=min(p(n)+2, p(n+1)+2)

wayne

按楼上的思路，编了一个Mathematica程序：

1. 
   
2. g = If[# > 3, If[EvenQ[#], #0[#/2] + 1, Min[#0[(# - 1)/2], #0[(# + 1)/2]] + 2], # - 1] &;
   
3. Table[{ii,g@ii}, {ii, 1, 100}]
   

复制代码

wayne

5# northwolves

p(2n+1)=min(p(n)+2, p(n+1)+2)

感觉这个好像有问题

wayne

比如：计算 a^27,按5楼的理论，应该先算出13或14，而a^13,a^14都至少需要5步，所以，
27应该要7步，可是这个只需要6步即可完成：
2,3,6,12,24,27
2,4,8,9,18,27

wayne

另外，算31,63,127,255,......似乎也有问题。

a^16需要四步，按5楼的理论，那么a^31应该要6步，可六步的方案我笔画了很长时间，也没找到。
7步的如下：
2，3，6，12，24，30，31
2，3，6，12，18，30，31
2，4，5，10，20，30，31
2，4，5，10，15，30，31

medie2005

Knuth写了一个程序计算的：
http://www-cs-faculty.stanford.edu/~knuth/programs.html