求幂快速算法

无心人

比如29 构造1， 2， 3是否足够？

gxqcn

原帖由 无心人 于 2008-12-23 21:09 发表 比如29 构造1， 2， 3是否足够？

没看明白。 注意在加法链中的数字表示计算 $x^n$ 过程中的一些中间结果的幂指数。

无心人

我的意思是否能借助一个精心构造的序列 来混合利用二进制算法和加法链

无心人

比如针对255以下数字 该序列都能把乘法次数控制到5次内？ （可能的情况）

gxqcn

我琢磨了一下，其实“加法链”本身即包含了二进制法和因子法，只是其出发点不同、研究思路不同罢了。 比如，主帖举例的：$x^55$ 的 二进制法的加法链为：{ 1, 2, 3, 6, 12, 13, 26, 27,54, 55 } 因子法的加法链则为：{ 1, 2, 4, 5, 10, 20, 40, 50, 55 }

无心人

因子法等于利用了多个素因子 二进制只考虑2

gxqcn

赞同！ 但也把问题搞复杂了，可能实用价值反而不高。

无心人

如果只考虑因子2， 3， 5， 7是否能达到折中呢？

gxqcn

这个有待再研究了。 我今天有点感冒就请假在家休息一天，现在得休息了。

无心人