BigInteger （亿进制高精度）类设计实验报告

课程设计题目：BigInteger（亿进制高精度）类设计实验

一、问题描述

C/C++ 语言中的 int 类型能表示的整数范围是-2^{31}~2^{31}-1，unsigned int 类型能表示的整数范围是 0~2^{32}-1，即 0~4294967295，所以，int 和 unsigned int 类型都不能存储超过10位的整数。有些问题需要处理的整数远远不止10位，这种大整数用C/C++语言的基本数据类型无法直接表示。请编写算法完成两个大整数的加、减、乘和除等基本的代数运算。

二、基本要求

  1. 大整数的长度在100位以下；
  2. 设计存储结构表示大整数；
  3. 设计算法实现两个大整数的加、减、乘和除等基本的代数运算；
  4. 分析算法的时间复杂度和空间复杂度。

三、概要设计

1. 数据结构的设计

采取符号和数位分离，以便模拟手算。

存储结构我们使用 C++ 自带的 vector，这样既在能随机存取的情况下，又能实现按需分配空间。

存储数位时，我们每8位存放在一个 int 里（亿进制高精度）。较之每1位存一个 int 的写法（十进制高精度），虽然不改变时间复杂度和空间复杂度，但通过压位能降低常数（相当于 n 变成 n/8，n 为 BigInteger 的位数），实际运行表现有较大改善。

2. 算法的设计

关于 BigInteger 类实现的各种算法，多为模拟手算过程，在此就以较复杂的除法（BigInteger 除 BigInteger）为例，其余的算法就只给出时间复杂度和空间复杂度，实现方法便不一一赘述了。

伪代码如下

BigInteger operator/(BigInteger a, BigInteger b) {
    if (b == 0) throw "被零除";
    c.sign = a.sign * b.sign;
    a.sign = b.sign = 1; // 这样只用考虑整数除整数
    for (int i = a.s.size() - b.s.size(); i >= 0; i--) {
        // 模拟手算的竖式除法，这里用二分求要填的数
        int l = 0, r = BigInteger::BASE - 1;
        int mid = (l + r + 1) >> 1;
        for (; l < r; mid = (l + r + 1) >> 1) {
            d = b * mid 再移位（乘以10^?）;
            
            // 更新 l 或 r
            if (a > d) l = mid;
            else r = mid - 1;
        }
        a = a - b * l 再移位（乘以10^?）;
        c.s[i] = l; // 竖式除法中的填上数步骤
    }
    return c;
}

记n为大整数的位数（十进制），BASE为进制，WIDTH为 BigInteger 中一位对应十进制的宽度。在亿进制高精度的情况下，这里BASE=10^8,WIDTH=8。

我们分析整个除法计算次数最多的步骤。类似手算除法的竖式除法，商的位数最多是除数位数与被除数的位数之差，又因为采用亿进制，故商的位数与n/WIDTH同阶。每一位我们都要试商，若用二分法试商，则试商次数为log_2{BASE}。商试过程中，我们需要到道高精度乘低精度和高精度比较大小，时间复杂度为O(n)。故时间复杂度为O(\frac{n}{WIDTH}*log_2{BASE}*n)，忽略常数得O(n^2)。

整个算法中，需要几个临时的 BigInteger 变量，故空间复杂度为O(n)。

时间复杂度 空间复杂度
O(n^2) O(n)

其余的基本代数运算：

加、减

时间复杂度 空间复杂度
O(n) O(n)

乘、取模

时间复杂度 空间复杂度
O(n^2) O(n)

比较运算符

时间复杂度 空间复杂度
O(n) O(1)

3. 抽象数据类型的设计

ADT BigInteger
Operation
    构造函数
        前置条件：BigInteger 不存在
        输入：一个 long long 或正确的 string
        功能：构造相应的 BigInteger
        输出：无
        后置条件：一个相应的 BigInteger
    析构函数
        前置条件：一个已经存在的 BigInteger
        输入：无
        功能：销毁该 BigInteger
        输出：无
        后置条件：释放该 BigInteger 所占用的存储空间
    +  -  *
        前置条件：无
        输入：两个已经存在的 BigInteger
        功能：实现两个 BigInteger 的加、减或乘运算
        输出：返回运算结果（BigInteger）
        后置条件：两个 BigInteger 不变
    /  %
        前置条件：无
        输入：两个已经存在的 BigInteger
        功能：实现两个 BigInteger 的整除或取模运算
        输出：若除数非零，返回运算结果（BigInteger），否则抛出异常
        后置条件：两个 BigInteger 不变
    <  >  ==  <=  >=
        前置条件：无
        输入：两个已经存在的 BigInteger
        功能：实现两个 BigInteger 的比较大小
        输出：返回运算结果（bool）
        后置条件：两个 BigInteger 不变
    +=  -=  *=  /=  %=
        前置条件：一个已经存在的 BigInteger
        输入：另一个已经存在的 BigInteger
        功能：实现类似于 C++ int 的五个赋值运算符
        输出：返回运算结果（BigInteger）
        后置条件：类似于 C++ int 的结果
    <<
        前置条件：无
        输入：一个已经存在的 BigInteger
        功能：输出该 BigInteger
        输出：返回运算结果（ostream）
        后置条件：该 BigInteger 不变
    >>
        前置条件：有输入流
        输入：一个已经存在的 BigInteger
        功能：从输入流中提取大整数到该 BigInteger 中
        输出：返回运算结果（istream）
        后置条件：该 BigInteger 读入了大整数
