应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程第十六题：2的1000次方的各项和
151/2返回列表12下一页
查看: 2591  |  回复: 14
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 2 个 程序强帖 ，点击这里进行查看

holmescn

金虫 (正式写手)

[交流] Euler 工程第十六题：2的1000次方的各项和 已有6人参与

这两天新版开通，版里很热闹，也就没有放题出来。今天放一个题吧。

已知2的15次方等于32768，其各项和为：3+2+7+6+8 ＝ 26 。
那么2的1000次方的各项和是多少呢？
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
1楼 2011-05-26 21:06:30
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+2): 谢谢参与！ 2011-05-27 15:24:11
来个Perl版：
CODE:
#!/usr/bin/perl
use bigint;
$sum += $_ foreach(2**1000 =~ /(.)/g);
print "result:$sum\n";

结果：1366
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
2楼2011-05-26 21:38:51
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+2): 谢谢交流讨论！ 2011-05-27 15:24:41
引用回帖:
Originally posted by huycwork at 2011-05-26 21:38:51:
来个Perl版：
CODE:
#!/usr/bin/perl
use bigint;
$sum += $_ foreach(2**1000 =~ /(.)/g);
print "result:$sum\n";

结果：1366

咳，我突然想到一个好玩的东西...

对于一个数的大指数出来的各个位数，0-9的概率分布趋向于均匀分布~

那么我们可以做大致的估算：

2^1000的位数为

向下取整(1000 * log 2) + 1 = 302 位

对于每个位的期望为4.5，然后所有位的和就约等于

302 * 4.5 = 1359

很接近，数学真是奇妙啊，哈哈哈~

嗯，回到正题，这个题考的是两个东西：

1. 大数乘法
2. 整数动态规划，求最少大数乘法次数的步骤

好的C算法在一般PC上应该能把运算时间控制在0.5秒以内，嗯~

PS：土土地思考，从2^31=2147483648开始算的话：
2^31 * 2^31 = 2^62
2^62 * 2^62 = 2^124
2^124 * 2 = 2^125
2^125 * 2^125 = 2^250
2^250 * 2^250 = 2^500
2^500 * 2^500 = 2^1000
只需要6次大数乘法，嗯，不确保这是最优的分法...不过这么算已经挺快了...

[ Last edited by sudo on 2011-5-26 at 22:13 ]
赞一下(2人) 回复此楼
3楼2011-05-26 21:52:34
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+1): 谢谢交流讨论！ 2011-05-27 15:26:19
引用回帖:
Originally posted by sudo at 2011-05-26 21:52:34:
咳，我突然想到一个好玩的东西...

对于一个数的大指数出来的各个位数，0-9的概率分布趋向于均匀分布~

那么我们可以做大致的估算：

2^1000的位数为

向下取整(1000 * log 2) + 1 = 302 位

对于 ...

这么说的话，这个好玩的东西还有另外一个扩展了：散列码，乘法运算的过程中，除了首位和末位之外，中间的所有位都与因数的位数相关，得出的结果中包含了各种离散的因素，得出的值也必定是均匀分散的。期望值应该也非常接近这样的猜测

这题以乘方来优化的话，乘法次数是少了许多，效率却不见提高许多，软件实现的大数类还是不如硬件geilivable啊……

突然想实现一个补码运算的大数类了
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
4楼2011-05-26 22:29:58
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
Originally posted by huycwork at 2011-05-26 22:29:58:
这么说的话，这个好玩的东西还有另外一个扩展了：散列码，乘法运算的过程中，除了首位和末位之外，中间的所有位都与因数的位数相关，得出的结果中包含了各种离散的因素，得出的值也必定是均匀分散的。期望值应 ...

没听说过什么硬件实现了大数运算诶...
赞一下(1人) 回复此楼
5楼2011-05-26 22:37:29
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
Originally posted by sudo at 2011-05-26 22:37:29:
没听说过什么硬件实现了大数运算诶...

那我们不是2^32次方以下的数都没法算了？
赞一下(1人) 回复此楼
漩涡的中心有一块空地，空空的。
6楼2011-05-26 22:42:09
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
Originally posted by huycwork at 2011-05-26 22:42:09:
那我们不是2^32次方以下的数都没法算了？

=,=这个不能算“大数”吧...
赞一下(1人) 回复此楼
7楼2011-05-26 22:44:24
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

微尘、梦想

