找回密码
 欢迎注册
楼主: 无心人

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

[复制链接]
发表于 2008-4-30 10:15:38 | 显示全部楼层
原帖由 无心人 于 2008-4-30 10:07 发表


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


  不对,我们在做大整数运算时,需要的计算的操作数的地址可能是通过 内存分配函数得到的, 但更多的可能数位于某个内存块的某一个位置。如kara_mul中将操作数分成 一些小的片段,并且对这些小的片段频繁的做 内存复制,大数加法,大数减法,你不能保证这些小的片段的地址是16字节对齐,而你的子程序必须要求16字节对齐,为此。你必须将这些小的片段复制到16对齐的内存块中,这样只能使得效率下降很多。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-30 10:19:20 | 显示全部楼层

回复 31# 的帖子

与我在 20# 要说的论点一致。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-30 10:20:20 | 显示全部楼层


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

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

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

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

我的最核心部分设想的是完美条件 :)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-30 10:21:45 | 显示全部楼层
另外,karatsuba算法的迭代层次不是很多的,我估计不超过6层
不会存在频繁的内存分配问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-30 10:29:09 | 显示全部楼层
如果非要16字节对齐,又要尽量避免数据迁移,势必:
1、内存的浪费:尤其在大整数对象很多时(比如算大数阶乘的初级阶段);
2、计算的浪费:因为端头连续的零也不得不参与常规计算。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-30 10:31:16 | 显示全部楼层


老大我都解释了

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

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

另外,我不会考虑你们的阶乘算法的,那是你们库要做的事情
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-4 17:43:14 | 显示全部楼层
请问下2^30进制和2^32进制有什么区别?
还有具体是怎么的实现,用的C语言的struct还是C++的class?(不可能是一个裸数组吧)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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已经淘汰了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-7 15:45:57 | 显示全部楼层
如果使用MMX和SSE指令做64bit数加法,2^30进制就有优势了,使用2^30进制,可使用MMX或者SSE/SSE2指令做连续16次乘积的累加,而采用2^32进制,则无法直接使用MMX或者SSE/SSE2对2个64bit数做加法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-19 13:50 , Processed in 0.054939 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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