endADT

四、详细设计

1. 设计抽象数据类型对应的C++类定义

为避免文章过于冗杂，请参见后文五、运行与测试 -> 4. 程序清单与运行结果。

2. 设计每个成员函数

成员函数除了前文三、概要设计 -> 3. 抽象数据类型的设计中所列出的借口，还有部分辅助函数，例如void __defragment()用于实现整理 BigInteger，BigInteger __BigInteger_shift(const BigInteger &b, const int &x)用于实现除法过程中需要的移位。它们的实现并不复杂，为避免文章过于冗杂，请参见后文五、运行与测试 -> 4. 程序清单与运行结果。

3. 设计主函数

主函数主要包括调用构造函数，加减乘除取模等运算进行测试。

五、运行与测试

1. 测试环境

运行环境：Windows 20H2, i7-9750H @ 2.60GHz, 16GB RAM

编译器：gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)

编译命令：-g

运行终端：cmd

2. 在调试程序的过程中遇到的问题与解决方案

问题1：执行完sprintf后变量i莫名其妙改变了

解决方案：经过仔细检查，我排除了自己编程出错的情况，于是判断为编译器异常。后重装编译器，现问题已解决。

问题2：对拍时与 Python 计算结果有差异

解决方案：出现问题的原因是，Python 中的整除是向下取整，而 C++ 一般是向零取整，所以当遇到负数的情况下，两种取整方式计算出的商和余数可能不同。后在和 Python 的对拍中，只考虑自然数大整数运算，现问题已解决。

问题3：对拍中 Python 运行速度远远快于 C++

解决方案：原来是对拍程序里的有个计时器忘记累加时间了，改正后现问题已解决。

3. 设计的测试数据与测试结果

测试1为设计部分极端样例，观察程序是否符合预期。

输入样例1

12
-5

输出样例1

7
17
-60
-2
2

输入样例2

-12
5

输出样例2

-7
-17
-60
-2
-2

输入样例3

-12
-5

输出样例3

-17
-7
60
2
2
-2

输入样例4

12345678901234567890
0

输出样例4

12345678901234567890
12345678901234567890
0

然后在除零时抛出异常。

有先导0的情况会在测试2中测试。

测试2为用随机数生成100位左右的大整数，和标程对拍，对拍10000次。

4. 程序清单及运行结果

程序清单如下

// main.cpp

#include <iostream>
#include "BigInteger.h"
using namespace std;

int main()
{
    // BigInteger y;
    // BigInteger x = y;
    // BigInteger z = -12356789012345678ll;
    // cout << z;

    BigInteger a, b;
    cin >> a >> b;
    cout << a + b << "\n";
    cout << a - b << "\n";
    cout << a * b << "\n";
    cout << a / b << "\n";
    cout << a % b << "\n";

    return 0;
}

// BigInteger.h

#ifndef BIGINTEGER_H
#define BIGINTEGER_H 1

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class BigInteger
{
public:
    BigInteger(long long num = 0);
    BigInteger(const string &str);
    ~BigInteger();

    BigInteger operator=(const long long num);
    BigInteger operator=(const string &str);

    BigInteger operator+() const;
    BigInteger operator-() const;

    friend BigInteger operator+(const BigInteger &a, const BigInteger &b);
    friend BigInteger operator-(const BigInteger &a, const BigInteger &b);
    friend BigInteger operator*(const BigInteger &a, const BigInteger &b);
    friend BigInteger operator/(const BigInteger &a, const BigInteger &b);
    friend BigInteger operator%(const BigInteger &a, const BigInteger &b);

    BigInteger operator+=(const BigInteger&b);
    BigInteger operator-=(const BigInteger&b);
    BigInteger operator*=(const BigInteger&b);
    BigInteger operator/=(const BigInteger&b);
    BigInteger operator%=(const BigInteger&b);

    friend bool operator<(const BigInteger &a, const BigInteger &b);
    friend bool operator>(const BigInteger &a, const BigInteger &b);
    friend bool operator==(const BigInteger &a, const BigInteger &b);
    friend bool operator<=(const BigInteger &a, const BigInteger &b);
    friend bool operator>=(const BigInteger &a, const BigInteger &b);

    friend ostream &operator<<(ostream &out, const BigInteger &x);
    friend istream &operator>>(istream &in, BigInteger &x);

private:
    vector<int> s;
    int sign = 1;

    static const int BASE = 100000000;
    static const int WIDTH = 8;

    void __defragment();
    friend BigInteger __BigInteger_shift(const BigInteger &b, const int &x);
};

