主题:对高精度运算实现的一个假想
类型,我是这样理解的:用来保存数据的一种方案。根据这种方案来对数据进行各种操作等。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;
当然上面都是基与已有的基本类型的,因此在生成代码时会有很多中间操作代码,会影响效率。不过实现起来比较简单,不然直接从汇编的角度去考虑,效率会有所提高的。
""""""