B计划之大数的表示

liangbch

原帖由 无心人 于 2008-4-30 10:07 发表 16字节对齐是编译器做的事情，我？ 我不需要做 我自己分配的内存，编译器或者操作系统 似乎默认就是16字节对齐的吧

不对，我们在做大整数运算时，需要的计算的操作数的地址可能是通过 内存分配函数得到的， 但更多的可能数位于某个内存块的某一个位置。如kara_mul中将操作数分成 一些小的片段，并且对这些小的片段频繁的做 内存复制，大数加法，大数减法，你不能保证这些小的片段的地址是16字节对齐，而你的子程序必须要求16字节对齐，为此。你必须将这些小的片段复制到16对齐的内存块中，这样只能使得效率下降很多。

gxqcn

与我在 20# 要说的论点一致。

无心人

我也没要求子程序是16字节对齐啊 只要是操作系统参与的分配，都是16字节对齐的啊 你不会自己实现内存池吧？ 我不会，我对效率的要求还没这么高 我的最核心部分设想的是完美条件 ：）

无心人

另外，karatsuba算法的迭代层次不是很多的，我估计不超过6层 不会存在频繁的内存分配问题

gxqcn

如果非要16字节对齐，又要尽量避免数据迁移，势必： 1、内存的浪费：尤其在大整数对象很多时（比如算大数阶乘的初级阶段）； 2、计算的浪费：因为端头连续的零也不得不参与常规计算。

无心人

老大我都解释了 可能是1024我说的有冲突和矛盾的地方 但1024只是分配单位，不是运算单位，运算以最有效率方式进行 数字自己会记住自己的有效长度的 另外，我不会考虑你们的阶乘算法的，那是你们库要做的事情

ssikkiss

请问下2^30进制和2^32进制有什么区别？ 还有具体是怎么的实现，用的C语言的struct还是C++的class？（不可能是一个裸数组吧）

liangbch

2^30进制和2^32进制的主要区别是， 对于2^30进制，可以做到16次乘积的累加和不超过2^64,因此在计算乘积的累加和时，只需要使用1条add指令和1条adc指令。 对于2^32进制，每次累加和都可能超过2^64,因此在累加和时，只需要使用1条add指令和2条adc指令。由于adc指令的代价很高，用2^30进制的速度可能高于2^32进制，尽管操作数的长度增加1/15. 用的C语言的struct还是C++的class其实并无本质差别。一般的，我们更愿意在底层使用C的语法来封装，在高层使用C++的语法来封装。

无心人

用SSE2等指令，不存在adc进位加 现在不支持SSE2的 CPU已经淘汰了

liangbch

如果使用MMX和SSE指令做64bit数加法，2^30进制就有优势了,使用2^30进制，可使用MMX或者SSE/SSE2指令做连续16次乘积的累加，而采用2^32进制，则无法直接使用MMX或者SSE/SSE2对2个64bit数做加法。