C#实现任意大数的计算和简单逻辑命题的证明
在前言中粗略地展示了MathAssist的“计算和证明”能力,本篇开始将详细介绍其实现原理。 从计算开始说起,要实现任意大数的计算器首先得有一个类支持大数运算,于是本篇介绍BigNumber的实现。
一般编程语言提供的数字类型都是基于cpu位数来实现,这样做是为了在基础类型上保证运算速度。 想当年本人刚开始学vb6(也是刚开始学程序)时,
想用这个圆周率公式来精确到小数点后上万位,可结果好像是在小数点后7、8位就无法再精确了。 稍微想下就可明白原因——所使用的float类型本身就只提供小数点后几位的精确度,而用它所计算出来的结果怎么可能精确到很多呢?
既然编程语言提供的类型无法实现无限精度,那么可以自定义一个类型来实现之。 其关键思想就是用数组来存储大数每位上的数,比如用List<int> (这里不严谨地将Lite<T>称为数组)。比如123456789这个数,可以将其放在数组中,数组元素分别为1,2,3,4,5,6,7,8,9。 然后再实现算法来完成加、减、乘、除运算即可。
BigNumber的属性很简单:
List<int> IntPart; //整数部分
List<int> DecimalPart; //小数部分
bool IsPlus; //是否是正数
BigNumber AbsoluteNumber; //返回绝对值
BigNumber ReverseNumber; //返回相反数
上面说过可以在数组元素中每个元素存储一位,不过细想一下,数组元素类型是int,最大是2147483647,可以存储多位数。这样存储后不仅可以大大节约程序的内存空间,也节约提高了运算速度。
故提供一个静态只读变量 int OneCount 来表示一个数组元素中存储数的位数。为了方便调试现在暂时设置为 4。
看一个简单的例子:
如果用如下的代码实例化一个BigNumber
BigNumber num1 = new BigNumber("13579.02468");
那么其IntPart为1, 3579,其DecimalPart为246, 8000。
也就是说从小数点开始,整数部分从右往左每4个一组,小数部分从左往右每4个一组。上面的246其实应该是0246,而用int表示的0246和246是一样的。而8000不能用8表示,如果是8的话,那么表示的就是13579.02460008这个数了。
BigNumber还实现了接口IComparable,这样用CompareTo()即可比较两个BigNumber的大小。
从字符串中识别出BigNumber其实就是一个很简单的状态机,首先看首字符是否为 - +
如果为-,那么这个数为负数,跳到4
如果为+, 那么这个数为正数,跳到4
如果为数字,那么这个数为正数,跳到4
扫描所有数字直到遇到 . 将扫描到的所有数字分组后存储在IntPart中
扫描所有数字直到结尾,将扫描到的所有数字分组后存储在DeciamlPart中
具体代码在IdentifyNumber.cs中.
注意不支持首字符是小数点的写法,即".14159"是非法格式。
加、减、乘、除的实现加、减、乘、除的实现本质上就是模拟人工用笔算,考查的是对for, if和数组的驾驶能力。下面将讲解核心点以及需要注意的地方,具体的代码细节不在此赘述,有兴趣的朋友可以再交流。后面提供源码,以供参考。
加、减法的实现考虑到正、负号,加减法各有4种情况,分别如下
正数加正数、正数加负数、负数加正数、负数加负数
正数减正数、正数减负数、负数减正数、负数减负数
而减法又要考虑两数的大小。
不过用绝对值和相反数进行变换后,上面的情况其实可以划归为两种:正数加正数、较大数减较小数。
比如负数加负数,可以先将两负数取绝对值后变成正数加正数,得到的结果指定为负数即可;正数减负数,其实就是正数加正数。具体代码在BigCalculate.Add(), BigCalculate.Minus()中。
而正数加正数、较大数减较小数,先计算小数部分、再计算整数部分,注意进位、对齐等问题即可。现在一个数组元素中存储一个四位数,那个当和为10000时才要需要进位。代码在BigCalculate.PlusAdd(), BigCalculate.PLusMinus()中。
乘法的实现乘法在笔算中会先忽略小数点,所以先要将BigNumber转化为List<int>,然后对两个List<int>进行相乘。BigCalculate.Multiply(List<int> one, List<int> two)函数实现。
具体的算法就是在双重for循环中依次对两个数组中的元素进行相乘,注意进位的问题即可。
除法的实现温馨提示: 本文由Jm博客推荐,转载请保留链接: https://www.jmwww.net/file/70203.html