存储空间是离散的,所以随机访问效率也不高,而且频繁的堆操作和引用操作势必大量增加开销,不利于编译器优化速度;另外,根据内存管理方式的不同,顺序存储方式可以再分为静态存储方式和动态存储方式。
静态存储方式数组的大小是事先已经知道的,适合知道大小的整数运算。
而因其数组长度是固定不变的,在运算的时候容易造成溢出。
所以其不适合不定长度的整数运算。
而动态方式,其可以动态分配内存空间。
可以根据整数位数的变化调整大小。
其是最常用的顺序存储方式,而且顺序存储方式是连续分配空间,所以其可以实现随机访问,提高速度,因为存储空间就是整数本身,没有其他额为开销,所以空间利用率也较高。
由于受到计算机字长的限制制约着大整数的运算,所以必须要解决大整数表示问题 , 通 常 是 采 用 B 进 制 表 示 , 如 x x x x ...x , 其 表 示 为 : 0 1 2 n b n 1 n2x x b x b x 2 b ... x n 1 b x n ( x 0 0 ) ( 0 i n )必 n 1 0 1 ,而且系数 x 0须是计算机可以表示的常数。
在基选择上,最容易想到也是最直接易懂的是用整数数组来保存大数,数组的每个元素保存大数的一个十进制数字,这种方式操作比较简单,但这种方式需要较多的额外运算,而且效率明显不高,也需要比较多的存储空间;效率比 3较高的,被采用的比较多的方式是用 B 进制数组存储大数,即把大数转化 B 进制表示,数组的每个元素存储这个 B 进制数的一个 B 进制的数位,这样既方便计算机处理又提高了内存的利用率,同时缩短了大数的实际表示长度,减少了循环的次数,有利于提高效率。
为了更好的适应各种算法的需要及避免过度浪费存储空间,本文采用多精度的方式。
1985 年,西安交通大学的王永祥副教授曾经采用过万进制的方法表示大数,并实现了自己的大数算法11。
根据万进制的原理,本文决定将整数进制 B 取为 2 的某次幂。
本文是基于 32 位系统,VC有__int64 这样的 64 位整数类型,但 32 位硬件上毕竟不能直接处理 64 位整数,那势必需要附加内部操作来完成。
为了匹配硬件操作,取 B 进制为半个 CPU 字长的 unsigned short int 型,即 216 进制. 由于 m 位的数乘以 n 位的数最多将产生 mn 位的数所以两个 216 进制数位的乘积可以用一个 232 数来保存而不超出 CPU的字长。
2.1.2 大整数结构 为了模块化编程程序结构清晰易懂。
本文在开始之前先对大整数做一个结构封装,使用一个结构体来表示大整数。
标示符 MBigInt 表示一个多精度的大整数结构:typedef struct / 定义大整数的结构 / long int alloclen / 记录数组已经分配总的空间大小 / long int length / 记录大整数的长度,即系数的个数 / int sign / 记录大整数的符号 / un_short pBigInt/ 指向大整数的数据的指针,即指向系数的地址 / MBigInt 上面大整数封装的结构中,分别记录大整数分配到的空间 alloclen 大小和已经在使用到的空间 length 大小。
使用这种结构能够有效地管理内存,减少堆操作的次数,减少相关操作带来的性能损失;通过一个指针来指向保存大整数的数据的数组,这样有利于内存的动态调整,可以不移动数组的任何元素而交换两个大整数,其只需要交换三个内置的整数值和一个指针就可以了。
本文所讨论的大整数的数位是按照低位在前的方式存放,则按从低位到高位的顺序把大整数的数位按下标从小到大顺序存放到数组中去,也 4就是十进制表示方式相反方向,这样既有利于扩展大数的长度也有利于缩减。
2.2 预定义的变量 因为在编程的时候很多的变量字符比较长,很容易略写某个字符,造成编程错误,所以本文首先对一些变量进行预定义。
typedef unsigned short int un_short /16 位数的声明符号/ypedef unsigned long int un_long /32 位数的声明符号/define BIT_PRE_WORD 16UL / 每个单精度数字含有的 bit 数 // 定义信号标识 /RETU.
上一篇:
企业日常工作排班系统【毕业论文,绝对精品】
下一篇:
给你春季巧治上火的养生妙方