求幂快速算法

无心人 · 发表于 2008-12-23 21:09:13

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

gxqcn · 发表于 2008-12-23 21:15:56

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

没看明白。

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

无心人 · 发表于 2008-12-23 21:42:53

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

无心人 · 发表于 2008-12-23 21:44:27

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

gxqcn · 发表于 2008-12-23 22:01:12

我琢磨了一下，其实“加法链”本身即包含了二进制法和因子法，只是其出发点不同、研究思路不同罢了。

比如，主帖举例的：$x^55$ 的
二进制法的加法链为：{ 1, 2, 3, 6, 12, 13, 26, 27,54, 55 }
因子法的加法链则为：{ 1, 2, 4, 5, 10, 20, 40, 50, 55 }

无心人 · 发表于 2008-12-23 22:02:51

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

gxqcn · 发表于 2008-12-23 22:07:50

赞同！

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

无心人 · 发表于 2008-12-23 22:09:14

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

gxqcn · 发表于 2008-12-23 22:15:16

这个有待再研究了。

我今天有点感冒就请假在家休息一天，现在得休息了。

无心人 · 发表于 2008-12-23 22:19:10

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 求幂快速算法