C++大整数运算(一):概述

6+

C++大整数运算系列文章讲述了实现大整数四则运算的基本思路和方法,对算法做简单的介绍并采用C++代码做进一步说明。本文并不试图写成一篇教程,而是对实现过程进行整理和概括。实现过程中学习了 Donald E. Knuth 著作的 The Art of Computer Programming 中的相关内容,特此致敬。

本文是C++大整数运算系列文章的第一篇,主要介绍作者对大整数运算的浅显认识和理解。

目录

实现一个大整数类的想法源于三年前(重度拖延症患者),那时还是一个ACMer,在刷题的时候遇到一个大整数求幂的题目,想了几种自己写得出来的方法都会超时,后来又试过几次,总感觉自己的想法太low,就搁置了。几个月前不知道为什么又把这件事想起来了,于是就写到了日程规划上,经过很多天零零散散地学习和整理,终于把基础的东西实现了,便在这里整理一下思路,把自己的想法和学到的知识记录下来。

实现大整数运算的基本思路就是使用数组模拟数位进行运算,比如使用字符数组或整型数组。使用字符数组保存每个十进制数字,计算时逐个数字运算是一种符合我们平时计算四则运算的方法,比如:

   “12345”
+  “54321”
__________
=  “66666”

但很明显,这样空间利用效率很低,且每次计算都要将字符转换成数字,保存结果的时候还要将数字转换成字符,很不方便。

如果采用整型数组来保存数位,就能解决这两个问题。首先,整型数组中保存的本身就是数字,不需要转换;其次,数组中每个数可以保存多个数位,解决了空间利用效率低的问题。而采用整型数组来保存数位,根据基数的不同,也至少有两种常用的方法。

1. 以10的幂次为基数

以10的幂次为基数即以10^k为基数,例如在32位计算机上使用int或unsigned型数组保存数位,可以选择10^4、10^8等作为基数。以10^k作为基数就是说如果把整型数组中的每个数看作一个数位,那么这个数组可以看作是10^k进制的数。以10的幂次作为基数可以很方便地将(用户输入的)十进制表示的字符串转换成整型数组的存储方式,也可以将整型数组的存储方式快速地转换成十进制的字符串。以10的幂次作为基数的缺点是每次计算都要进行除法操作来获得余数和进位,降低了运算效率。

2. 以2的幂次为基数

以2的幂次为基数即以2^k为基数,例如在32位计算机上使用int或unsigned型数组保存数位,可以选择2^16、2^30、2^32等作为基数。以2的幂次作为基数可以很方便地通过移位运算来计算余数和进位,比除法快很多。但用户的输入以及用户期望的输出一般是十进制的数,因此以2^k作为基数时,进制转换可能会花费一些时间。

上述两种方法各有优劣,如果为了方便实现,选择10的幂次为基数就可以了;但作者认为以2的幂次为基数是更优的选择,通常可以假设大部分时间是在中间的运算过程中消耗的,而用户需要查看的只是最后的结果(很少需要进行进制转换),因此以2的幂次为基数的优势更明显一些,本系列文章选择2^32为基数。

另一个需要说明的事情是存储方向的问题。由于运算过程中可能会产生进位,因此,将数据的低位保存在数组的“前面”,高位保存在数组的“后面”,这样在需要进位时可以利用数组后面预留出来的空间,而不需要将所有的数据都向后移动。关于预留空间的事情可以交给std::vector去做,而我们的重点放在四则运算上面。

到这里,一些基础的想法和工作已经完成,我们决定采用std::vector<unsigned>来保存数位,采用2^32进制来进行计算,使用数据“倒序存储”的方法避免进位时的(不必要的)移动。当存储方式确定之后,计算方法基本也已经定型,下一节将介绍如何进行加法和减法操作。

6+

发表评论

电子邮件地址不会被公开。 必填项已用*标注