#endif /* BIGINTEGER_H */


#ifndef BIGINTEGER_H
#define BIGINTEGER_H 1

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class BigInteger
{
public:
    BigInteger(long long num = 0);
    BigInteger(const string &str);
    ~BigInteger();

    BigInteger operator=(const long long num);
    BigInteger operator=(const string &str);

    BigInteger operator+() const;
    BigInteger operator-() const;

    friend BigInteger operator+(const BigInteger &a, const BigInteger &b);
    friend BigInteger operator-(const BigInteger &a, const BigInteger &b);
    friend BigInteger operator*(const BigInteger &a, const BigInteger &b);
    friend BigInteger operator/(const BigInteger &a, const BigInteger &b);
    friend BigInteger operator%(const BigInteger &a, const BigInteger &b);

    BigInteger operator+=(const BigInteger&b);
    BigInteger operator-=(const BigInteger&b);
    BigInteger operator*=(const BigInteger&b);
    BigInteger operator/=(const BigInteger&b);
    BigInteger operator%=(const BigInteger&b);

    friend bool operator<(const BigInteger &a, const BigInteger &b);
    friend bool operator>(const BigInteger &a, const BigInteger &b);
    friend bool operator==(const BigInteger &a, const BigInteger &b);
    friend bool operator<=(const BigInteger &a, const BigInteger &b);
    friend bool operator>=(const BigInteger &a, const BigInteger &b);

    friend ostream &operator<<(ostream &out, const BigInteger &x);
    friend istream &operator>>(istream &in, BigInteger &x);

private:
    vector<int> s;
    int sign = 1;

    static const int BASE = 100000000;
    static const int WIDTH = 8;

    void __defragment();
    friend BigInteger __BigInteger_shift(const BigInteger &b, const int &x);
};

#endif /* BIGINTEGER_H */

测试1

样例1（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week04\BigInteger>BigInteger.exe
12
-5
7
17
-60
-2
2

样例2（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week04\BigInteger>BigInteger.exe
-12
5
-7
-17
-60
-2
-2

样例3（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week04\BigInteger>BigInteger.exe
-12
-5
-17
-7
60
2
-2

样例4（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week04\BigInteger>BigInteger.exe
12345678901234567890
0
12345678901234567890
12345678901234567890
0
terminate called after throwing an instance of 'char const*'

测试2（符合预期）

和 Python 对拍

Python 代码

# BigInteger.py

