首页 > 代码库 > 大整数运算 ——第一次个人项目报告

大整数运算 ——第一次个人项目报告

1.          首先在输入上,除了考虑第一位正负号和起始0的情况外,还考虑了每行仅仅只有一个换行符的情况。防止在多组输入情况下,误输入4行数据。

2.          在加法运算中,主要分类讨论了两个运算符的加减情况,直接先判断结果的正负情况,再判断是加法还是减法,减法运算仅仅是改变了第二个运算符的正负情况,特别判断了一下运算符是0和结果是0的输出情况,运算才用手工模拟。

3.          乘法采用了FFT的算法,将在时域上复杂度为O(n^2)的卷积运算,变成了频域上简单的相乘,将时间复杂度降低为了O(nlogn),提高了运算的效率。

4.          除法运算采用手工模拟算法,本想到使用牛顿迭代法进行优化,可以时间限制,未能完成,最后10万位除以5万位,时间大概在5秒左右。

5.          除此之外对加减法和乘除法采用不同进制进行运算,加快各个运算之间的效率。

6.          优点在于适应各种输入,都采取了防范措施,防止程序崩溃

代码链接:https://github.com/zj140/calc/blob/master/calc.cpp

大整数运算 ——第一次个人项目报告