找回密码
 欢迎注册
查看: 37469|回复: 46

[讨论] B计划之大数的表示

[复制链接]
发表于 2008-3-29 09:01:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
由于存在10进制和2进制的快速转换算法
所以,我觉得在算法里用2进制表示是最合适的
那么用多少位2进制做单位比较合适呢?
无论如何,8位、16位都是不能用于大数的表示的,效率太低的
那么剩下的选择是32、64、128
如果仅考虑运算的方便,我们可以选择32位
但考虑到多媒体指令级的运用可以大大简化和提高效率
那么128位是一个不错的选择了
128位,运算时可以方便拆分成2个64位或者4个32位
无论用于ALU还是MMX还是SSE都是很方便的
同时在表示上也不会浪费很多空闲位
在内存处理上,128位可以对齐16字节
能很迅速的复制和装入数据
现在的问题是如何定义一个普遍的128位的变量呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-29 09:36:09 | 显示全部楼层
可以先定义一个 128bits 的结构,并申明16字节对齐(需编译器支持),
然后再定义以该结构为元素的数组或链表,就看需求了。

不过,不建议自定义单元采用比系统 int 更大的粒度,比如128位连基本的四则运算都成问题,整体效率怎么提高?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-29 10:59:54 | 显示全部楼层
为了快速复制啊
省的再考虑不是128倍数了
另外,似乎加法也能得到加速?

外部定义128位,内部实现还是可以64位或者32位运算的啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-29 20:53:12 | 显示全部楼层
考虑好了
目前还是以双字为最小单位
但是长度总是4的倍数
即二进长度是128倍数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-10 19:53:38 | 显示全部楼层
我的观点如下:
   1.和gxq的观点相同,大数采用2种进制。2进制和10进制。2进制的内部表示以$2^30$为基。10进制的内部表示以$10^9$为基。
   2.大数表示采用和intel相反的顺序,和书写顺序一致。高位在前,低位在后。这样带来的好处是,转为为串输出比较方便。也便于实现任意精度(非完全精度),当缩减精度时很方便。
   3.采用10^9进制,对于乘法效率的提高有很大帮助,对应2进制,对于乘法和加法的效率也能带来帮助。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-10 20:10:41 | 显示全部楼层
老大
你正好说反了
Intel顺序才好缩减精度呢
只要把串长度减少就可以了
至于输出
GxQ有体会吧
和进制无关的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-10 20:46:21 | 显示全部楼层
原帖由 无心人 于 2008-4-10 20:10 发表
老大
你正好说反了
Intel顺序才好缩减精度呢
只要把串长度减少就可以了
至于输出
GxQ有体会吧
和进制无关的

没有说反,缩减精度应该是丢弃次要数字,保留最重要的数字。如 0x12345678在内存中的存储顺序为0x78,0x56,0x34,0x12.如果缩减长度2个字节则变为0x5678,如此一来,最重要的数字丢失了,这样不是精度降低而是完全错误了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-10 20:53:11 | 显示全部楼层


明白了
和我说的不是一个事情啊

不过可惜
这个功能没什么用处

而且大部分软件包都不这么做吧
大头方式某些基本操作不容易做吧?
比如加法,就无法保证两个整数对齐16字节
会影响速度的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-10 21:17:40 | 显示全部楼层
我用的是与Intel顺序一致。

大数计算,头尾都可能随时面临插入删除。合理的数据结构至关重要。
至于输出,与大头在前在后关系不大(尤其是我那种进制不存在“劈开断裂”问题)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-10 21:26:10 | 显示全部楼层
两个运算大头不好做
就是长串乘双字
长串加双字
可能都存在进位
如何解决?
还有长串除以双字,存在缩减字长的问题,如何解决?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-19 19:36 , Processed in 0.052267 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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