B计划之大数的表示

无心人

由于存在10进制和2进制的快速转换算法 所以，我觉得在算法里用2进制表示是最合适的 那么用多少位2进制做单位比较合适呢？ 无论如何，8位、16位都是不能用于大数的表示的，效率太低的 那么剩下的选择是32、64、128 如果仅考虑运算的方便，我们可以选择32位 但考虑到多媒体指令级的运用可以大大简化和提高效率 那么128位是一个不错的选择了 128位，运算时可以方便拆分成2个64位或者4个32位 无论用于ALU还是MMX还是SSE都是很方便的 同时在表示上也不会浪费很多空闲位 在内存处理上，128位可以对齐16字节 能很迅速的复制和装入数据 现在的问题是如何定义一个普遍的128位的变量呢？

gxqcn

可以先定义一个 128bits 的结构，并申明16字节对齐（需编译器支持）， 然后再定义以该结构为元素的数组或链表，就看需求了。 不过，不建议自定义单元采用比系统 int 更大的粒度，比如128位连基本的四则运算都成问题，整体效率怎么提高？

无心人

为了快速复制啊 省的再考虑不是128倍数了 另外，似乎加法也能得到加速？ 外部定义128位，内部实现还是可以64位或者32位运算的啊

无心人

考虑好了 目前还是以双字为最小单位 但是长度总是4的倍数 即二进长度是128倍数

liangbch

我的观点如下： 1.和gxq的观点相同，大数采用2种进制。2进制和10进制。2进制的内部表示以$2^30$为基。10进制的内部表示以$10^9$为基。 2.大数表示采用和intel相反的顺序，和书写顺序一致。高位在前，低位在后。这样带来的好处是，转为为串输出比较方便。也便于实现任意精度（非完全精度），当缩减精度时很方便。 3.采用10^9进制，对于乘法效率的提高有很大帮助，对应2进制，对于乘法和加法的效率也能带来帮助。

无心人

老大 你正好说反了 Intel顺序才好缩减精度呢 只要把串长度减少就可以了 至于输出 GxQ有体会吧 和进制无关的

liangbch

原帖由 无心人 于 2008-4-10 20:10 发表 老大 你正好说反了 Intel顺序才好缩减精度呢 只要把串长度减少就可以了 至于输出 GxQ有体会吧 和进制无关的

没有说反，缩减精度应该是丢弃次要数字，保留最重要的数字。如 0x12345678在内存中的存储顺序为0x78,0x56,0x34,0x12.如果缩减长度2个字节则变为0x5678,如此一来，最重要的数字丢失了，这样不是精度降低而是完全错误了。

无心人

明白了 和我说的不是一个事情啊 不过可惜 这个功能没什么用处 而且大部分软件包都不这么做吧 大头方式某些基本操作不容易做吧? 比如加法，就无法保证两个整数对齐16字节 会影响速度的

gxqcn

我用的是与Intel顺序一致。 大数计算，头尾都可能随时面临插入删除。合理的数据结构至关重要。 至于输出，与大头在前在后关系不大（尤其是我那种进制不存在“劈开断裂”问题）

无心人

两个运算大头不好做 就是长串乘双字 长串加双字 可能都存在进位 如何解决？ 还有长串除以双字，存在缩减字长的问题，如何解决？