Cuckoo!
0%

CS205 C/C++ Project01设计报告 乘法计算器

Posted on In
只具有乘法功能的计算器，高精度，用户友好

Part 0. 团队成员

姓名 学号 贡献率
咕桃 - 100%

Part 1 - Analysis

题目重述&主要思路

本题目要求实现一个能将若干格式下的两个数进行乘法运算的简单计算器。

根据题目所给样例，可以分析出题目基础要求的数据类型：

  1. 整数
  2. 浮点数
  3. 大整数
  4. 浮点数(科学计数法)

其中对于程序设计要求最高的为大整数和浮点数(科学计数法格式)的运算，因此笔者在设计程序时选择实现大整数(科学计数法格式)以便一次性适配题目要求的所有格式，除基础要求外，本项目支持以下功能：

  1. 大整数(科学计数法)
  2. 带有K/M/G/T后缀的大整数
  3. 大浮点数
  4. 大浮点数(科学计数法)
  5. 带有K/M/G/T后缀的大浮点数
  6. 简写形式大浮点数
  7. 自定义精度计算
  8. 显示数据类型
  9. 显示科学计数法格式转换过程
  10. 交互式输入输出

模型假设

由于题目所给信息较少，笔者对输入的数据范围等进行了假设，并根据假设设计程序。

以下是本程序适配的数据范围：

对于一个科学计数法浮点数，格式记为$A.BeC$

整数部分$A$与小数部分$B$位数之和记为$n$，$1\leq n \leq 10^{4}$，即存储一万位有效数字

10的幂指数记为$C$，$-10^{18}\leq C \leq 10^{18}$，即存储上限为$10^{10^{18}}$量级

高精度乘法

对于__int128也无法存下的大数，此处使用了高精度乘法的算法进行运算。

模拟竖式计算的基础高精度乘法算法复杂度为$O(n^2)$，对于10000位有效数字，一般能在秒级时间内得出运算结果，因此使用该算法解决问题是可以接受的，就不劳压位乃至FFT和NTT牛刀杀鸡了。

高精度乘法作为广为人知的入门算法，此处不再过多赘述细节，仅简述其思路：

以$A*B=C$为例，$A$和$B$位数记为$n_A,n_B$

  1. 调整$A>B$。

  2. 采用short数组，按位存储$A$和$B$的有效数字。

  3. 模拟竖式计算，先遍历两个乘数每一位相乘的值，加到结果数的对应位。

    $C[p]=\sum^{p-1}_{i=1}\sum^{p-i}_{j=1}A[i]*B[j]$

  4. 从低位到高位取模进位。

  5. 调整结果数位数，加和幂指数，输出结果。

多类型数据的输入、互化、交叉运算

对于合法输入的多类型数据，程序将其分为7类，并使用简洁的正则表达式进行类型识别，识别不同类型后，再通过分支使用不同构造方法进行拆分存储。

本题中的运算涉及科学计数法，因此笔者采用了向上兼容，将所有数字预处理为科学计数法整数格式，即通过将位数存储于幂指数中的方式，保证次幂前数字在$(1,10)$之间，免去了传统高精度浮点运算中对齐小数点的繁杂，同时规避了不同类型数据之间的互化问题。

由于上述处理，程序仅需满足同一类型的乘法，笔者采用简洁的重载运算符写法，具有优秀的普适性和拓展性。

Part 2 - Code

正则表达式与数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
const regex pure_int("^[+-]?[0-9]+$");
const regex int_with_e("^[+-]?[0-9]+e[+-]?[0-9]+$");
const regex int_with_suffix("^[+-]?[0-9]+[kKmMgGtT]$");
const regex pure_float("^[+-]?[0-9]+.[0-9]+$");
const regex float_with_e("^[+-]?[0-9]+.[0-9]+e[+-]?[0-9]+$");
const regex float_with_suffix("^[+-]?[0-9]+.[0-9]+[kKmMgGtT]$");
const regex abbreviated_float("^[+-]?.[0-9]+$");

enum data_type
{
    NaN, PURE_INT, INT_WITH_E, INT_WITH_SUFFIX, PURE_FLOAT, FLOAT_WITH_E, FLOAT_WITH_SUFFIX, ABBR_FLOAT
};
const string type_name[] = {"NaN", "PURE_INT", "INT_WITH_E", "INT_WITH_SUFFIX", "PURE_FLOAT", "FLOAT_WITH_E", "FLOAT_WITH_SUFFIX", "ABBR_FLOAT"};

上文提到，程序将合法输入数据分为7类，分别为：纯整数、带有幂指数的整数、带有后缀的整数(kmgt)、纯浮点数、带有幂指数的浮点数、带有后缀的浮点数、简写浮点数。

此处使用enum进行记录，classifier()函数中集成正则表达式进行识别分类。在本程序中，以下样例所示格式的输入均合法：

