liangbch 发表于 2008-4-30 10:15:38

原帖由 无心人 于 2008-4-30 10:07 发表 http://images.5d6d.net/dz60/common/back.gif
:)

16字节对齐是编译器做的事情,我?
我不需要做
我自己分配的内存,编译器或者操作系统
似乎默认就是16字节对齐的吧

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

gxqcn 发表于 2008-4-30 10:19:20

回复 31# 的帖子

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

无心人 发表于 2008-4-30 10:20:20

:)

我也没要求子程序是16字节对齐啊

只要是操作系统参与的分配,都是16字节对齐的啊

你不会自己实现内存池吧?

我不会,我对效率的要求还没这么高

我的最核心部分设想的是完美条件 :)

无心人 发表于 2008-4-30 10:21:45

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

gxqcn 发表于 2008-4-30 10:29:09

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

无心人 发表于 2008-4-30 10:31:16

:)

老大我都解释了

可能是1024我说的有冲突和矛盾的地方

但1024只是分配单位,不是运算单位,运算以最有效率方式进行
数字自己会记住自己的有效长度的

另外,我不会考虑你们的阶乘算法的,那是你们库要做的事情

ssikkiss 发表于 2010-7-4 17:43:14

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

liangbch 发表于 2010-7-7 11:56:27

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++的语法来封装。

无心人 发表于 2010-7-7 12:38:09

:)

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

liangbch 发表于 2010-7-7 15:45:57

如果使用MMX和SSE指令做64bit数加法,2^30进制就有优势了,使用2^30进制,可使用MMX或者SSE/SSE2指令做连续16次乘积的累加,而采用2^32进制,则无法直接使用MMX或者SSE/SSE2对2个64bit数做加法。
页: 1 2 3 [4] 5
查看完整版本: B计划之大数的表示