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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程第十六题：2的1000次方的各项和
151/2返回列表12下一页
查看: 2174  |  回复: 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下一页
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 294求调剂材料与化工专硕 +10 陌の森林 2026-03-18 10/500 2026-03-19 12:35 by peike
[考研] 287求调剂 +3 晨昏线与星海 2026-03-19 4/200 2026-03-19 12:32 by peike
[考研] 328求调剂，英语六级551，有科研经历 +4 生物工程调剂 2026-03-16 12/600 2026-03-19 11:10 by 生物工程调剂
[考研] 一志愿中海洋材料工程专硕330分求调剂 +7 小材化本科 2026-03-18 7/350 2026-03-19 10:46 by Linda Hu
[考研] 材料工程专硕调剂 +5 204818@lcx 2026-03-17 6/300 2026-03-18 22:55 by 204818@lcx
[考研] 297求调剂 +8 戏精丹丹丹 2026-03-17 8/400 2026-03-18 14:30 by laoshidan
[考研] 070300化学319求调剂 +6 锦鲤0909 2026-03-17 6/300 2026-03-18 13:22 by Iveryant
[考研] 材料，纺织，生物（0856、0710），化学招生啦 +3 Eember. 2026-03-17 9/450 2026-03-18 10:28 by Eember.
[硕博家园] 湖北工业大学 生命科学与健康学院-课题组招收2026级食品/生物方向硕士 +3 1喜春8 2026-03-17 5/250 2026-03-17 17:18 by ber川cool子
[考研] 材料工程专硕274一志愿211求调剂 +6 薛云鹏 2026-03-15 6/300 2026-03-17 11:05 by 学员h26Tkc
[考研] 一志愿，福州大学材料专硕339分求调剂 +3 木子momo青争 2026-03-15 3/150 2026-03-17 07:52 by laoshidan
[考研] 304求调剂 +3 曼殊2266 2026-03-14 3/150 2026-03-16 16:39 by houyaoxu
[考研] 一志愿华中师范071000，325求调剂 +6 RuitingC 2026-03-12 6/300 2026-03-16 14:50 by 可淡不可忘
[考研] 26考研一志愿中国石油大学(华东)305分求调剂 +3 嘉年新程 2026-03-15 3/150 2026-03-15 13:58 by 哈哈哈哈嘿嘿嘿
[考研] 材料与化工 323 英一+数二+物化，一志愿：哈工大 本人本科双一流 +4 自由的_飞翔 2026-03-13 5/250 2026-03-14 19:39 by hmn_wj
[考研] 289求调剂 +4 这么名字咋样 2026-03-14 6/300 2026-03-14 18:58 by userper
[考研] 0856材料与化工301求调剂 +5 奕束光 2026-03-13 5/250 2026-03-13 22:00 by 星空星月
[考研] 304求调剂 +7 7712b 2026-03-13 7/350 2026-03-13 21:42 by peike
[考研] 26调剂/材料科学与工程/总分295/求收留 +9 2026调剂侠 2026-03-12 9/450 2026-03-13 20:46 by 18595523086
[考研] 321求调剂（食品/专硕） +3 xc321 2026-03-12 6/300 2026-03-13 08:45 by xc321
信息提示
关闭
请填处理意见
关闭