大整数算法[01] 大整数的表示和相关定义
★ 相关的数据类型定义
在干正事之前,先定义好各种数据类型还是很有必要的,避免在以后的编码中引起混乱。
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位,相当于一个双精度类型。
之所以这么定义,是为了方便移植,对于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.
}
★ 总结
本片文章简单介绍了大整数的相关定义,下一篇就要开始讲讲最基本的维护算法,主要有大整数的初始化,精度增加,内存释放等等。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。