1
2
3
4
5
6
7
PURE_INT : -19260817
INT_WITH_E : -1926e-0817
INT_WITH_SUFFIX : -19260817k
PURE_FLOAT : -1926.0817
FLOAT_WITH_E : -1926.08e-17
FLOAT_WITH_SUFFIX : -1926.0817k
ABBR_FLOAT : -.19260817

存储结构

1
2
3
4
5
6
7
8
struct BigNum
{
    int len;
    short val[10005];//1e4 digits, from low to high
    bool sign;//true: +
    ll exp;
    data_type type;
};

对于数据，此处使用结构体进行统一存储，$len$存储有效位数、$val[]$从低位到高位存储各位数字，$sign$存储符号，$exp$存储幂指数，$type$则存储数据类型(其实最后几乎都会变成INT_WITH_E)。使用结构体为后续的构造器、重载运算符带来便利。

构造器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
BigNum(string s)
    {
        transform(s.begin(), s.end(), s.begin(), ::tolower);
        this->type = classifier(s);
        switch (type)
        {
            case PURE_INT:...
            case INT_WITH_E:...
            case INT_WITH_SUFFIX:...
            case PURE_FLOAT:...
            case FLOAT_WITH_E:
            {
                int dot_pos = s.find('.');
                this->sign = true;
                int e_pos = s.find('e');
                ll base_exp = -(e_pos - dot_pos - 1);
                s.erase(dot_pos, 1);
                e_pos--;
                if (s[e_pos + 1] == '-')
                {
                    e_pos++;
                }
                for (int i = e_pos + 1; i < s.size(); i++)
                {
                    exp *= 10;
                    exp += s[i] - '0';
                }
                if (s[e_pos] == '-')
                {
                    exp = -exp;
                    e_pos--;
                }
                if (s[0] == '-')
                {
                    this->sign = false;
                    s.erase(0, 1);
                    e_pos--;
                }
                for (int i = 1; i <= e_pos; i++)
                {
                    this->val[i] = s[e_pos - i] - '0';
                }
                this->exp += base_exp;
                this->len = e_pos;
                break;
            }
            case FLOAT_WITH_SUFFIX:...
            case ABBR_FLOAT:...
            default:...
        }
    }

在classifier()识别类别后，构造器针对不同类别数据，传入字符串，生成新结构体。

各类型思路类似，此处仅展示相对复杂的FLOAT_WITH_E类型的构造过程，主要分为以下三步:

  1. 记录小数点对$exp$的贡献，抹除小数点，加和原有$exp$。
  2. 记录符号并抹除。
  3. 按位取模存储，记录$len$。

规范化格式

在运算前，首先进行格式规范化，将末位0全部纳入幂指数后抹除，降低计算复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
BigNum standardize_exp(BigNum a)
{
    BigNum c;
    c.type = PURE_INT;
    c.len = 0;
    c.sign = a.sign;
    c.exp = a.exp;
    for (int i = 1; i <= a.len; i++)
    {
        if (a.val[i] == 0 && c.len == 0)
        {
            c.exp++;
        }
        else
        {
            c.val[++c.len] = a.val[i];
        }
    }
    if (c.exp)
    {
        c.type = INT_WITH_E;
    }
    return c;
}

重载运算符

此处重载了比较符<和乘法符*。

比较符的主要作用是将较大的数放在竖式上方，因此不考虑符号。思路简单：规范化→比幂指数→从高到低逐位比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool operator<(BigNum a, BigNum b)//抛开符号比大小
{
    a = standardize_exp(a);
    b = standardize_exp(b);
    if (a.exp == b.exp)
    {
        for (int i = a.len; i >= 1; i--)
        {
            if (a.val[i] != b.val[i])
            {
                return a.val[i] < b.val[i];
            }
        }
        return false;//a==b
    }
    else
    {
        return a.exp < b.exp;
    }
}

乘法重载原理已在上文提过，此处模拟竖式计算就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
BigNum operator*(BigNum a, BigNum b)
{
    a = standardize_exp(a);
    b = standardize_exp(b);
    BigNum c, t;
    c.exp = a.exp + b.exp;
    c.sign = !(a.sign xor b.sign);
    c.len = a.len + b.len + 1;
    if (a < b)
    {
        t = a;
        a = b;
        b = t;
    }
    for (int i = 1; i <= a.len; i++)
    {
        for (int j = 1; j <= b.len; j++)
        {
            c.val[i + j - 1] += a.val[i] * b.val[j];
        }
    }
    for (int i = 1; i <= c.len; i++)
    {
        if (c.val[i] >= 10)
        {
            c.val[i + 1] += c.val[i] / 10;
            c.val[i] %= 10;
            c.len = max(c.len, i + 1);
        }
    }
    c = standardize_exp(c);
    return c;
}

输出结果

输出函数print_BigNum(BigNum a, ll constraint)初始默认以科学计数法格式，输出无精度损失的结果。

