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

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

[复制链接]
 楼主| 发表于 2008-4-29 21:28:33 | 显示全部楼层
很久没动这个了

写点新的感受

我想如果是32位CPU
分配的最小单位是1024bit也就是32个32位

为什么呢?

因为,正好是8个128位,无论使用什么方法
都可以做最大8路的展开算法了

:)

另外,对未来使用64位,也能符合一次8个128位或者16个64位的展开要求

我想,这是比较合适的选择
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-29 21:44:23 | 显示全部楼层
还是以前的观点,不建议采用这么大的单位。
比如RSA,常常使用512bit的整数,你用这么大的单位,存储空间整整浪费了1倍,计算乘法时,乘法运算的次数增加到原先的4倍。
浪费太严重了!!!
浪费太严重了!!!
浪费太严重了!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-29 21:56:51 | 显示全部楼层
你太激动了啊

1024是底层的bit块大小
但初始的长度是32位啊

也就是说
参与运算的实际大小以实际值参与运算

选择1024不过方便操作而已
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-30 07:37:20 | 显示全部楼层
大数运算免不了要“左移”、“右移”运算(许多加速算法有此需求),

如果说需要“左移”一个基本单元,
正常的不过是在数据结构的头或尾插入一个基本单元,

而如果是采用1024bit的大单元,
必须在插入后还有进行额外的数据的迁移,
使高效的“移位”运算效率大打折扣!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-30 07:42:40 | 显示全部楼层


两位老大

我的1024是最小分配单位
而不是最小操作单位

我敢用这么大数据运算么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-30 07:52:04 | 显示全部楼层
我在 14# 说的还有另一层意思:

如果考虑16bytes对齐(或更高的1024bits对齐),
有时需要额外大数据迁移,非常不划算。

至于内存分配管理模式,似乎与“大数的表示”不相关了吧?
它更多的是一种策略,目的仍然是尽可能地减少数据迁移次数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-30 08:08:35 | 显示全部楼层


1024只是一个尺度

而不是一个对齐的依据

对齐还是以16字节为准的好

你说的数据迁移的具体含义是什么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-30 09:20:47 | 显示全部楼层
所谓的“数据迁移”,主要发生在:
1、数据的正常备份
2、无法直接插入新的(或删除旧的)数据单元时
3、为字节对齐(可选项)

其中:
第1项应尽可能避免不必要的次数;
第2项可通过合理的数据结构减少数据迁移的发生频次(但也要兼顾读写效率);
第3项如果仅为了内部实现的便利,如果效率提升轻微,不用也罢。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-30 09:24:14 | 显示全部楼层
1、和1024无关,备份只备份有效数字就可,源和目的的1024仅是分配块大小
2、大数核心运算不存在插入删除操作,即使外围有,也是1的变形啊
3、有关系,有很大关系,有的操作16字节对齐的效率提升明显,最简单的是逻辑运算、复制、比较大小、清零等
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-30 09:39:23 | 显示全部楼层
插入:乘以 内部进制的若干次方
删除:除以 内部进制的若干次方(也可仅移动首指针)

如果为了16字节对齐,
那么,在用Karatsuba、Toom等算法分段时不得不考虑必须16字节整数倍分段,
而且分段后首部或尾部某些连续的“0”也不得不参与运算。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-19 16:17 , Processed in 0.047320 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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