> 科技正文

大整数的表示和相关定义 大数问题表示

      ★ 相关的数据类型定义

        在干正事之前,先定义好各种数据类型还是很有必要的,避免在以后的编码中引起混乱。

        uintX   X位无符号整形,如uint32表示32位无符号整形

        intX    X位有符号整形,如int32表示32位有符号整形

         基本数据类型定义:

            #ifdef _MSC_VER
            typedef __int8              int8;
            typedef __int16             int16;
            typedef __int32             int32;
            typedef __int64             int64;

            typedef unsigned __int8     uint8;
            typedef unsigned __int16    uint16;
            typedef unsigned __int32    uint32;
            typedef unsigned __int64    uint64;
            #else
            typedef signed char         int8;
            typedef signed short        int16;
            typedef signed int          int32;
            typedef signed long long    int64;

            typedef unsigned char       uint8;
            typedef unsigned short      uint16;
            typedef unsigned int        uint32;
            typedef unsigned long long  uint64;
            #endif

            这里的类型定义未必全部都会用上,因为都是从我其他项目直接拿来用的。

         布尔类型:

             typedef uint8 boolean;
             #define TRUE                  1
             #define FALSE                 0

      ★ 大整数类型的定义

          C语言的最长类型是64位,对于超过64位的无符号整形应该如何保存?很简单,用多个单精度类型存储即可。

        比如1234可以表示成1×1000+2×100+3×10+4×1,于是很容易想到采用十进制,数组的每一位用0到9表示,然后对数字数组按照笔算的原理编写加减乘除函数,但是这么做效率会很低的,因为1024比特的大数在十进制下也有三百多位,对于任何一种运算,都需要在两个有数百个元素的数组空间上多次重循环,还需要许多额外的空间存放计算的进退位标志及中间结果,速度可想而知了,同时,对于一些移位运算,使用十进制会变得非常麻烦,而且速度也会大打折扣。对于程序猿来讲,二进制思维是很重要的,在这里就体现出来了。对于大整数计算,可以采用2^n进制来简化计算过程(2^n进制实际上就是二进制的缩减表示而已),对于32位的系统,n可以取32,这样用于表示大整数的数位会大大减少。例如十进制的4294967296可以表示成1,0 (2^32进制),4294967297可以表示成1, 1 (2^32进制),而且处理移位计算会十分方便。

           首先定义单精度类型和双精度类型:

           typedef uint32 bn_digit;         //定义大整数数位类型,通常情况下长度为操作系统的字长,相当于一个无符号的单精度类型.

           typedef uint64 bn_udbl;         //定义双字长无符号整形,32位系统下就是64位,相当于一个双精度类型.

           typedef int32  bn_sint;            //有符号单精度类型,长度为操作系统的字长.

           之所以这么定义,是为了方便移植,对于64位操作系统bn_digit就是64位的无符号整形(这种情况下使用的是2^64进制),此时bn_udbl无定义。

              bignum结构定义:

           typedef struct
           {
                  int sign;             //符号标识,1表示非负整数,-1表示负整数。
                  size_t alloc;       //表示数组dp在增加大小之前的可用数位,alloc数必须是非负整数。
                  size_t used;       //表示数组dp用了多少位来表示一个指定的整数,used数必须是非负整数。
                  bn_digit *dp;    //指针dp指向动态分配的代表指定多精度整数的数组,不足位(alloc-used)全部置0,数组中的数据按照LSB顺序存储(低地址保存低位)
            } bignum; 

               有效的bignum结构:

              考虑到效率还有代码的健壮性,给bignum结构的状态指定了几个规则(某些情况下例外):

              1. alloc的值为非负整数,也就是说,dp要么指向一个预先分配有空间的数组,要么为NULL。

              2. used的值为非负整数,且used<=alloc。

              3.used的值暗示了数组dp中的第used-1位数不能为0,也就是说以0为首的高位必须被截断,数组dp中第used个及以上的位置必须置为0。

              4. 如果used是0,则sign = 1,此时bignum的值为0或者dp仅仅初始化但没分配内存。

      ★ 参数传递

      在任何库的开发过程中,都应该尽早确定函数参数传递的约定,避免在以后的开发中随着库的增大以及复杂度的增加而遇到难题。在我的大整数库中,采用赋值的方式表示。例如计算两个大整数a,b的和,结果放在c中,函数原型就是: int bn_add_bn(bignum *c, const bignum *a, const bignum *b);    即c = a + b,函数返回一个整形,用于表示计算时是否遇到错误,如内存分配失败等,返回0表示函数调用正常。

      ★ 错误处理

      在大整数算法中,最有可能碰到的问题,就是动态内存分配出错,当然还有一些其他问题,以后在慢慢讨论。对于内存错误,只要一出现,后面的计算就无法进行了,应该立即退出并返回错误值。在我的大数库中,有以下的错误被定义:

    //Error Value
   #define BN_MEMORY_ALLOCATE_FAIL                 -0x0001         //动态内存分配错误
   #define BN_EXCEED_MAX_LIMB                             -0x0002         //超出最大数位
   #define BN_EXCEED_MAX_BITS                              -0x0003         //超出最大的比特位
   #define BN_NEGATIVE_VALUE_ERROR                  -0x0004         //负数错误
   #define BN_INVALID_INPUT                                    -0x0005         //无效输入
   #define BN_DIVISION_BY_ZERO                              -0x0006         //除以0错误
   #define BN_BUFFER_TOO_SMALL                           -0x0007         //缓冲区太小
   #define BN_READ_FILE_ERROR                                -0x0008         //读文件错误
   #define BN_WRITE_FILE_ERROR                               -0x0009         //写文件错误
   #define BN_NO_MODULAR_INVERSE                     -0x000A         //模逆不存在

   错误检查宏:

  #define BN_CHECK(x)                   if((ret = x) != 0){ goto clean; }

        这个宏的作用是用来检查函数中每一步操作的执行情况,一旦检测到错误(非0的函数返回值),即把函数的返回值置ret为错误值x,然后跳转到函数末尾执行清理操作(通常是临时变量的动态内存释放)。这个宏定义里面使用了goto语句,通常情况下应该是避免使用goto语句,这在大多数情况下是有必要的,然而当所有函数都可能出现调用失败的时候,使用几行代码来处理错误就显得很有意义了。

      对于一个大整数计算的函数,通常的形式是这样的:

       int bn_function(bignum *b, const bignum *a)

       {

                  int ret;              //如果使用了BN_CHECK宏,ret必须被定义

                  bignum c;

                  bn_init(&c);        //临时变量初始化

                  /**

                    * Do something here

                    */

                   BN_CHECK(bn_function2(b, a, c));      //BN_CHECK检查bn_function2的调用情况,如果出错,直接跳转到clean后执行清理操作。

        clean:

                  bn_free(&c);       //临时变量内存释放

                   return ret;          //返回错误值,如果无错误,ret = 0.

       }

      ★ 总结