但有时候我们并不关心小数点后第10位是什么，因此该函数的constraint参数限定了小数点后的位数，通过四舍五入的方式，使得输出结果不会过于冗长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
void print_BigNum(BigNum a, ll constraint)
{
    string res = "";
    a = standardize_exp(a);
    bool flg = false;
    ll cnt = 0;
    for (int i = a.len; i >= 1; i--)
    {
        if (a.val[i] != 0 || flg)
        {
            cnt++;
            if (constraint != -1 && cnt <= constraint + 1)
            {
                flg = true;
                if(cnt==constraint+1&&(i>1&&a.val[i-1]>=5))//四舍五入
                {
                    res = res + (char) (a.val[i] + '1');
                }
                else
                {
                    res = res + (char) (a.val[i] + '0');
                }
            }
            else if (constraint == -1)
            {
                res = res + (char) (a.val[i] + '0');
                flg = true;
            }
        }
    }
    if (!flg)
    {
        res = res + "0";
    }
    if (res.size() > 1 || a.exp)
    {
        ll new_exp = a.exp + cnt - 1;
        if (res.size() > 1)
        {
            res.insert(1, 1, '.');
        }
        if (new_exp)
        {
            res += "e";
            stringstream ss;
            string tmp_s;
            ss.clear();
            ss << new_exp;
            res = res + ss.str();
        }
    }
    if (!a.sign)
    {
        res = "-" + res;
    }
    cout << res;
}

用户交互

本程序设计了用户友好的交互命令，命令列表如下：

1
2
3
4
5
6
-h help
-t type_list
-p [num] set precision
-s show datatype
-c show data convert
-q quit

分别实现了：帮助列表、支持的数据类型列表、设置小数点后保留位数、展示输入数据类型、展示转换后数据类型、退出功能，且本程序除了支持命令行参数输入单次计算外，在收到-q指令前也支持多次输入计算，并对错误输入进行报错。并且使用了>>>来让计算器看起来比较像某种语言的交互式界面。

Part 3 - Result & Verification

基础要求

Test case #1: 整数乘法

image-20220925015232703

image-20220925083649225

Test case #2: 浮点数乘法

image-20220925015341290

image-20220925083735712

Test case #3: 大整数乘法

image-20220925015438229

image-20220925083840850

Test case #4: 大浮点数乘法

image-20220925015645989

image-20220925084538204

(windows的科学计算器到这里精度就不够了)

Test case #5: 错误输入

image-20220925015809404

进阶测试

Bunched test cases : 混合格式多组输入、鲁棒性…

image-20220925021142752

拓展测试

Bunched test cases : 用户交互、精度设置、数据类型、数据转换、鲁棒性…

image-20220925022112312

Big number test case : 1000位*1000位，运行耗时52ms(含IO时间)，用户态CPU耗时11ms，系统态CPU耗时12ms。

输入：

image-20220925083224925

输出：

image-20220925083249101

Part 4 - Difficulties & Solutions

读入与存储

Difficulty：本次项目的一大难题在于输入数据的格式多样且未知，因此如何将各种格式的字符串转化为数字，以何种形式存储再进行计算是项目的核心所在。

Solution：通过自己可能的输入格式进行设计，利用正则表达式处理字符串，向上兼容全部以INT_WITH_E格式存储，减少了对齐小数点等繁杂过程。

高精度

Difficulty：对于大数的运算，无法使用原生的数据类型进行存储。

Solution：利用结构体按位存储，重载高精度乘法运算，计算时直接使用即可。

输出格式

Difficulty：对于不同的输入，应该采用怎样的输出格式？

Solution：本项目定位是科学计算器，且采用了归一化的数据存储，因此结果只要不是-9~9的PURE_INT，那么就会采用科学计数法格式进行输出，统一且优雅。

用户友好设计

Difficulty：用户不知道本项目支持的输入格式，需要查看数据类型、科学计数法转换结果等调试信息，有不同精度需求，有多次计算需求…

Solution：为了调试的时候更舒服，实现了帮助菜单，显示调试信息命令，自定义保留位数命令，交互式输入输出…

Part 5 - Summary

​ 初见题目时，一眼高精，觉得相对简单；仔细一看样例，没说输入格式，样例中包含题目要求，被不同类型数据的交叉运算困扰许久；回过头一想，不管什么输入，干脆都用科学计数法存就好了，遂切。

​ Simple is beautiful. 写项目时，笔者也在不断删改：

  • 自学了简单的正则表达式用法，代替了原有冗长缓慢的条件语句判断。
  • 使用重构运算符写法，而非函数。
  • 利用构造器对输入数据进行归一化，避免了不同结构体的交叉运算。
  • 对于实际需求选择了合适的算法，而非小题大做。
  • ……

​ 笔者经过本次项目，也对WSL环境下使用命令行进行编译、调试、运行等操作有了一定的熟悉，在使用一些陌生语法时对输入输出、结构体、字符串处理有了更深的理解。