无心人 发表于 2009-1-12 09:39:36

10^n的二进制表示

对所有的n <= 20的
10^n寻找小于n项的二进制幂的加减表示

比如1000正常的是9, 8, 7, 6, 5, 3共6个2的方幂加在一起
可以表示为9+8+7+6+5+3
但存在1000=2^10-2^4-2^3的结果
即最短表示是10-4-3

求出满足题目的最短表示

medie2005 发表于 2009-1-12 09:44:53

动态规划.

无心人 发表于 2009-1-12 10:21:56

:)

给出结果
我想知道结果
为了快速的乘以10^n用

admin 发表于 2009-1-12 10:31:03

一次乘法可能比三次“移位+加减”还快吧？

gxqcn 发表于 2009-1-12 10:32:34

对不起，忘了脱马甲了。:lol :lol

无心人 发表于 2009-1-12 10:33:46

一次乘法是9个时钟
三次移位加减是1.5时钟
乘法吞吐量是2
加减移位是0.5
你说谁快？

无心人 发表于 2009-1-12 10:34:57

:lol

不过谢谢你提醒
我要重新评估下
大于10000的10的方幂的乘法了

gxqcn 发表于 2009-1-12 10:39:07

原帖由 无心人 于 2009-1-12 10:33 发表 http://bbs.emath.ac.cn/images/common/back.gif
一次乘法是9个时钟
三次移位加减是1.5时钟
乘法吞吐量是2
加减移位是0.5
你说谁快？

你说的是老型号的CPU，
新的CPU中MUL指令的时钟数很小了。

无心人 发表于 2009-1-12 11:19:09

呵呵

需要测试下么？

tprime 发表于 2009-1-12 11:33:17

回复 9# 无心人 的帖子

主流CPU 32位整数乘法要4个时钟左右
页: [1] 2 3
查看完整版本: 10^n的二进制表示