标题:☆★百分英雄帖★☆ 如果要你表示一个超过千万位的大整数你会用什么办法实现 ...
只看楼主
jack10141
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:陕西西安
等 级:小飞侠
威 望:6
帖 子:706
专家分:2271
注 册:2010-8-10
结帖率:100%
已结贴  问题点数:100 回复次数:16 
☆★百分英雄帖★☆ 如果要你表示一个超过千万位的大整数你会用什么办法实现?
在处理大数运算的时候,我们习惯用到的办法是用基10、基10000或者基32768的办法把相应的数字存放到数组的元素中去,数组中的一个元素存放相应的一个数位的数字,然后整个数组就是我们要表示的大整数。
但是虽然C本身并没有规定数组元素个数的最大值,但是编译器都会有自己的局限,比如:
TC2.0 数组最多元素个数为16383(TC编译器限制)
GCC for windows 数组最多元素个数为520756(经试验得到的不出错的最大值)
..........
显然,用数组表示大数的方法似乎不能很好的解决千万位数量级的大整数,那么如果是你的话你会用什么数据结构来表示这样的大整数呢??当然我们可以想到不少的办法,但是如果我们考虑这么大的一个数需要进行加减乘除的四则运算的时候,兼顾效率,你认为什么处理办法是最优的?


[ 本帖最后由 jack10141 于 2010-8-29 01:45 编辑 ]
搜索更多相关主题的帖子: 办法 英雄 整数 
2010-08-29 01:43
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
得分:10 
http://

专心编程………
飞燕算法初级群:3996098
我的Blog
2010-08-29 02:01
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
得分:10 
以下是引用jack10141在2010-8-29 01:43:20的发言:

在处理大数运算的时候,我们习惯用到的办法是用基10、基10000或者基32768的办法把相应的数字存放到数组的元素中去,数组中的一个元素存放相应的一个数位的数字,然后整个数组就是我们要表示的大整数。
但是虽然C本身并没有规定数组元素个数的最大值,但是编译器都会有自己的局限,比如:
TC2.0 数组最多元素个数为16383(TC编译器限制)
GCC for windows 数组最多元素个数为520756(经试验得到的不出错的最大值)
..........
显然,用数组表示大数的方法似乎不能很好的解决千万位数量级的大整数,那么如果是你的话你会用什么数据结构来表示这样的大整数呢??当然我们可以想到不少的办法,但是如果我们考虑这么大的一个数需要进行加减乘除的四则运算的时候,兼顾效率,你认为什么处理办法是最优的?
你在搞笑吧?我直接开个64M的数组都不成问题,这个数组能表示2亿位的大整数了,御坂回答

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2010-08-29 02:43
Windy0Winll
Rank: 2
来 自:走了
等 级:等待验证会员
帖 子:71
专家分:90
注 册:2010-8-26
得分:10 
我以前写过这样一个结构:
程序代码:
#define N      2

typedef struct int128 {
        unsigned char status ;      // 状态
        union {
              int32 val32[ 2*N+1 ]; // int32是自己定义的一个无符号32位类型
              int64 val64[   N   ]; // int32是自己定义的一个无符号64位类型
              }val;   
        }int128;
然后自己来实现各种运算(位运算和四则运算)。当时那个程序是用来练习的,没有考虑小数。如果确实需要的话,再在int128结构中加一个联合类型来保存小数部分的数据。这也还是用2进制来表示10进制数的。这样也就可以用 正数 求反加1 的方法来表示负数。在实现加法和乘法的时候用32位数来做为操作数,得到的结果保存在64位数中,(两个32位数相加或相乘的结果决不会超过64位)。
不过我觉得的这个方案没有直接用10作基有效率(在书上我看到一个基10的方案的乘法是用查表法实现的)。如果直接用数组和基10来实现的话不仅比较浪费空间,效率也不怎么高(在处理进位的时候有点麻烦)。

悄悄地来。。。 然后悄悄地走。。。。。。
2010-08-29 04:15
jack10141
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:陕西西安
等 级:小飞侠
威 望:6
帖 子:706
专家分:2271
注 册:2010-8-10
得分:0 
以下是引用御坂美琴在2010-8-29 02:43:15的发言:

你在搞笑吧?我直接开个64M的数组都不成问题,这个数组能表示2亿位的大整数了,御坂回答
那么你来说说进行四则运算的时候,效率如何更高??

Coding就像一盒巧克力,你永远不会知道你会遇到什么BUG
别跟我说你是不能的,这让我愤怒,因为这侮辱了你的智慧
2010-08-29 21:44
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
得分:40 
以下是引用jack10141在2010-8-29 21:44:42的发言:

那么你来说说进行四则运算的时候,效率如何更高??
所有运算压位,为了通用全压4位(或者64位系统上压8位)。加减法直接做,乘除全部用FFT。

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2010-08-29 21:49
pkwangxinjun
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:45
专家分:170
注 册:2010-8-29
得分:10 
采用数组存储    超长的数字计算的话可以采用满9999进进一的方法来
这个论坛里以前不是有个疯狂编程的例子吗  求2的十万次幂 楼主可以看下哈
2010-08-29 22:22
Spygg
Rank: 5Rank: 5
等 级:职业侠客
帖 子:135
专家分:394
注 册:2007-5-20
得分:10 
回复 7楼 pkwangxinjun
这个有理.
2010-08-29 23:02
jack10141
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:陕西西安
等 级:小飞侠
威 望:6
帖 子:706
专家分:2271
注 册:2010-8-10
得分:0 
以下是引用pkwangxinjun在2010-8-29 22:22:00的发言:

采用数组存储    超长的数字计算的话可以采用满9999进进一的方法来
这个论坛里以前不是有个疯狂编程的例子吗  求2的十万次幂 楼主可以看下哈
hehe 2的10W次幂,结果数量级达不到10进制的千万数量级吧?差得很远呢!!

Coding就像一盒巧克力,你永远不会知道你会遇到什么BUG
别跟我说你是不能的,这让我愤怒,因为这侮辱了你的智慧
2010-08-30 08:54
以中
Rank: 3Rank: 3
来 自:长沙
等 级:论坛游侠
帖 子:108
专家分:129
注 册:2010-4-13
得分:0 
回复 2楼 StarWing83
老大,你要做什么?

道之所存,师之所存。
2010-08-30 12:09



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-317086-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.159776 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved