找回密码
 欢迎注册
楼主: gxqcn

[讨论] 求幂快速算法

[复制链接]
发表于 2008-12-23 21:09:13 | 显示全部楼层
比如29 构造1, 2, 3是否足够?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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次内? (可能的情况)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-23 22:07:50 | 显示全部楼层
赞同! 但也把问题搞复杂了,可能实用价值反而不高。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-12-23 22:09:14 | 显示全部楼层
如果只考虑因子2, 3, 5, 7是否能达到折中呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-23 22:15:16 | 显示全部楼层
这个有待再研究了。 我今天有点感冒就请假在家休息一天,现在得休息了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-12-23 22:19:10 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-21 18:12 , Processed in 0.028306 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表