当前位置:首页 > Windows程序 > 正文

C#实现任意大数的计算和简单逻辑命题的证明

2021-05-24 Windows程序

在前言中粗略地展示了MathAssist的“计算和证明”能力,本篇开始将详细介绍其实现原理。 从计算开始说起,要实现任意大数的计算器首先得有一个类支持大数运算,于是本篇介绍BigNumber的实现。
一般编程语言提供的数字类型都是基于cpu位数来实现,这样做是为了在基础类型上保证运算速度。 想当年本人刚开始学vb6(也是刚开始学程序)时,

想用这个圆周率公式来精确到小数点后上万位,可结果好像是在小数点后7、8位就无法再精确了。 稍微想下就可明白原因——所使用的float类型本身就只提供小数点后几位的精确度,而用它所计算出来的结果怎么可能精确到很多呢?
既然编程语言提供的类型无法实现无限精度,那么可以自定义一个类型来实现之。 其关键思想就是用数组来存储大数每位上的数,比如用List<int> (这里不严谨地将Lite<T>称为数组)。比如123456789这个数,可以将其放在数组中,数组元素分别为1,2,3,4,5,6,7,8,9。 然后再实现算法来完成加、减、乘、除运算即可。

BigNumber概要

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