木虫 (知名作家)
★
小木虫(金币+0.5):给个红包，谢谢回帖
就让我幻想一下吧：
开辟1001位的内存A，高位置1，其余位置0，再开辟4位内存，放上1010，如果刚好有这么一条指令DIV AB，表示A除以B，商返回给A，余数返回给B，然后进行一个循环，把B中的数相加，就是答案了。

我实现不了啊！
赞一下(1人) 回复此楼
任风云变幻，我笑对人生！
8楼2011-05-26 22:51:08
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+1): 谢谢交流！ 2011-05-27 15:26:38
引用回帖:
Originally posted by sudo at 2011-05-26 22:44:24:
=,=这个不能算“大数”吧...

把寄存器调大一些不就可以了嘛~
不过这电路板就复杂了，严重怀疑散热性能

我最近就实现了一个基于位的模板类，效率很不高啊，就是因为减少乘法次数引入了负数，整个代码都复杂了。
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
9楼2011-05-26 22:51:36
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
引用回帖:
Originally posted by 微尘、梦想 at 2011-05-26 22:51:08:
就让我幻想一下吧：
开辟1001位的内存A，高位置1，其余位置0，再开辟4位内存，放上1010，如果刚好有这么一条指令DIV AB，表示A除以B，商返回给A，余数返回给B，然后进行一个循环，把B中的数相加，就是答案 ...

你这还竖式除法了都

以10为模进行多项式乘法计算，简单又划算。
赞一下 回复此楼
漩涡的中心有一块空地，空空的。
10楼2011-05-26 22:59:45
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
151/2返回列表12下一页
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 在坚冰还盖着北海的时候，我看到了怒放的梅花。 (金币+10) +7 ziyangfang 2026-08-25 10/500 2026-09-01 09:32 by qvbaoxiao
[基金申请] 面上函评意见出来了，像什么等级？ 20+3 Tsingking1 2026-08-27 14/700 2026-09-01 08:29 by 尼古拉斯小虫
[基金申请] 怎么看青基中了没有啊 +6 叶九微 2026-08-26 6/300 2026-08-31 23:54 by yudaoqian88
[文学芳草园] 梦想 +5 myrtle 2026-08-26 5/250 2026-08-31 14:40 by hahaboy
[基金申请] 中青基了要发朋友圈吗？ +7 349506619 2026-08-28 7/350 2026-08-31 13:39 by 冼亮淀粉酶
[基金申请] 29号明天会评吗 +4 笨笨唐 2026-08-28 4/200 2026-08-31 09:30 by huixian257
[基金申请] 为什么到现在没收到通知？ +5 tannykie 2026-08-29 5/250 2026-08-30 21:05 by purplejack
[基金申请] 有没有仍没收到信息的 +7 德尚中行 2026-08-27 8/400 2026-08-30 20:52 by purplejack
[考博] 找导师 +6 yuanjiabao 2026-08-29 7/350 2026-08-30 14:40 by 生科新手
[基金申请] 国自然评审意见 +13 wangmingqi 2026-08-28 19/950 2026-08-29 10:22 by Poppy1104
[基金申请] 2026年叶企孙基金 +4 bud_bud 2026-08-27 7/350 2026-08-29 07:23 by foolishmani
[基金申请] 基金系统什么内容也没有 30+4 winsaint 2026-08-27 9/450 2026-08-28 11:06 by maolC
[基金申请] 我不理解！ +15 Edward_pc 2026-08-26 23/1150 2026-08-26 20:34 by zzuzxg
[基金申请] 出来了 +9 trojank 2026-08-26 9/450 2026-08-26 14:25 by 宝贝虫子
[基金申请] 为什么国自然不能直接公布 +4 bjdxyxy 2026-08-26 4/200 2026-08-26 13:12 by qingmu1201
[基金申请] 国合里面能看到了 +7 一怀馨秋 2026-08-26 7/350 2026-08-26 11:23 by zhaosm1982
[基金申请] 国际合作可查了，中了面上 (EPI+1)(金币+50) +18 Ldrop2023 2026-08-26 18/900 2026-08-26 11:15 by cmrandy
[基金申请] 项目信息和经费信息在系统里都可以看到了 +6 wittyboy 2026-08-26 14/700 2026-08-26 10:55 by wittyboy
[基金申请] 国合可查了 +3 paperzjh 2026-08-26 3/150 2026-08-26 10:41 by LemmonTr
[基金申请] 牛来！米来！面来！ +8 beefly 2026-08-26 8/400 2026-08-26 08:37 by xuzhipiao
信息提示
关闭
请填处理意见
关闭