柴 君

天津电子信息职业技术学院，天津 300350

0 引言

首先，我们来阅读如下简单C语言程序:

很显然，如果是在Turbo C环境下运行，则输出的结果是字符串no。出现这种结果的原因也不是很难分析:由于计算机给任何数据分配的内存空间都是有限的，它不能直接存放任意大或者任意精度的数据。但是在计算机应用中，尤其是信息安全密码学和科学计算中，大数运算和高精度运算有着普遍的需求。在这种矛盾中，对超过范围的数据（这里的范围包括大小和精度:普遍的开发环境中，long型的数据大小小于1011，double型的数据精度小于16位），就必须设计新的数据结构进行存储，并定义基于新结构的基本运算[1]。在本文中，我们将分析大整数的存储和运算的实现。

根据如何存储大整数的方法不同，我们将实现方法分为数组方式实现和链表方式实现两种。

1 数组方式实现分析

1）大整数数组存储

在数制表达当中，进制数（即基数）是基础。一个整数A表达成 A = (a0a1… an)，其实际表示的是一个以 a0、 …an为系数的多项式: A =，其中的X表示基数[2]。所以，存储一个大整数，实际上就是存储这些系数，而最直观的就是数组存储了。但如果一个数组元素存储一个十进制系数，会存在明显的空间浪费，运算实现过程也会出现循环次数过多的问题，效率低。因此要选择合适的基数X:分析发现如果取X=10000是比较合适的，一方面并没有超出long型数据的范围，另一方面会减少大整数的实际位数，提高空间和时间上的效率。同时，十进制数转换为万进制数不会改变大整数原有的数字形式，也就不需要多余的数字转换运算，只需要把原数的每四位看成一个整体，依次存入数组而已。……