a = int(input())
b = int(input())
print(a + b)
print(a - b)
print(a * b)
print(a // b)
print(a % b)

对拍程序（.cpp）

// 对拍.cpp

#include <ctime>
#include <iostream>
using namespace std;

const int _T = 1e4;

int main()
{
    clock_t mycpp_start_time, mycpp_end_time;
    double mycpp_total_time;
    clock_t ans_py_start_time, ans_py_end_time;
    double ans_py_total_time;

    int TTT = _T;
    while (TTT--)
    {
        cout << "Case: " << _T - TTT << "\n";
        system("rand.exe > BigInteger.in");

        ans_py_start_time = clock();
        system("python BigInteger.py < BigInteger.in > BigInteger.ans");
        ans_py_end_time = clock();
        ans_py_total_time += (double)(ans_py_end_time - ans_py_start_time) / CLOCKS_PER_SEC;
        
        mycpp_start_time = clock();
        system("BigInteger.exe < BigInteger.in > BigInteger.out");
        mycpp_end_time = clock();
        mycpp_total_time += (double)(mycpp_end_time - mycpp_start_time) / CLOCKS_PER_SEC;

        if (system("fc BigInteger.ans BigInteger.out"))
        {
            system("pause");
            break;
        }
    }
    if (TTT == -1)
    {
        cout << "Complete.\n";
        cout << "Run times: " << _T << "\n";
        cout << "Ans py total time: " << ans_py_total_time << "s\n";
        cout << "My cpp total time: " << mycpp_total_time << "s\n";
    }
    else
        cout << "error" << endl;
    system("pause");
    return 0;
}

随机数据生成程序（.cpp）（不考虑负数，原因见五、运行与测试 -> 2. 在调试程序的过程中遇到的问题与解决方案）

// rand.cpp

#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

inline void work(int x)
{
    // if (rand() & 1)
    //     printf("-");
    while (rand() & 15)
        printf("0");
    while (x--)
        printf("%d", (rand() << 15) + rand());
    printf("\n");
}

int main()
{
    srand(time(NULL));
    rand(), rand(), rand();

    work(12);
    work(10);

    return 0;
}

对拍结果如下

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week04\BigInteger>对拍.exe

（中间输出过长已省略）

Case: 9999
Comparing files BigInteger.ans and BIGINTEGER.OUT
FC: no differences encountered

Case: 10000
Comparing files BigInteger.ans and BIGINTEGER.OUT
FC: no differences encountered

Complete.
Run times: 10000
Ans py total time: 357.602s
My cpp total time: 173.728s
Press any key to continue . . .

像这类的程序，C++ 比 Python 运行速度更快但代码实现更难，这是符合预期的。

和 cpp 标程对拍

cpp标程来自技能书的博客高精度压位（亿进制）模板，网址https://blog.csdn.net/long_hen/article/details/105023965。不过他取模的两个数均为负的情况符号写错了，我帮他改过来了。

代码过长，在此便不展示了。

对拍程序大体同上，只修改了部分名称。

随机数据生成程序同上，但删去注释，即考虑有负数的情况。

对拍结果如下

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week04\BigInteger>对拍.exe

（中间输出过长已省略）

Case: 9999
Comparing files BigInteger.ans and BIGINTEGER.OUT
FC: no differences encountered

Case: 10000
Comparing files BigInteger.ans and BIGINTEGER.OUT
FC: no differences encountered

Complete.
Run times: 10000
Ans cpp total time: 136.167s
My cpp total time: 173.101s
Press any key to continue . . .

考虑到我用的是vector，而标程用的是数组，这个结果可以接受。

六、总结与心得

  1. C++ 相较于其他编程语言的高性能在本例中体现得淋漓尽致。

  2. 高精度不愧为最能锻炼代码能力的模板之一，原理简单但实现难，同时还得考虑很多特殊情况。写一遍高精度，受益匪浅。

  3. 实际上，上述部分写法有些部分为了代码实现方便而小幅度牺牲了性能，例如 BigInteger 的构造函数可以直接写而不是调用operator =。如需获得更好的性能表现，这些部分可以改善，但会使代码更加冗杂。

  4. 如果采用FFT（快速傅里叶变换）和NTT（快速数论变换）算法，可以将乘法的时间复杂度优化到O(nlonn)。再利用牛顿迭代，可以将除法的时间复杂度优化到O(nlonn)，进而优化取模。不过可惜的是，本人实力有限。

  5. 笔者以前没有敲过高精度除高精度，也没敲过亿进制高精度。以前总想着代码实现很难很恐怖，但敲完这次后感觉也没有那么繁琐。人有时候真的只是被自己吓倒了。不禁让人想起一句曾经的网络流行语：

消除恐惧的最好办法就是面对恐惧。加油，奥利给！

七、参考资料

  1. 刘汝佳. 算法竞赛入门经典. 清华大学出版社, 2009.
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

  • 高精度计算
    高精度计算 有时候C语言内置数据类型难以处理非常大的整数计算，此时需要自己实现大整数计算。 数字存储方式 一般的高...
    yuq329阅读 409评论 0赞 2
  • 模版:高精度加减乘除
    4个高精度的关键位置是t的表示，t均是上一位留下来的值，遵从大的在前，小的在后 加法：上一位留下来的整除后的进位数...
    得力小泡泡阅读 467评论 0赞 0
  • 高精度运算
    之前早就想把学过的算法记录下来，但是一直没有时间。最近在给五年级的小学生上OI的算法课，所以正好可以把所思所想留存...
    flydan阅读 1,148评论 0赞 0
  • 高精度 - 高精度数除以低精度数
    1 题目描述 输入位数小于5000位的被除数以及在整形数据范围内的除数，要求输出两者进行除法运算后的整数商，忽略小...
    Veahow阅读 1,833评论 0赞 0
  • 大数据阶乘运算-java高精度运算
    在java中提供了两个拥有高精度计算了类：BigInteger和BigDecimal BigInteger：支持任...
    荔枝哥阅读 732评论 0赞 0

友情链接更多精彩内容