回 帖 发 新 帖 刷新版面

主题:对高精度运算实现的一个假想

这个假想是从类型的角度来分析的。
  类型,我是这样理解的:用来保存数据的一种方案。根据这种方案来对数据进行各种操作等。c语言提供了struct和union等来实现自己设计这个存储方案。当然有时候过分依赖具体的存储结构会使得代码的可移植性很差。可以说,一种类型,实际上是一个算法。
  c语言的long long通常情况下是8字节。有时候8字节还不足以表示一个数(在数学运算中)。于是我们需要自己来重新设计一个方案。我们可以定义这样一个类型:
      typedef struct huge_int {  //假设sizeof(char)的值为1
              unsigned char status    ;
              unsigned char val[ 20 ] ;
              }    huge_int    ;
其中status用来保存运算中的状态,如符号,是否溢出,是否进位,非法移位等;val用来表示整数。当然这个huge_int可以表示一个160位的2进制数。
  现在类型有了,要来实现这个类型的存储方案。一种是低地址存低位,一种是高地址存低位,或者自己再设计一个更新颖更有吸引力的方案。考虑到对这两种方法的熟悉度,我一般选择第一种。
  实现这个类型的运算:位运算和四则运算。这些运算实现起来也非常简单,这里不再熬述了。
  huge_int能表示数的范围大于long long的范围,因此我们不能直接把一个10进制数直接转换成这中类型。用10进制字符来传递是个不错的方案。如"456"表示456。于是我们要实现把这种字符转换成huge_int类型。在实现了四则运算和long long转huge_int的前提下,这也是很简单的。如"456"可以这样转换成num的伪代码:
             num   =  llong_to_num('6'-'0');
             num  +=  llong_to_num('5'-'0') * llong_to_num(10 );
             num  +=  llong_to_num('4'-'0') * llong_to_num(100);
那这样把hug_int行转换成字符输出呢?方案和10进制转2进制的一样。如把1111 1111(255)转换成10进制字符的伪代码:(  num = 1111 1111  )
             ch[ 0 ] = num % 1010 ; num /= 1010 ; // *ch=0101;对应'5'
             ch[ 1 ] = num % 1010 ; num /= 1010 ; // *ch=0101;对应'5'
             ch[ 2 ] = num % 1010 ; num /= 1010 ; // *ch=0010;对应'2'           
             //直到num为0为止。然后倒序即可。
如果用的是c++来实现,可以重载运算符,就真的可以像上面的伪代码那样来写代码了,那感觉起来特舒服(附件中给出c语言实现的清单,没有任何实现)。    
  对于小数的运算。1.可以用一种类似与浮点数的方法定义这样一个类型:
           typedef struct mfloat {
                    unsigned char status    ;//状态
                    unsigned char val[ 20 ] ;//值
                    } mfloat ;
然后可以这样约定,这160位中用1位表示符号,29位表示指数,剩下的130位表示尾数。对于浮点数的四则运算也完全可以通过定点数来实现。2.可以用一种类似与浮点数的方法定义这样一个类型:
            typedef struct mfloat {
                    unsigned char status    ;//状态
                    unsigned int  pointer   ;//小数点的位置
                    unsigned char val[ 20 ] ;//值
                    } decimal;
            
  当然上面都是基与已有的基本类型的,因此在生成代码时会有很多中间操作代码,会影响效率。不过实现起来比较简单,不然直接从汇编的角度去考虑,效率会有所提高的。
           
""""""

回复列表 (共10个回复)

沙发

用char的话,效率很低,几乎所有的开源大数都使用 unsigned int

仅仅设计一个大数类型不难,难的是要有效率。有很多开源的大数,我以前也研究过,对数学和编程技巧要求很高。

板凳

确实,用int效率不仅仅只好一点点,尤其在做乘法时,运算次数大大减少。

3 楼

struct int_128  // 16字节Integer
{
#ifdef HI_LO
   unsigned __int64 Low;
   unsigned __int64 High;
#else
   unsigned __int64 High;
   unsigned __int64 Low;
#endif
};

这是俺曾用过的一个结构,可惜没在MacOS中试验过:)——年代久远,不记得到底是HI_LO还是LO_HI了~~~
呵呵:)

个人认为最好用系统的东西,否则错了会很纠结的:)

4 楼

对于大整数,个人觉得用32位无符号int作存储单元比较好,这样在实现乘法时,可以直接转成系统的64位long long数乘法,还不会溢出。

5 楼

我也觉得是HI_LO,LO_HI我认为是低位在高地址。苹果的是不是高地址存的低位?上次看一本书中提过,现在记不清了

6 楼

苹果系统的PPC版本使用的是与PC版本相反的:)
因为编译器本来就支持__int64,所以就不用4个单元了,两个搞定:)

7 楼

我的意思是:编译器不支持128位数,在两个64位数运算时有可能发生溢出,所以在运算过程中有可能还是要回到32位数。
问一个厚脸皮的问题:运行一次同类型加法和乘法的时间比大概是多少?

8 楼

如果都是整点数,则差几十倍,浮点差几百倍(都是最坏情况)——BUT:这不算是啥厚脸皮的问题哈:)

不过现在对于有超线程、SIMD/MIMD、多核、多CPU的架构,已不能这样简单的评估性能了,让程序尽可能占满流水线才好:)

9 楼

typedef struct int_128 {
        union {
              unsigned __int32 val[ 4 ] ;
              unsigned __int64 VAL[ 2 ] ;
              } val  ;                
        }   int_128  ;
这个结构用来表示128位整数感觉也还不错。

10 楼

你好.我是全职网赚工作者.
如果你有时间有电脑.
想在网络上创业.请联系我..
项目绝对真实.详情QQ空间资料
加盟请联系 QQ908889846

我来回复

您尚未登录,请登录后再回复。点此登录或注册